Модулярная арифметика (продолжение) Квадратичные вычеты Степенные вычеты

 

Продолжим исследовать вычеты.

Широкое применение в криптографии нашла формула:

xn ≡ a mod m, n=2

xn ≡ a mod p – квадратичный вычет

b сравнимо с a по модулю p, где

b= x2

 

(числа х и а из интервала (1- (р-1))

p-простое число, р>2. b ≡ a mod p

 

 

Пример

Пусть p=7 (р берем из диапазона всех простых нечетных чисел, больших 2) Все возможные остатки: 0,1,2,3,4,5,6

Подставим вместо x^

12 ≡ 1 mod 7

22 ≡ 4 mod 7

32 ≡ 2 mod 7 =9

42 ≡ 2 mod 7 =16

52 ≡ 4 mod 7 =25

62 ≡ 1 mod 7 =36

Все остатки можно разделить на 2 класса:

1,2,4 – квадратичные вычеты

3,5,6 - квадратичные невычеты

Число квадратичных вычетов равно числу квадратичных невычетов и равно

(p-1)/2

 

 

Приложение

 

 

Пусть модуль составное число и раскладывается на 2 простых сомножителя:

 

m=p*q=5*7=35

α=(p-1)(q-1)/4 – число квадратичных вычетов, которые являются взаимнопростыми с m

4*6/4=6

12 ≡ 1 mod 35=1

22 ≡ 1 mod 35=4

32 ≡ 1 mod 35=9

42 ≡ 1 mod 35=16

52 ≡ 1 mod 35=25

62 ≡ 1 mod 35=1

72 ≡ 1 mod 35=14

82 ≡ 1 mod 35=29

92 ≡ 1 mod 35=11

…………………..

 

 

Число неповторяющихся вычетов – 11

Из них взаимнопростых чисел с 35 – 1, 4, 9, 11, 16, 29

Для нахождения квадратичных вычетов достаточно перебрать только половину.

 

 

Критерий Эйлера для определения является ли число а квадратичным вычетом.

a(p-1)/2 ≡ 1 mod p – элемент принадлежит к классу квадратичных вычетов Если a(p-1)/2 ≡ -1 mod p, то элемент принадлежит к классу квадратичных невычетов

 

Степенные вычеты первообразный элемент (корень)

 

 

Пусть мы имеем модуль m.

Возьмем некоторый элемент а из диапазона: 1≤а≤m-1

И начинаем возводить его в степени:

a1 , a2 ,…, a j( m ) При этом (a,m)=1 aj(m) ≡ 1 mod m

ak ≡ 1 mod m, где k≤φ(m)

k называется показателем числа а по модулю m

 

Определение. Показателем a по модулю m (Pm(a) или просто P(a))

называется наименьшая положительная степень числа a, при которой выполняется сравнение:

 

aP ( a )

 

º1 mod m .

 

Из определения следует, что для любых чисел

r º1, P(a) -1

 

(натуральных чисел, меньших P(a)) не должно выполняться сравнение вида

 

a r º 1mod m .

 

Пример 2.7. Найти значение P11(3). Число 5 может быть показателем

 

числа 3, так как 35 mod 11 = (34 ? 3) mod 11 = (4? 3) mod 11 = 1, то есть

 

35 º1 mod 11 .

 

А для чисел

 

3r mod 11 ≠ 1:

r = 1, 4

не выполняется условие

3r º 1mod 11, то есть

 

31 mod 11 = 3 ≠ 1;

 

32 mod 11 = 9 ≠ 1;

 

33 mod 11 = 27 mod 11 = 5 ≠ 1;

 

34 mod 11 = (27? 3) mod 11 = (5×3) mod 11 = 4 ≠ 1.

 

Ответ: показатель степени для числа 3 по модулю 11 равен P11(3) = 5.

 

Число a, где (a, m) = 1, называется первообразным элементом (первообразным корнем, порождающим элементом)по модулю m, если показатель a по этому модулю равен φ(m), то есть

P(a) = φ(m).

 

Таким образом, первообразным элементом является число a, для которого выполняется сравнение:

aj(m) º1 mod m ,

 

где φ(m) = Pm(a).

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

 

рассматриваются все числа

a = 2, m - 1 , которые удовлетворяют следующим

 

условиям:

 

1) взаимной простоты чисел a и m: (a, m) = 1;

 

2) aj(m)

º1mod m

или

aj(m) mod m =1;

 

3) для

"r =1, j(m) -1, являющегося делителем числа φ(m) (то есть

 

r | φ(m) ), выполняется условие a r

º/1mod m .

 

Замечание 2.1. Число 1 в качестве варианта первообразного элемента не рассматривается, так как при любой степени единицы и любом модуле будет выполняться условие 1j(m) º 1 mod m .

Существует частный случай переборного варианта поискапервообразных элементов - когда модуль m является простым числом p (в этом случае первообразные элементы называются примитивными

элементами). В качестве вариантов первообразных корней рассматриваются

 

все числа

a =2, p -1, которые удовлетворяют условиям:

 

1) взаимной простоты чисел a и m: (a, m) = 1;

 

2) так как функция Эйлера, вычисляемая от простого числа, равна

 

φ(p) = p – 1, то

a p-1 º1mod p

или

a p-1 mod p =1;

 

3) для

"r =1, p -1, являющегося делителем числа φ(p) = p-1 (то есть

 

r | p−1 ), выполняется условие

a r º/1mod p .

 

Теорема 2.1. Число a,

a =2, p -1,будет первообразным элементом по

 

простому модулю p, если выполняется условие:

 

p-1

a pi

 

º/1 mod p

 

для "i = 0, k - 1 ,

 

k -1

a

где число p – 1 представлено в виде канонического разложения p – 1 = Õpi i

i = 0

 

на k простых сомножителей, αi - натуральные числа.

 

Приводимые формулировки теорем раздела 2.3 взяты из [4, 11]. Пример 2.8. Проверить с помощью теоремы 2.1, что число a = 10

является первообразным элементом по простому модулю p = 19.

 

Число p – 1 = 19 – 1 = 18 можно разложить в канонический вид:

 

p − 1 = 18 = 2? 32.

 

(p – 1)/p1 = 18/2 = 9; (p – 1)/p2 = 18/3 = 6.

 

 

Проверим, что

 

p-1

a pi

 

 

º/1 mod p , i = 1, 2 .

 

Запишем промежуточные результаты вычислений (схема Горнера, раздел 1.7).

103 mod 19 = 1000 mod 19 = 12;

 

106 mod 19 = (103 mod 19)2 mod 19 = (12? 12) mod 19 = 144 mod 19 = 11;

 

109 mod 19 = (106 mod 19)? (103 mod 19) mod 19 = (11? 12) mod 19 =

 

= 132 mod 19 = 18.

 

Таким образом, 109 º/1 mod 19

и 106 º/1 mod 19 .

 

Ответ: число a = 10 является первообразным элементом по простому модулю p = 19.

 

 

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

 

Теорема 2.2. Число первообразных корней, принадлежащих диапазону

 

a = 2, p - 1, равно:

 

- φ(p-1), если модуль p - простое число;

 

- φ(φ(m)), если модуль m - составное число.

 

Пример 2.9. Найти первообразный элемент по модулю 54.

 

Взаимно простыми с числом 54 в диапазоне

1, 53

являются числа 1, 5,

 

7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53. Данный ряд можно вычислить с помощью алгоритма Евклида (раздел 1.1).

Используя свойство мультипликативности функции Эйлера, вычислим φ(54) по формуле Эйлера (раздел 1.6), когда число 54 раскладывается на кратные сомножители: 54 = 2? 33. Тогда φ(54) = (21−20)? (33−32) = 1? 18 = 18. Значение φ(φ(54)) = φ(18) = 6 задает число первообразных элементов по

модулю 54 (теорема 2.2).

 

В качестве переменной r, удовлетворяющей условиям

 

r | φ(m), могут быть числа 1, 2, 3, 6, 9.

"r = 1, j (m) - 1 и

 

Пусть a = 5; проверим - является ли оно первообразным элементом по модулю 54.

1) (5, 54) = 1.

 

2) Заранее вычислим элементы 53 mod 54, 56 mod 54 и 59 mod 54.

 

53 mod 54 = 125 mod 54 = 17;

 

56 mod 54 = (53)2 mod 54 = (53 mod 54)2 mod 54 = 172 mod 54 = 289 mod

 

54 = 19.

 

59 mod 54 = (53? 56) mod 54 = (53 mod 54)(56 mod 54) mod 54 = 17? 19 mod 54 =

 

= 323 mod 54 = 53.

 

aj(m) mod m

= 518 mod 54 = (59)2 mod 54 = 53? 53 mod 54 = 1.

 

В вычислениях была применена формула вычисления модуля от произведения нескольких чисел (раздел 1.4).

3) Проверим, что делители числа φ(m) - r = {1, 2, 3, 6, 9} - не являются показателями числа 5. Запишем сразу ответы без промежуточных вычислений, так как значения выражений были вычислены во втором пункте.

51 mod 54 = 5; 56 mod 54 = 19;

52 mod 54 = 25; 59 mod 54 = 53;

53 mod 54 = 17.

То есть для "r = {1, 2, 3, 6, 9} не выполняется сравнение: 5r º1 mod 54.

 

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

 

 

Теорема 2.3 определяет алгоритм получения всех первообразных элементов, если известен хотя бы один из этих элементов.

Теорема 2.3. Если a - первообразный элемент по (простому и составному) модулю m, то остальные первообразные элементы могут быть найдены как числа ak, удовлетворяющие условиям (ak mod m, φ(m)) = 1 и k ≥ 2, k - целое.

Пример 2.10. Пусть задано числовое поле GF(m) с порядком m = 17.

 

Проверим, являются ли числа 2 и 3 примитивными элементами, то есть можно ли с помощью этих чисел получить все остальные элементы поля

 

GF(17).

 

Для этого возведем числа 2 и 3 в степени

 

Вначале запишем степени двойки.

 

i = 1, m - 1.

 

21 mod 17 = 2;

22 mod 17 = 4;

23 mod 17 = 8;

24 mod 17 = 16;

25 mod 17 = 15;

26 mod 17 = 13;

27 mod 17 = 9;

28 mod 17 = 1;

 

29 mod 17 = 2;

210 mod 17 = 4;

211 mod 17 = 8;

212 mod 17 = 16;

213 mod 17 = 15;

214 mod 17 = 13;

215 mod 17 = 9;

216 mod 17 = 1;

При степени 9 начинается повтор (с периодом 8) результатов, полученных ранее, то есть с помощью элемента 2 нельзя получить все элементы GF(m), и 2 не является примитивным элементом поля GF(m).

Рассмотрим теперь степени тройки.

 

31 mod 17 = 3;

32 mod 17 = 9;

33 mod 17 = 10;

34 mod 17 = 13;

 

35 mod 17 = 5;

36 mod 17 = 15;

37 mod 17 = 11;

38 mod 17 = 16;

 

39 mod 17 = 14;

310 mod 17 = 8;

311 mod 17 = 7;

312 mod 17 = 4;

 

313 mod 17 = 12;

314 mod 17 = 2;

315 mod 17 = 6;

316 mod 17 = 1;

Здесь представлены все ненулевые элементы данного поля. То есть 3 является примитивным элементом поля GF(m), с помощью которого можно получить все остальные элементы поля.

 

 

Пример2.11. Пусть число a = 3 является первообразным элементом по простому модулю p = 7. Действительно, для a выполняются условия

 

a p-1 º1mod p

и (a, p) = 1, где φ(p) = p−1 = 7-1 = 6 (вычисление функции

 

Эйлера описано в разделе 1.6).

 

Общее число первообразных элементов можно найти из теоремы 2.2. Так как модуль p - простое число, то число элементов равно φ(p−1) = φ(6) = φ(2)? φ(3) = 1? 2 = 2.

 

Таблица 2.5. Поиск первообразного элемента

 

k	3k mod 7	Выполняется (3k mod 7, 6) = 1?
	9 mod 7 = 2	Нет, числа четные
	27 mod 7 = 6	Нет, числа четные
	81 mod 7 = 4	Нет, числа четные
	(4? 3) mod 7 = 5	Да, числа 5 и 6 взаимно простые

 

Получим на основе первообразного элемента a другие первообразные. Среди чисел k ≥ 2 найдем такие, при которых будет выполняться условие (ak, φ(p)) = 1 или (3k mod 7, 6) = 1 (теорема 2.3). Представим результаты в виде табл. 2.5. Для вычисления результатов 2-го столбца можно использовать схему Горнера (раздел 1.7), а для 3-го – алгоритм Евклида (раздел 1.1).

Таким образом, на основе первообразного элемента 3 можно получить другой первообразный элемент 35 mod 7 = 5.

 

Существуют частные алгоритмы вычисления первообразного элемента по простым и составным модулям, представленные в виде следующих теорем.

Теорема 2.4. Пусть p - простое число. Если a является первообразным элементом по составному модулю pα (α ≥ 1), то число a будет первообразным элементом и по модулю p.

Теорема 2.5. Пусть p - простое число. Если a - первообразный элемент по модулю p, то первообразным элементом также являются:

- число a по составному модулю pk, если выполняются условия

 

 

k ≥ 2 и

a ( p

-1)

pk -2

º/1 mod

p k ;

 

- одно из чисел a или a + p по модулю p2.

 

Теорема 2.6. Пусть p - простое число. Если a - первообразный элемент по модулю p2, то число a является первообразным элементом по модулю pk,

k ≥ 2.

 

Теорема 2.7. Любой нечетный первообразный элемент по модулю pk

 

является первообразным корнем и по модулю 2pk, где p - простое число и

 

k ≥ 1 - целое.

 

Теорема 2.8. Первообразные элементы по составному модулю m

 

существуют тогда и только тогда, когда:

 

1) m = pk,

 

2) m = 2pk,

 

где p - простое число и k ≥ 1 - целое.

 

Теорема 2.9(обобщающая). Первообразный элемент существует тогда и только тогда, когда модуль m Î{2, 4, pk, 2pk}, где p - простое число и k ≥ 1 - целое.

Дополнительные примеры для решения.

 

1. Найти значение P11(7).

 

2. Найти все первообразные элементы для модуля 17.

 

3. Найти первый первообразный элемент для модуля 56.

 

4. Найти все первообразные элементы для модуля 49.

 

Вопросы для самопроверки.

 

1. Что такое показатель числа a? Что такое первообразный элемент? В чем разница между этими двумя понятиями?

2. Каким образом можно проверить (из определения), что число a является первообразным элементом, если модуль – составное число?

3. Какие алгоритмы теории чисел используются при нахождении первообразного элемента?

4. Каким образом можно проверить (из определения), что число a является первообразным элементом, если модуль – простое число?

5. Каким образом можно проверить, что число a является первообразным элементом, если p - простой модуль и для числа p−1 задано каноническое разложение?

6. Как можно вычислить число первообразных элементов для заданного модуля m?

 

7. Как можно вычислить все первообразные элементы, если известен хотя бы один из них?

8. Какие существуют частные алгоритмы вычисления первообразного элемента по простому и составному модулям?

9. При каких значениях модуля m может существовать первообразный элемент?