Другие предметы \ Основы теории криптографии и криптоанализа

Учбово-методичний посібник для виконання лабораторних робіт з дисципліни „Основи теорії криптографії і криптоаналізу”, страница 16

Оскільки всі числа з даного класу еквівалентності виходять з одного числа даного класу додатком числа, кратного m, то всі числа з даного класу мають з модулем m однаковий найбільший загальний дільник. По деяких розуміннях, підвищений інтерес представляють ті відрахування, що мають з модулем m найбільший загальний дільник, який дорівнює одиниці, тобто відрахування, що взаємно прості з модулем.

1.3.6.  Приведена система відрахувань. Функція Ейлера. Теорема Ейлера.

Визначення 3.6.1. Приведеною системою відрахувань по модулю m називається сукупність усіх відрахувань з повної системи, взаємно простих з модулем m. [11]

Приведену систему звичайно вибирають з найменших додатних відрахувань.

Наприклад, для числа 12 найменшою додатною повною системою відрахувань по модулю 12 буде множина {1,2,3,4,5,6,7,8,9,10,11}, а приведеною системою відрахувань по модулю 12 буде множина: {1,5,7,11}.

Очевидно, що якщо число m – просте, то приведена система відрахувань по модулю m, буде збігатися з найменшою додатною повною системою відрахувань і складатися з m – 1 елемента.

Функція Ейлера – це кількість елементів у приведеній системі відрахувань по модулю m (позначення: j(m)). Іншими словами, j(m) – це кількість позитивних цілих чисел, менших m і взаємно простих з m (для будь-якого m, більшого 1).

Лема 3.6.1. 1) Будь-які j(m) чисел, попарно не порівнянні по модулю m і взаємно прості з модулем, утворять приведену систему відрахувань по модулю m.

2) Якщо (a,m) = 1 і x пробігає приведену систему відрахувань по модулю m, то ах так само пробігає приведену систему відрахувань по модулю m. [11]

Доказ. Твердження 1) – очевидно. Доведемо твердження 2) Числа ах попарно непорівнянні (це доводиться так само, як у лемі 1 цього пункту), їх рівно j(m) штук. Ясно також, що усі вони взаємно прості з модулем, тому що (a,m)=1, (x,m)=1 Þ(ax,m)=1 . Виходить, числа ах утворять приведену систему відрахувань.

Теорема Ейлера. Нехай m>1 , (a,m)=1 , j(m) – функція Ейлера. Тоді:

aj (m) º1(mod m). [11]

Доказ. Нехай х пробігає приведену систему відрахувань по mod m :

x=r1, r2,..., rc

де c= j(m) їхнє число, r1, r2,..., rc – найменші додатні відрахування по mod m . Отже, найменші додатні відрахування, що відповідають числам ax суть відповідно:

r1, r2,..., rc

– теж пробігають приведену систему відрахувань, але в іншому порядку (див. лему 1). Значить:

a× r1 ºrj(mod m)
a×r2 ºrj2 (mod m)
...
a×rc ºrjc (mod m)

Перемножимо ці ci штук порівнянь. Вийде:

ac r1r2...rc ºrj1rj2 ...rjc (mod m)

Тому що r1r2 ...rc=r1r2...rc¹ 0 і взаємно прості з модулем m, то, поділивши останнє порівняння на r1r2 ...rc, одержимо aj(m) º1(mod m).

Мала теорема Ферма Нехай р – просте число, р не поділяє a . Тоді:

ap-1º1(mod p). [11]

Доказ Покладемо в умові теореми Ейлера m=p , тоді j(m)=p-1. Одержуємо
a p – 1 º 1 (mod p).

Необхідно відзначити важливість умови взаємної простоти модуля і числа a у формулюваннях теорем Ейлера і Ферма. Простий приклад: порівняння 62 º 1(mod 3) очевидно не виконується. Однак можна легко підправити формулювання теореми Ферма, щоб зняти обмеження взаємної простоти.

Наслідок. Без всяких обмежень на a ÎZ, ap ºa(mod p). [11]

Доказ. Помножимо обох частин порівняння ap-1 º1(mod p) на a . Ясно, що вийде порівняння, справедливе і при a , кратному р.

1.3.7.  Квадратичні відрахування.

Визначення 3.7.1. Якщо порівняння x2 ºa (mod p) має рішення, то число а називається квадратичним відрахуванням по модулю р. У противному випадку, число а називається квадратичним невідрахуванням по модулю р. [1]

Якщо ж в якості модуля ми беремо складене число n, то для того щоб а було квадратичним відрахуванням по n, воно повинне бути квадратичним відрахуванням по модулю всіх простих співмножників n.

Приклад 3.7.1.: Якщо р = 7, квадратичними відрахуваннями є числа 1, 2, і 4:

12 = 1 = 1 (mod 7)

22 = 4 = 4 (mod 7)

32 = 9 = 2 (mod 7)

42 =16 = 2(mod 7)

52 = 25 = 4 (mod 7)

62 = 36 = 1 (mod 7)

Помітьте, що кожне квадратичне відрахування двічі з'являється в цьому списку.

Це пояснюється наступним:

Якщо а – квадратичне відрахування по модулю р , то порівняння x2 ºa (mod p) має в точності два рішення. Дійсно, якщо а – квадратичне відрахування по модулю р , то в порівняння x2 ºa (mod p ) є хоча б одне рішення x ºx1 (mod p ). Тоді x2 = -x1 – теж рішення, адже (-x1)2 =x12 . Ці два рішення не порівнянні по модулю р >2 , тому що з x1 º-x1 (mod p ) випливає 2 x1 º0(mod p ), тобто (оскільки р ¹ 2) x1 º0(mod p), що неможливо, тому що а ¹0.

Оскільки порівняння x2 ºa (mod p ) є порівняння другого ступеня по простому модулю, то більше двох рішень воно мати не може.

Приведена (тобто без нуля) система відрахувань

по модулю р складається з ( p – 1)/2 квадратичних відрахувань, порівнянних з числами 12 ,22 ,…,((p–1)/2)2,і (p – 1)/2 квадратичних невідрахувань, тобто відрахувань і невідрахувань нарівно.

Дійсно, квадратичні відрахування порівнянні з квадратами чисел

,

а саме, з числами 12 ,22 ,…,((p–1)/2)2,при цьому всі ці квадрати різні по модулю р, тому що з k2 ºl2 (mod p), де 0< k < l £(p – 1)/2, випливає, що порівняння x2 ºk2 (mod p) має чотири рішення: l, –l, k, –k, що неможливо [6]

1.3.8.  Символ Лежандра.

Визначення 3.8.1. Нехай а – будь-яке ціле число, p – просте число більше 2. Тоді символ Лежандра визначається як:

, якщо а кратне р.

, якщо а – квадратичне відрахування по модулю р

, якщо а – квадратичне невідрахування по модулю р

Теорема. (Критерій Ейлера) Нехай а не кратне р. Тоді:

a(p -1)/2 ºL(a, p)(mod p). [11]

Доказ. Якщо a кратне p, тоді a(p -1)/2 º0(mod p), тобто L(a, p)=0.

Якщо a не кратне p, тоді по теоремі Ферма, a p -1 º1(mod p ) тобто

У лівій частині останнього порівняння в точності один співмножник поділяється на р, адже обидва співмножники на р поділятися не можуть, інакше їхня різниця, що дорівнює двом, поділялася б на р >2. Отже, має місце одне і тільки одне з порівнянь:

Скачать файл