В настоящем пункте будем рассматривать число 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 1 , a 2 не являются порождающими элементами группы U p , то a 1 a 2 также не является порождающим элементом U p . Отсюда делаем вывод о том, что наименьший порождающий элемент группы U p – простое число.
Пример
p =71. p -1=70=2·5·7.
Для того чтобы a являлся порождающим элементом, необходимо и достаточно, чтобы выполнялись условия: a 10 1(mod n ), a 14 1(mod n ), a 35 1(mod n ).
Будем испытывать числа из U 71 . Вместо a b mod 71 для краткости будем писать a b .
2: 2 10 =30, 2 14 =54, 2 35 =1. 2 не является порождающим элементом.
3: 3 10 =48, 3 14 =54, 3 35 =1. 3 не является порождающим элементом.
В настоящем пункте будем рассматривать число 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 1 , a 2 не являются порождающими элементами группы U p , то a 1 a 2 также не является порождающим элементом U p . Отсюда делаем вывод о том, что наименьший порождающий элемент группы U p – простое число.
Пример
p =71. p -1=70=2·5·7.
Для того чтобы a являлся порождающим элементом, необходимо и достаточно, чтобы выполнялись условия: a 10 1(mod n ), a 14 1(mod n ), a 35 1(mod n ).
Будем испытывать числа из U 71 . Вместо a b mod 71 для краткости будем писать a b .
2: 2 10 =30, 2 14 =54, 2 35 =1. 2 не является порождающим элементом.
3: 3 10 =48, 3 14 =54, 3 35 =1. 3 не является порождающим элементом.
5: 5 10 = 1. 5 не является порождающим элементом.
7: 7 10 =45, 7 14 =54, 7 35 =70. 7 – порождающий элемент.
Итак, наименьший порождающий элемент группы U 71 (или первообразный корень по модулю 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 10 ={1, 3, 7, 9}
3 2 =9, 3 3 =7, 3 4 =1. O 10 (3)=4=φ(10). 3 – первообразный корень.
7 2 =9, 7 3 =3, 7 4 =1. O 10 (7)=4=φ(10). 7 – первообразный корень.
9 2 =1. O 10 (9)=2.
Действительно, нашлись два первообразных корня по модулю 10.
Теорема 3
Пусть с
=φ(m
), q
1 , q
2 , … , 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 g a , но в криптографии применяют сочетание «дискретный логарифм» и пишут γ=log g a . Поскольку на протяжении настоящего пособия не раз встретится упоминание о так называемой задаче дискретного логарифмирования, будем употреблять последний вариант названия и написания. Тем более, что дискретные логарифмы обладают некоторыми свойствами логарифмов непрерывных:
Свойство 1: Дискретный логарифм разнозначен в полной системе вычетов по модулю φ(m ).
Свойство 2: log g ab …h≡ log g a +log g b +…+log g h (mod φ(m )).
Свойство 3: log g a n ≡n log g a (mod φ(m )).
Доказательство этих свойств не представляет сложности и является прямым следствием определений дискретного логарифма и первообразного корня.
Определение 1: Показателем (порядком) целого числа a по данному модулю m называется наименьшее целое положительное число, обозначаемое через , которое удовлетворяет следующему сравнению: .
Пример 1. Найти 
.
Составим последовательно сравнения вида 
. Наименьшее значение k, при котором получим b=1 и будет искомой характеристикой.
Следовательно, =5.
Теорема 1: Справедливы следующие утверждения:
3. 
Теорема 2: Сравнение 
имеет место тогда и только тогда, когда .
Определение 2: Класс вычетов 
называется первообразным корнем по модулю m, если показатель класса вычетов равен функции Эйлера, т.е. . Вместе с классом 
мы будем называть первообразными корнями и все числа этого класса.
Чтобы убедиться, что а, где (а,m)=1, - первообразный корень по модулю m, достаточно проверить, что , где к – собственные делители .
Пример 2. По модулю 54 класс - первообразный корень. Действительно, . Собственные делители равны k = {1, 2, 3, 6, 9}. Легко проверить, что при всех k.
Первообразные корни существуют не для всех модулей, а только для модулей вида 1, , где p – нечетное простое число, 
.
Для нахождения первообразного корня по простому модулю m можно пользоваться следующим критерием:
Лемма: Пусть 
и - различные простые делители числа с. Для того чтобы число g, (g, m)=1 было первообразным корнем по модулю m, необходимо и достаточно, чтобы это g не удовлетворяло ни одному из сравнений
.
Пример 3: Найти первообразный корень по модулю 41.
Решение: Имеем . Следовательно, для того чтобы число g было первообразным корнем по модулю 41, необходимо и достаточно, чтобы это g не удовлетворяло ни одному из сравнений:
Испытывая числа 2,3,4,…, находим
Отсюда видим, что число 6 – первообразный корень, так как оно не удовлетворяет ни одному из сравнений (*).
Определение 3. Пусть 
. Число s называется индексом числа b по модулю m и основанию a, если имеет место сравнение: . При этом используют обозначение .
Пример 4. Так как .
Ввиду практической пользы индексов для каждого простого модуля p (не слишком большого) составлены таблицы индексов (см. например в ). Это две таблицы: одна – для нахождения индекса по числу, другая – для нахождения числа по индексу.
Пример 5. Построить таблицы индексов для модуля p=41.
В примере 3 было показано, что первообразным корнем по модулю 41 является число. Его мы и примем за основание индексов. Находим сравнения (сравнения берутся по модулю 41):
| N | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 0 | 26 | 15 | 12 | 22 | 1 | 39 | 38 | 30 | |
| 1 | 8 | 3 | 27 | 31 | 25 | 37 | 24 | 33 | 16 | 9 |
| 2 | 34 | 14 | 29 | 36 | 13 | 4 | 17 | 5 | 11 | 7 |
| 3 | 23 | 28 | 10 | 18 | 19 | 21 | 2 | 32 | 35 | 6 |
| 4 | 20 |
| I | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 1 | 6 | 36 | 11 | 25 | 27 | 39 | 29 | 10 | 19 |
| 1 | 32 | 28 | 4 | 24 | 21 | 3 | 18 | 26 | 33 | 34 |
| 2 | 40 | 35 | 5 | 30 | 16 | 14 | 2 | 12 | 31 | 22 |
| 3 | 9 | 13 | 37 | 17 | 20 | 38 | 23 | 15 | 8 | 7 |
Здесь, номер строки указывает число десятков, номер столбца – число единиц. Так, например, чтобы найти ind 25 воспользуемся таблицей слева. Искомый индекс находится на пересечении 2 строки и 5 столбца и равен 4. Число, индекс которого равен 33 найдем из второй таблицы на пересечении 3 строки и 3 столбца. Это число 17.
Теорема 3. Пусть - первообразный корень по модулю m, (b,m)=1. Тогда сравнение имеет место тогда и только тогда, когда 
Теорема 4. Пусть - первообразный корень по модулю m, . Тогда
