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

Але будь-яке квадратичне відрахування а задовольняє при деякому х порівнянню a ºx2 (mod p) і, отже, задовольняє також одержуваному з нього зведенням у ступінь (p – 1)/2 порівняння a(p -1)/2 ºxp-1 º1(mod p) (знову теорема Ферма). При цьому, квадратичними відрахуваннями і вичерпуються всі рішення порівняння a(p -1)/2 º1(mod p), тому що, будучи порівнянням ступеня (p – 1)/2, воно не може мати більш ніж (p – 1)/2 рішень. Це означає, що квадратичні невідрахування задовольняють порівнянню a(p -1)/2 º-1(mod p)

Перелічимо далі найпростіші властивості символу Лежандра.

Властивість 3.8.1. Якщо a ºb (mod p ), то L(a, p) = L(b, p). [11]

Ця властивість випливає з того, що числа одного класу по модулю р будуть всі одночасно квадратичними відрахуваннями або квадратичними невідрахуваннями.

Властивість 3.8.2. L(1, p)=1.

Доказ очевидний, адже одиниця є квадратом.

Властивість 3.8.3.

Доказ цієї властивості випливає з критерію Ейлера при а = -1. Через те що ( p – 1)/2 – парне, якщо р виду 4 n +1, і непарне, якщо р виду 4 n +3, то число -1 є квадратичним відрахуванням по модулю р тоді і тільки тоді, коли р виду 4 n +1.

Властивість 3.8.4. L(ab, p) = L(a, p)L(b, p) [11]

Дійсно,

Властивість 3.8.4., поширюється на будь-яке кінцеве число співмножників у чисельнику символу Лежандра, взаємно простих з р. Крім того, з нього випливає

Властивість 3.8.5. , тобто в першому числі символу Лежандра можна відкинути будь-який квадратний множник. [11] Дійсно:

, тому що незалежно від того чи буде  або , .

Для визначення символу Лежандра можна скористатися наступним алгоритмом:

1.  Якщо а = 1, то L(a, p) = 1

2.  Якщо а парне, то

3.  Якщо а непарне L(a, p), то

1.3.9.  Символ Якобі

Символ Якобі, J(a, n), являє собою узагальнення символу Лежандра на складені модулі, він визначається для будь-якого цілого a і будь-якого непарного цілого n. [1] Функція зручна при перевірці на простоту. Символ Якобі є функцією на множині отриманих відрахувань дільників n і може бути обчислений по різних формулах. Ось один із способів:

Визначення 3.9.1: J(a, n) визначений, тільки якщо n непарне.

Визначення 3.9.2: J(0, n) = 0.

Визначення 3.9.3: Якщо n – просте число, то символ Якобі J(a, n) = 0, якщо а поділяється на n.

Визначення 3.9.4: Якщо n – просте число, то символ Якобі J(a, n) = 1, якщо а – квадратичне відрахування по модулю n.

Визначення 3.9.5: Якщо n – просте число, то символ Якобі J(a, n) = -1, якщо а не є квадратичним відрахуванням по модулю n.

Визначення 3.9.6: Якщо n – складене число, то символ Якобі J(a, n) = J(a, p1)× ... × J(a, pm), де p1, ... , pm – це розкладання n на прості співмножники.

Наступний алгоритм рекурсивно розраховує символ Якобі:

Правило 3.9.1: J(1, n) = 1

Правило 3.9.2: J(ab, n) = J(a, n) J(b, n)

Правило 3.9.3: J(2, n) =, якщо (n2-1)/8 непарне, і -1 у противному випадку

Правило 3.9.4: J(a, n)= J((a mod n), n)

Правило 3.9.5: J(a, b1b2) = J(a, b1) J(a, b2)

Правило 3.9.6: Якщо найбільший загальний дільник a і b = 1, а також a і b непарні:

Правило 3.9.6а: J(a, b)= J(b, а), якщо (a – 1)(b – l)/4 парне

Правило 3.9.6b: J(a, b)= –J(b, а), якщо (a – 1)(b – 1)/4 непарне

Ось алгоритм мовою C++ [6]:

long Jacobi(long a,long p)

{

long g;

if(a>=p)a=a%p;

if(a==0)return 0;

if(a==1)return 1;

if(a<0)if((p-1)/2 % 2 == 0)return Jacobi(-a,p);

else return -Jacobi(-a,p);

if (a % 2 == 0)

if (((p*p -1)/8) % 2 == 0)

return +Jacobi(a/2,p);

else

return -Jacobi(a/2,p);

g = NOD(a,p);

if(g==a) return 0;

else if(g!=1)return Jacobi(g,p)*Jacobi(a/g,p);

else if(((a-1)*(p-1)/4)%2==0)return +Jacobi(p,a);

else return -Jacobi(p,a);

}

Якщо заздалегідь відомо, що n – просте число, замість використання попереднього алгоритму просто обчисліть a((n – 1)/2) mod n, у цьому випадку J(a, n) еквівалентний символу Лежандра L(a, n).

Символ Якобі не можна використовувати для визначення того, чи є а квадратичним відрахуванням по модулю. [1]

1.3.10.  Генератори

Визначення 3.10.1. Якщо p – просте число, і g менше, ніж p, то g називається генератором по модулю p, якщо для кожного числа b від 1 до p – 1 існує деяке число a, що ga º b (mod p). [1]

Іншими словами, g є примітивом стосовно p. Наприклад, якщо р = 11, то 2 – це генератор по модулю 11:

210 = 1024º1 (mod 11)

21 = 2 º 2 (mod 11)

28 = 256 º 3 (mod 11)

22 = 4 º 4(mod 11)

24 =16 º 5(mod 11)

29 = 512 º 6 (mod 11)

27 = 128 º 1 (mod 11)

23 = 8 º 8(mod 11)

26 = 64 º 9(mod 11)

25 = 32 º 10 (mod 11)

Кожне число від 1 до 10 може бути представлено як 2a(mod p). Для р=11 генераторами є 2, 6, 7 і 8. Інші числа не є генераторами. Наприклад, генератором не є число 3, тому що не існує рішення для

3a º 2(mod 11)

У загальному випадку перевірити, чи є дане число генератором, нелегко. Однак задача спрощується, якщо відомо розкладання на множники для p – 1. Нехай q1, q2, ... , qn – це різні прості множники p – 1. Щоб перевірити, чи є число g генератором по модулю p, обчисліть

для всіх значень q=q1, q2,..., qn.

Якщо це число дорівнює 1 для деякого q, то g не є генератором. Якщо для всіх значень q розраховане значення не дорівнює 1, то g – генератор. [1]

Приклад 3.10.1. Нехай p = 11. Прості множники р – 1 = 10 – це 2 і 5. Для перевірки того, чи є число 2 генератором, обчислимо:

Жодна з відповідей не дорівнює 1, тому 2 – це генератор.

Приклад 3.10.2. Перевіримо, є чи генератором число 3:

Отже, 3 – це не генератор.

1.3.11.  Розкладання на множники

Розкласти число на множники – значить знайти його прості співмножники.

10 = 2×5

60 = 2×2×3×5

252601=41×61×101

2113 – 1 =3391×23279×65993×1868569×1066818132868207

Розкладання на множники є однією з найдавніших проблем теорії чисел. Цей процес нескладний, але вимагає часу. Це поки залишається так, але ряд зрушень у цьому мистецтві усе-таки відбувся.

Приведемо перелік найбільш вдалих алгоритмів факторизації: [1]