Нахождение первообразных корней по простому модулю

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

Теорема

O_n(a)=n—1 1) a^n—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.

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

Первообразные корни существуют не для всякого модуля. Действительно, как было показано в Примере 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.

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

Если 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)).

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