рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

Модулярная арифметика (продолжение) Квадратичные вычеты Степенные вычеты - Лекция, раздел Математика, Материалы лекций Математические основы криптологии   Продолжим Исследовать Вычеты. Широкое Применение В К...

 

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

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

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 может существовать первообразный элемент?


 

– Конец работы –

Эта тема принадлежит разделу:

Материалы лекций Математические основы криптологии

В М Захаров.. Материалы лекций.. Математические основы криптологии..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Модулярная арифметика (продолжение) Квадратичные вычеты Степенные вычеты

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Лекция№1
    Криптология состоит из двух направлений: криптографии и криптоанализа.   Криптография – наука о способах преобразования (шифрования)

Асимметричное шифрование
    Алгоритм RSA (Revest, Shamir, Adelman) 1978г. e, n А, М В    

Алгоритм передачи секретного ключа по открытому каналу
В середине 70-х годов произошел настоящий прорыв в современной криптографии – появление асимметричных криптосистем, которые не требовали передачи секретного ключа между сторонами. Здесь от

Алгоритм Евклида
  Алгоритм Евклида дает правило вычисления наибольшего общего делителя   (НОД) 2-х натуральных чисел. (a,b)= d , где d – НОД НОК – наименьшее общее кратное

Алгоритм рае кнута
   

Свойства делимости целых чисел
  Два числа a и b называются взаимно простыми если их НОД = 1   (a1,a2,….,an)= НОД   (a1,a2) = d1   (a3,d1) = d2

Свойства делимости целых чисел
  Свойства приведены без доказательства.   1)Свойство дистрибутивности   Пусть заданны три натуральных числа a,b,

Простые числа
  1)- каноническое разложение &nb

Получение простых чисел
  По мере того как мы будем изучать курс «Математические основы криптологии» мы будем возвращаться к этой теме. Задача получение простых чисел во многом зависит от того как с

Проверка простоты чисел Мерсенна
  Числами Мерсенна называются числа вида М(p) = 2p - 1, pÎN.   Задача для чисел Мерсенна - поиск в ряду э

Sp-2 mod M(p) ≡ 0, т.е. остаток равен 0
  Поясним, каким образом задается ряд Sk. Члены последовательности  

Алгоритм Бухштаба
  Данный алгоритм приведен из книги Бухштаба А.А. "Теория чисел" [4]. Пусть задано натуральное нечетное число n, n ≥ 9, которое необходимо разложить на 2

Алгоритм Ферма
  Алгоритм Ферма похож на алгоритм Бухштаба и является эффективным, если у раскладываемого числа n есть делитель (который

Функция Эйлера
  Имеется целое, положительное число m. Оно может быть как составным, так и простым. Функцию Эйлера принято обозначать, практически во всех учебниках как:  

Мультипликативная функция
  Имеем два натуральных числа a и b, если они взаимно просты, то мультипликативная функция устанавливает число взаимно простых чисел, для произведение двух взаимно простых чисел по фо

Числовая функция
  Это функция устанавливающая целую часть от некоторого рационального числа [a] – обозначение   может быть как положительное, так и отрицательное число

Для возведение натуральных чисел по модулю в большие степени
    Функция Эйлера может быть использована для возведение больших чисел в большую степень по модулю.     Имеется целое число

Возведение натуральных чисел по модулю в большие степени по схеме Горнера
Пусть задано выражение вида   y = a x mod m , (1.1)   где a ÎN - основание степени,  

Сравнимость по модулю. Модулярная арифметика
    Понятие «модулярная арифметика» ввел немецкий ученый Гаусс.   Модульная арифметика аналогична обычной арифметике: она коммутативна, ассоциатив

Свойства операций сравнения
    В криптографии существуют шифры и по простому модулю и по составному модулю.   Нужно знать когда применять простой модуль, а когда состав

Доказательство теоремы Эйлера
  Пусть даны m и φ(m)=k   Имеем число a, причем (a,m)=1     Берем ряд натуральных чисел: a1

Элементы теории конечного поля простейшие алгебраические структуры
  Под алгебраической структурой будем понимать некоторое множество   S с одной или несколькими операциями на нем.   Пусть S х S обозначае

Кольца и поля
  Алгебраические структуры с двумя бинарными операциями - сложение и умножение.     Определение 1.7. Множество S называется кольцом, е

Характеристика поля
  Определение 1.12. Если в поле Fq все ненулевые элементы имеют аддитивный порядок k, то говорят, что поле Fq имеет характеристику k. Обозначение. р - простое число.

Вычисление обратных элементов
  В арифметике действительных чисел просто вычислить обратную величину a−1 для ненулевого a: a-1 = 1/a или a? a-1 = 1.

Многочлены над конечным полем
  Onределенuе 1.13. Многочленом (относительно х) над полем GF(p)   m

Для любого простого р и nÎN существует хотя бы один неприводимый над полем GF(p) многочлен степени n [9]
Любой неприводимый над полем GF(p) многочлен степени п делит     многочлен x pm - x   (также и мног

Алrебраические структуры над множеством многочленов
  Кольцо многочленов над полем GF(p)   Определение 1.17. Кольцо, образованное многочленами над полем GF(p), называется кольцом многочлен

Расширение полей
  Рассмотрим, какова связь полей GF(p) и GF( p n ).   Пусть F - поле. Подмножество К поля Р, которое само является полем относительно операций поля Р, на

Системы уравнений сравнений
  Общий вид:   x ≡ c1 mod m1   x ≡ c2 mod m2

Pound; b£ n-1
  Если для каждого простого делителя p числа n-1 справедливы следующие утверждения:     (1) bn-1≡ 1(mod n),  

Числа Кармайкла
  Может ли составное нечетное число n быть псевдопростым по всем взаимно-простым с ним основаниям b? Забегая вперед, скачем, что «да».     Заметим

Процедура получения устойчивых простых чисел
  1. Генерируются простые числа s,t   2. Получаем простое число r такое что, (r-1) делит t без остатка: r-1|t На основе этих двух операций получаем про

М-последовательности. ГПСЧ типа ЛРС1
  Опр ед ел ени е. Последовательностью над полем   GF ( p)   будем   назы

M - последовательности на основе произведения многочленов
Рассмотрим способ построения схемы линейного регистра сдвига на основе характеристического многочлена, задаваемого как произведение   многочленов, при &nbs

Произведения многочленов
  Рассмотрим следующие свойства ЛРП, порождаемой схемой ГПСП,   изображенной на рис. 2.1, при a0 =1.  

ЛЕКЦИЧ 16
  Способы представления элементов поля GF(2n)   Для представления элементов в полях Галуа вида GF(2n) существуют ра

Алгоритм получения элементов поля GF(2n) в стандартном базисе
  Для построения элементов поля GF(2n) в стандартном базисе существует следующий алгоритм, использующий сдвиговыерегистры. На входе: поле GF(2n

Заданными в стандартном базисе
   

Алгоритм асимметричного шифрования RSA
  Алгоритм RSA предложили в 1978 г. 3 автора: Райвест (Rivest), Шамир (Shamir) и Адлеман (Adleman). RSA является алгоритмом с открытым ключом, работающим в режимах шифрования данных и

Математическая модель алгоритма RIJNDAEL
  Байты можно рассматривать как элементы конечного поля GF(28) -   многочлены степени не более 7   а7х7 + а6х

Раунд преобразования алгоритма RIJNDAEL
  RIJNDAEL выполняет серию однотипных раундов преобразования шифруемого блока. Шифруемый блок и его промежуточные состояния в ходе преобразования представляются в виде квадратной матр

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги