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

                                          

 

Тогда

 

                      

                        Определение. Если

 

                                    

 

где число b – взаимно простое с n, то за

  принимается значение      

 

 

                          Теорема. Пусть g – первообразный корень по модулю n и b – число взаимно простое с модулем n, n > 1, т.е. (b,n) = 1.

Тогда

                     

 

                         Рассмотрим случай, когда модуль простое число. В этом случае известно, что по любому простому p существуют φ(p-1) классов первообразных корней. Если взять за основание какое – либо g из любого класса первообразных корней, то для любого числа b, которое не делится на p, существуют индексы. Будем рассматривать наименьший из всех возможных индексов числа b  по основанию a для простого модуля p. При этих условиях для простых модулей p иногда вычисляют таблицу индексов для всех целых чисел из интервала [1,p-1].

                          Кроме того, известно , если число p, p > 2 – простое, то для составных модулей вида   и   существуют первообразные корни. Поэтому для чисел взаимно простых с модулями  и      существуют индексы.

 

                  Пример. Пусть дан модуль  где p – простое число. Вычислим

 

          

           

Известно, что  показатели k, для которых

 

                                             

 

должны быть делителями φ(n). Делителями числа 18 являются числа 1, 2, 3, 6, 9. Однако существует теорема, которая утверждает, что первообразные корни по модулю  будут первообразными корнями и по модулю    ,t ≥ 2. По этой логике для того, чтобы найти показатели для некоторого числа a, для которого выполняется сравнение       по модулю n = 27, достаточно рассмотреть только показатели, которые являются  делителями значения  функции   Эйлера для числа   Имеем,

 

                   

 

                            Итак, среди показателей  k < φ(9) числа a, для которых выполняется сравнение

                                        

 

могут быть только делители числа φ(9) = 6. Отсюда следует, что для любого числа a показатель k < φ(9) , для которого выполняется сравнение   , могут быть только числа 1, 2, 3.

                            Рассмотри число g = 5. проверим, является ли число g первообразным корнем по модулю n = 27. Для этого вычислим

• , и          

       

                        

По теории в  условиях данной задачи существует такое k, для которого

 

                                   

 

причем показатель k является делителем φ(9). Из выкладок следует, что таким показателем может быть только число φ(9) = 6. проверим данный вывод:

 

       

 

Из вычисления  следует, что 5 есть первообразный корень по модулю 9, а значит, число g = 5 является первообразным корнем и по модулю n = 27.

                     Убедившись, что g = 5 первообразный корень по модулю n = 27, т.е.

 

             

 

перейдем к  вычисления индексов по модулю 27 с основанием g = 5. Имеем следующие индексы чисел по основанию g = 5 по модулю 27

 

                         

           

 

                          

    

    

 

 

В итоге проделанных  вычислений получаем следующие значения дискретных логарифмов по модулю 27 при  основании 5:

 

 

В заключении рассмотрим сравнение 

 

                                          

 

Вычислить y при заданных значениях p, g и x не представляет труда. Обратная задача – по значениям p, g  и y вычислить x, т.е. определить индекс или дискретный логарифм – трудная задача с точки зрения числа арифметических операций.

                        Сложность этой задачи для  реально используемых значений модуля p находится за пределами возможностей современных вычислительных систем. Поэтому некоторые современные криптографические системы с открытыми ключами создаются на базе задачи дискретного логарифмирования. К подобным системам можно отнести схему Эль – Гамаля и схему Шнорра. Данные схемы используются для решения некоторых криптографических задач.

 

 

                   §5.Индексы по любому составному модулю

 

 

                       Теорема1. Пусть m = 2^tp₁^t₁p₂^t₂… p_k^t_k – каноническое разложение числа m. Пусть далее c  и c₀ имеют значения, указанные в теореме, т.е. c =1, c₀ = 1, если  t = 0 или t = 1; c = 2, c₀ = 2^t-2 , если t ≥ 2; c_s = φ(p_s^t_s), g_s – наименьший первообразный корень по модулю p^t_s.

 

                         Теорема2. Если

 

                                     a ≡ (-1)^γ5^γ₀(mod 2^t),

                                     a ≡ g₁^γ₁(mod p₁^t₁),…, a ≡ g_k^γ_k(mod p_k^t_k),           (1)

 

то система  γ, γ₀, γ_1, …, γ_k называется системой индексов числа a по модулю m.

                         Из такого определения следует, что γ, γ₀ – система индексов числа a по модулю 2^t, а γ_1, …, γ_k – индексы числа a по модулям p₁^t₁, …, p_k^t_k . Поэтому всякое a, взаимно простое с m ( тем самым оно взаимно простое и со всеми 2^t , p₁^t₁, …, p_k^t_k), имеет единственную систему индексов γ^’, γ^’₀, γ^’₁, …, γ^’_k среди cc₀c₁…c_k = φ(m) систем γ, γ₀, γ_1, …, γ_k, которые получим, заставляя γ, γ₀, γ_1, …, γ_k независимо друг от друга пробегать наименьшие неотрицательные вычеты по модулям c, c₀, c₁,…, c_k, а все системы индексов числа a суть все системы γ, γ₀, γ_1, …, γ_k , составленные из неотрицательных чисел классов

 

                          γ ≡ γ^’₁(mod c),  γ₀ ≡ γ^’₀(mod c₀),

                          γ₁ ≡ γ^’₁(mod c₁), …, γ_k ≡ γ^’_k(mod c_k).

 

                        Числа a с данной системой индексов γ, γ₀, γ_1, …, γ_k могут быть найдены путем решения системы (1), а следовательно, образуют класс чисел по модулю m.

 

                         Теорема3. Так как индексы γ, γ₀, γ_1, …, γ_k числа a по модулю m являются индексами его соответственно по модулям 2^t , p₁^t₁, …, p_k^t_k , то верна теорема:

                         Индексы произведения сравнимы  по модулям c, c₀, c₁,…, c_k с суммами индексов сомножителей.

 

                         Теорема4. Пусть τ = φ(2^t) при t ≤ 2  и τ = 1/2 φ(2^t) при t > 2 и пусть h – общее наименьшее кратное чисел τ, с₁, …, с_k .

                         При всяком a, взаимно простом с m, сравнение a^h ≡ 1 верно по всем модулям 2^t , p₁^t₁, …, p_k^t_k , значит , это сравнение верно и по модулю m. Поэтому а не может быть первообразным корнем по модулю m в тех случаях, когда h <φ(m). Но последнее имеет место при t >2, при k >1, а также при t = 2, k = 1. Поэтому для m > 1 первообразные корни могут существовать лишь в случаях m = 2, 4, p₁^t₁, 2p₁^t₁.  Но как раз для этих случаев существование первообразных корней было доказано выше(§2) . Поэтому все случаи, когда существуют первообразные корни по модулю m, превосходящему 1, суть

 

                                    m = 2, 4, p^t, 2p^t.

 

 

 

 

 

                                       §6.Примеры

 

 

1) Построим таблицы для модуля p = 41. Первообразным корнем по модулю 41 будет g = 6; его мы примем за основание индексов. Находим (сравнения берутся по модулю 41):

 

 

6⁰ ≡ 1

6¹ ≡ 6

6² ≡ 36

6³ ≡ 11

6⁴ ≡ 25

6⁵ ≡ 27

6⁶ ≡ 39

6⁷ ≡ 29

6⁸ ≡ 10

6⁹ ≡ 19

6¹⁰ ≡ 32

6¹¹ ≡ 28

6¹² ≡ 4

6¹³ ≡ 24

6¹⁴ ≡ 21

6¹⁵ ≡ 3

6¹⁶ ≡ 18

6¹⁷ ≡ 26

6¹⁸ ≡ 33

6¹⁹ ≡ 34

6²⁰ ≡ 40

6²¹ ≡ 35

6²² ≡ 5

6²³ ≡ 30

6²⁴ ≡ 16

6²⁵ ≡ 14

6²⁶ ≡ 2

6²⁷ ≡ 12

6²⁸ ≡ 31

6²⁹ ≡ 22

6³⁰ ≡ 9

6³¹ ≡ 13

6³² ≡ 37

6³³ ≡ 17

6³⁴ ≡ 20

6³⁵ ≡ 38

6³⁶ ≡ 23

6³⁷ ≡ 15

6³⁸ ≡ 8

6³⁹ ≡ 7

 

 

 

поэтому указанные  таблицы будут

 

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, т.е. ind 25 = 4. Число, индекс которого 33, найдем в графе второй таблицы, общей строке с номером 3 и столбцу с номером 3, т.е. 33 = ind 17.

 

2) Для сравнения    x⁸ ≡ 23(mod 41) имеем (8, 40) = 8, причем ind 23 = 36 не делится на 8. Поэтому это сравнение неразрешимо.

 

3) Для сравнения   x¹² ≡ 37(mod 41)  имеем (12, 40) = 4, причем ind 37 = 32 делится на 4. Поэтому это сравнение разрешимо, причем это сравнение имеет 4 решения. Указанные решения найдем следующим образом.

 Это сравнение равносильно таким:

 

                                 12 ind x ≡ 32(mod 40), ind x ≡ 6(mod 10).

 

Отсюда для ind x найдем 4 несравнимых по модулю 40 значения:

 

                                             ind x = 6, 16, 26, 36,

соответственно  чему найдем 4 решения этого сравнения:

                                              x ≡ 39; 18; 2; 23(mod 41).

 

4) Является ли число 5 первообразным корнем по модулю 54?

 

                 φ(54) = φ(2*3³) = φ(2) * φ(3³) = 1(3³-3²) = 18

 

По свойству порядок числа можно искать среди  делителей φ(m):

 

                                     18: 1, 2, 3, 6, 9, 18

 

5¹ ≡ 5(mod 54)

5² ≡ 25(mod 54)

5³ ≡ 125 ≡ 17(mod 54)

5⁶ ≡ (5³)² ≡ 17² ≡ 289 ≡ 19(mod 54)

5⁹ ≡ (5³ * 5⁶) ≡ 17 * 19 ≡ 323 ≡ -1 ≡ 53(mod 54)

5¹⁸ ≡ (5⁹)² ≡ (-1)² ≡ 1(mod 54)

 

P₅₄(5) = 18 = φ954)

 

Следовательно, 5 – первообразный корень по модулю 54.

 

5) Решить сравнение:

 

8x ≡ -11(mod 37)

(8, 37) = 1, отсюда следует, что сравнение имеет единственное решение

ind(8x) ≡ ind(-11)(mod 36)

ind 8 + ind x ≡ ind 26(mod 36)

33 + y ≡ 24(mod 36)

y ≡ -9(mod 36) ≡ 27(mod 36)

ind x ≡ 27(mod 36)

x ≡ 31(mod 37)

 

6) Решить сравнение:

 

15x⁴ ≡ 17(mod 23)

ind 15 + 4 ind x ≡  ind 17(mod 22)

3 + 4 ind x ≡ 9(mod 22)

4 ind x ≡ 6(mod 22)

4 y ≡ 6(mod 22)

(4, 22) = 2 и 6 (/2), отсюда следует, что сравнение имеет 2 решения

2 y ≡ 3(mod 11)

2 y ≡ 14(mod 11)

y ≡ 7(mod 11), y ≡  18(mod 11)

ind x ≡ 7(mod 22) = > x ≡ 10(mod 23), ind x ≡ 18(mod 22) = > x ≡  13(mod 23)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                 

 

 

 

 

 

 

 

 

 

 

Список  литературы

 

1. Виноградов И. М. Основы теории чисел. — Москва-Ижевск: НИЦ «Регулярная и хаотическая динамика», 1965

 

2. С. Т. Зевало и др. «Алгебра и теория чисел», Москва 1983

 

3. Бухштаб А.А. Теория чисел. - М.: Просвещение, 1966.

 

4. Л. Я. Куликов «Алгебра и теория чисел», М.: Высшая школа, 1979.

 

5. Михелович Ш.Х. Теория чисел. -2-е изд. - М.: Высшая школа, 1967.

 

6. Нестеренко Ю. В. Теория чисел : учебник для студ. высш. учеб. заведений / Ю. В. Нестеренко. — М.: Издательский центр «Академия», 2008. 

 

7.  Сизый С. В. Лекции по теории чисел: Учебное пособие для математических специальностей. Екатеринбург: Уральский государственный университет им. А. М. Горького, 1999. 

 

8. А. Вейль Основы теории чисел. - М.: Мир, 1972

 

9.  Кочева А. А. Задачник-практикум по алгебре и теории чисел. Ч. III. Для студентов-заочников II курса фнз.-мат. фак. пед. ин-тов. — М.: Просвещение, 1984.

 

10.     Хассе Г. Лекции по теории чисел. М.: Наука, 1953.