Как найти первого разную корня - Исправление недочетов и поиск решений вместе с Examum.ru

Первообразный корень по модулю ― целое число такое, что

${displaystyle g^{phi (m)}equiv 1mod m}$

${displaystyle g^{ell }not equiv 1mod m}$

при

Где ― функция Эйлера.

Иначе говоря, первообразный корень — порождающая мультипликативной группы кольца вычетов по модулю .

Для первообразного корня его степени ${displaystyle g^{0}=1,g,...,g^{phi (m)-1}}$ несравнимы между собой по модулю и образуют приведенную систему вычетов по модулю .
Таким образом, для каждого числа , взаимно простого с , найдется
показатель (), для которого

${displaystyle g^{ell }equiv amod m}$

Первообразные корни существуют не для всех модулей, а только для
модулей вида

${displaystyle m=2,4,p^{a},2p^{a}}$

где ― простое число.
В этих случаях мультипликативные группы приведенных классов вычетов по модулю устроены наиболее просто: они являются циклическими группами порядка .
С понятием первообразного корня по модулю тесно связано понятие индекса числа по модулю .

История

Первообразные корни для простых модулей были введены Эйлером, но существование первообразного корней для любых простых модулей было доказано лишь Гауссом в 1801.

Пример

Проверим, является ли число 3 первообразным корнем по модулю 7.
Если это так, то каждое число от 1 до 6 должно быть представлено
остатком от деления некоторой степени тройки на 7,
действительно, перебором убеждаемся:

${displaystyle 3^{1}equiv 3 {pmod {7}}}$

${displaystyle 3^{2}equiv 2 {pmod {7}}}$

${displaystyle 3^{3}equiv 6 {pmod {7}}}$

${displaystyle 3^{4}equiv 4 {pmod {7}}}$

${displaystyle 3^{5}equiv 5 {pmod {7}}}$

3⁶ = 1 (mod 7)

Примеры наименьших первообразных корней по модулю m:

m	2	3	4	5	6	7	8	9	10	11	12
первообразный корнь mod m	1	2	3	2	5	3	—	2	3	2	—

hu:Primitív gyök
pl:Pierwiastek pierwotny
ta:ஏது மூலம், மாடுலோ p
vi:Căn nguyên thủy modulo n

Источник

Эта статья находится в разработке!

Первообразные корни

Определение:

Вычет называется первообразным корнем по модулю , если .

Где — порядок числа , а — функция Эйлера.

Теорема:

Пусть — первообразный корень по модулю . Тогда ^a — первообразный корень по модулю НОД.

Доказательство:

Так как g^a — первообразный корень, значит (g^a)^φ(p)=1, но p, поэтому φ(p)=p-1, значит (g^a)^p-1=1, и это же справедливо для g: g^p-1=1. Пусть НОД(a;p-1)=k, k>1, тогда . Но, по определению ord, — минимальная степень, в которую следует возвести , чтобы получить единицу, а . Получили противоречие, теорема доказана.
cdot Теперь докажем обратную теорему:

Пусть существует k такое, что , и . Но , значит . Следовательно либо , либо . Но по определению первообразного корня, и ord, , то есть , а так как НОД, то , что противоречит нашему предположению. Обратная теорема доказана.

Теорема (О количестве первообразных корней):

Количество различных первообразных корней по модулю p равно φ(p-1).

Доказательство:

Пусть g — первообразный корень.
Во-первых, исходный первообразный корень существует, так как мультипликативная группа поля вычетов циклична (то есть ).
Во-вторых, при . Таким образом есть смысл рассматривать только первообразные корни, образованные из исходного, путем возведения в степень не выше .

По доказанной обратной теореме — первообразный корень. С другой стороны для любого другого a, по прямой теореме не является первообразным корнем. Но по определению равно количеству НОД . Очевидно, для всех различны. Теорема доказана.

Источник

В настоящем пункте
будем рассматривать число n,
причем n—1=* — каноническое разложение на простые
сомножители.

Теорема

O_n(a)=n—1
1)aⁿ^—1≡1(mod
n);

2)
,1(mod
n).

Доказательство:

Пусть O_n(a)=n—1.
Тогда (1) выполняется в силу определения
порядка элемента в группе. Кроме того,
,
1 ≤<n—1=
O_n(a),
откуда в силу определения порядка
элемента, выполняется (2).

Пусть теперь
выполнены (1) и (2). Покажем, что O_n(a)=n—1.

В силу (1), O_n(a)(n—1).
В силу (2), O_n(a)
не делит
.
Значит,O_n(a)=n—1.

□

Результатами
только что доказанной теоремы можно
пользоваться для нахождения
порождающего элемента группы U_p,
причем проверять стоит только второй
пункт, так как первый для простого
модуля выполняется автоматически
согласно теореме Ферма. Кроме того,
можно вывести правило:
если a₁,
a₂
не являются порождающими элементами
группы U_p,
то a₁a₂
также не является порождающим элементом
U_p.
Отсюда делаем вывод о том, что наименьший
порождающий элемент группы U_p
– простое число.

Пример

p=71.
p—1=70=2·5·7.

Для того чтобы a
являлся порождающим элементом, необходимо
и достаточно, чтобы выполнялись условия:
a¹⁰1(mod
n),
a¹⁴1(mod
n),
a³⁵1(mod
n).

Будем испытывать
числа из U₇₁.
Вместо a^b
mod
71 для краткости будем писать a^b.

2: 2¹⁰=30, 2¹⁴
=54, 2³⁵=1.
2 не является порождающим элементом.

3: 3¹⁰=48, 3¹⁴=54, 3³⁵=1.
3 не является порождающим элементом.

5: 5¹⁰= 1.
5 не является порождающим
элементом.

7: 7¹⁰=45, 7¹⁴=54, 7³⁵=70.
7 – порождающий элемент.

Итак, наименьший
порождающий элемент группы U₇₁
(или первообразный корень по модулю
71) есть 7.

6.5. Существование и количество первообразных корней.

Первообразные
корни существуют не для всякого модуля.
Действительно, как было показано в
Примере 2 п.1, не существует первообразных
корней по модулю 8.

Теорема 1

Первообразные
корни по модулю m
существуют
m=2,
4, p^α
или 2p^α,
где p
– простое нечетное число.

Теорема 2

Количество
первообразных корней по модулю m,
если они существуют, есть φ(φ(m)).

Пример:

Определить
количество первообразных корней по
модулю 10.

10 = 2·5=2р.
Первообразные корни существуют. Найдем
их количество.

φ(φ(10))=φ(4)=2.

Проверим результат.
U₁₀={1,
3, 7, 9}

O₁₀(1)=1;

3²=9,
3³=7,
3⁴=1.
O₁₀(3)=4=φ(10).
3 – первообразный корень.

7²=9,
7³=3,
7⁴=1.
O₁₀(7)=4=φ(10).
7 – первообразный корень.

9²=1.
O₁₀(9)=2.

Действительно,
нашлись два первообразных корня по
модулю 10.

Теорема 3

Пусть с=φ(m),
q₁,
q₂,
… , q_k
– различные простые делители с.
Тогда g:
(g,m)=1
– первообразный корень по модулю m
не выполняется ни одно из сравнений,i=1,2,…,k.

■

Теорема, доказанная
в предыдущем пункте, является частным
случаем данной теоремы при простом n.

6.6. Дискретные логарифмы.

Если g
– первообразный корень по модулю m
(порождающий элемент U_m),
то, если γ пробегает полную систему
вычетов по модулю φ(m),
то g^γ
пробегает приведенную систему вычетов
по модулю m.

Для чисел a:
(a,m)=1
введем понятие об индексе, или о
дискретном логарифме.

Если a≡g^γ
(mod
m),
то γ называется индексом,
или дискретным
логарифмом
числа а
по основанию g
по модулю m.

В теории чисел
принято употреблять слово «индекс» и
писать γ=ind_ga,
но в криптографии применяют сочетание
«дискретный логарифм» и пишут γ=log_ga.
Поскольку на протяжении настоящего
пособия не раз встретится упоминание
о так называемой задаче дискретного
логарифмирования, будем употреблять
последний вариант названия и написания.
Тем более, что дискретные логарифмы
обладают некоторыми свойствами
логарифмов непрерывных:

Свойство 1:
Дискретный логарифм разнозначен в
полной системе вычетов по модулю φ(m).

Свойство 2:
log_gab…h≡log_ga+log_gb+…+log_gh
(mod
φ(m)).

Свойство 3:
log_gaⁿ≡nlog_ga(mod
φ(m)).

Доказательство
этих свойств не представляет сложности
и является прямым следствием определений
дискретного логарифма и первообразного
корня.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

Источник

Таблица J.1 показывает первый первообразный корень по модулю простого числа первообразных корней для простых чисел, меньших чем 1000.

Таблица
J.1.

Простое	Корень	Простое	Корень	Простое	Корень	Простое	Корень	Простое	Корень	Простое	Корень	Простое	Корень
2	1	103	5	241	7	401	3	571	3	739	3	919	7 .
3	2	107	2	251	6	409	21	577	5	743	5	929	3
5	‘7	109	6	257	3	419	2	587	2	751	3	937	5
7	3	113	2	263	5	421	2	593	3	757	2	941	2
11	2	127	3	269	2	431	7	599	7	761	6	947	2
13	2	131	2	271	6	433	5	601	7	769	11	953	3
17	3	137	3	277	5	439	15	607	3	773	2	967	5
19	2	139	2	281	3	443	2	613	2	787	2	971	2
23	5	149	2	283	3	449	3	617	3	797	2	977	3
29	2	151	6	293	2	457	13	619	2	809	3	983	5
31	3	157	5	307	5	461	2	631	3	811	3	991	6
37	2	163	2	31 1	17	463	3	641	3	821	2	997	7
41	6	167	5	313	10	467	2	643	11	823	3
43	3	173	2	317	2	479	13	647	5	827	2
47	5	179	2	331	3	487	3	653	2	829	2
53	2	181	9	337	10	491	2	659	2	839	11
59	2	191	19	347	2	499	7	671	2	853	2
61	2	193	5	349	2	503	5	673	5	857	3
67	2	197	2	353	2	509	2	677	9	859	2
71	2	199	3	359	7	521	3	683	5	863	5
73	5	211	2	367	6	523	2	691	3	877	2
79	3	323	3	373	2	541	2	701	2	881	3
83	2	227	2	379	2	547	2	709	2	883	2
89	2	229	6	383	5	557	2	719	11	887	5
97	5	!33	3	389	2	563	2	727	5	907	2
101	2	239	7	397	5	569	3	733	6	911	17

Источник