Материал: Теорія чисел в криптографії

Якщо взяти до уваги, що для усіх простих чисел p = 4k + 1 величина p -1 парна, а 2

для p = 4k + 3 , або p = 4k − 1 - непарна, то дану властивість можна прокоментувати так: для всіх модулів типу p = 4k + 1 число -1 є квадратичний лишок, а для модулів типу

p = 4k + 3 , або p = 4k − 1 - квадратичний нелишок.

Наприклад -1 за модулем 29 є квадратичний лишок, бо 29 = 7 × 4 +1 , а для модуля 3 квадратичний нелишок, бо 3 = 4 ×1 -1

p= 8k ± 3

6.Закон взаємності двох простих непарних чисел:

парним, якщо хоч один із множників парний.

56

Приклади:

1.Дослідити, чи має розв’ язки конгруенція x 2 º 438(mod 593)

Розв’язання

Спочатку спростимо конгруенцію: x 2 º -155(mod 593). Розкладемо a = -155 = (-1)×5 ×31

Для визначення наявності розв’язків обчислимо символ Лежанндра

Висновок: Конгруенція x 2 º 438(mod 593) розв’язків немає.

2.Дослідити, чи має розв’ язки конгруенція x 2 º 2021(mod1231)

Розв’язання

Спочатку спростимо конгруенцію: x 2 º 792(mod1231). Розкладемо

a = 792 = 8 × 9 ×11 = 23 × 32 ×11

Для визначення наявності розв’язків обчислимо символ Лежанндра

Висновок: Конгруенція x 2 º 792(mod1231) має 2 розв’язки.

57

Питання 4. Символ Якобі.

Якобі узагальнив символ Лежандра на випадок, коли модуль конгруенції P є

Теорема 1.

Для символу Якобі вірні всі властивості 1-6 символу Лежандра.

853

Приклад. Обчислити: 1409

Висновки Після вивчення теми 5 ви повинні знати такі факти:

–Квадратична конгруенція має такий загальний вигляд:

ax 2 + bx + c º 0(mod m);

– Зведена квадратична конгруенція має вигляд: y 2 º C(mod P) ;

– Якщо (C, P) = P , то квадратична конгруенція y 2 º C(mod P) завжди має єдиний розв’язок y ≡ 0(mod P)

58

– Якщо модуль є складеним числом m = p1α1 p2α2 ...pk α k , то розв’язання квадратичної конгруенції зводиться до розв’язання системи конгруенцій виду:

особливості розв’язання:

квадратична конгруенція, в якій не ділиться на p , тобто (C , p) = 1, має 2 різних

розв’язки, якщо

p−1

C 2 ≡ 1(mod p),

або зовсім немає розв’язків, якщо

p−1

C 2 ≡ −1(mod p)

Причому розв’язками є класи лишків з повної найменшої системи лишків або з абсолютно найменшої системи лишків.

–Якщо конгруенція y 2 ≡ C(mod p) має розв’язки, то C носить назву

лишка за модулем p , якщо розв’язків немає, то C - нелишок за модулем p .

–Показником наявності розв’язків у квадратичної конгруенції

Лежандра можна використовуючи 6 властивостей.

– Узагальненням символу Лежандра є символ Якобі. Якщо розглядається конгруенція y 2 ≡ a(mod P), де P = p1 p2 ... pk , то символом Якобі називається показник

Після вивчення теми 4 ви повинні вміти:

– Визначати, чи має квадратична конгруенція y 2 ≡ a(mod m) нульовий розв’язок.

–Спираючись на властивості символу Лежандра, обчислити його для конгруенції

y 2 ≡ a(mod p), ( p - просте число) визначивши тим самим чи є лишком за модулем

pчисло a .

–В разі складного модуля квадратичної конгруенції y 2 ≡ a(mod m) обчислювати для неї символ Якобі.

Контрольні питання до теми №4.

1.Дайте означення квадратичної конгруенції за довільним модулем.

2.Укажіть в якому випадку квадратична конгруенція має єдиний нульовий розв’язок.

3.Назвіть спосіб розв’язання квадратичної конгруенції за складеним модулем.

4.Назвіть критерій Ейлера про наявність розв’язків конгруенції x2 ≡ a(mod p)

59

5.Дайте означення лишка і нелишка за модулем p

6.Назвіть слідство з критерію Ейлера про наявність розв’язку квадратичної конгруенції.

7.Назвіть теорему Ейлера про взаємодію лишків і нелишків по певному простому модулю.

8.Назовіть 6 властивостей символу Лежандра.

9.За допомогою символу Лежандра з’ясуйте, чи є лишком 139 за модулем 5, якщо так, знайдіть розв’язок квадратичної конгруенції x2 ≡ 139(mod 5)

10.За допомогою символу Лежандра з’ясуйте, чи є лишком 98 за модулем 5, якщо так, знайдіть розв’язок квадратичної конгруенції x2 ≡ 98(mod 5)

11.Які лишки з повної системи найменших додатних лишків за модулем 7

a = {0,1,2,3,4,5,6} є лишками для квадратичної конгруенції x2 ≡ a(mod 7)? Скільки таких лишків?

12.Дайте означення символу Якобі за складеним модулем P = p1 p2 ... pk

13.Обчисліть символ Якобі для 393 за модулем 455.

60