Файл: Теорія чисел в криптографії.pdf

Питання 2 Квадратична конгруенція за простим непарним модулем p

Якщо a ≡ 0(mod p), то (3) має один розв’язок.

Теорема 2. Критерій Ейлера.

Якщо a в конгруенції (3) не ділиться на p , тобто (a, p) = 1, то відповідна конгруенція має 2 різних розв’язки, якщо

p−1

a 2 ≡ 1(mod p),

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

p−1

a 2 ≡ −1(mod p)

Доведення: Розглядаємо конгруенцію (3) за прости непарним модулем p .

Оскільки (a, p) = 1, то за теоремою Ферма a p−1 − 1 ≡ 0(mod p). Оскільки в нашому випадку p − 1 завжди парне, то вірним буде подання:

Якщо добуток ділиться на просте число, значить обов’язково хоча б один з

за властивостями можливе піднесення до цілого степеня. Піднесемо конгруенцію до

степеня p −1 , отримаємо: 2

p−1

xp−1 ≡ a 2 (mod p).

За теоремою Ферма з урахуванням (x, p) = 1 маємо x p −1 ≡ 1(mod p), отже, виходячи з

існування розв’язку x конгруенції (3), отримали:

p−1

a 2 ≡ 1(mod p).

Висновок: якщо (3) має розв’ язки, то для неї виконується конгруенція

p−1

a 2 ≡ 1(mod p). В цьому випадку конгруенція має рівно 2 класи коренів, створених на лишках з повної системи абсолютно найменших лишків x та − x (або x та p − x з

повної системи найменших лишків) модуля p , оскільки (− x)2 = x 2 ≡ a(mod p)

Очевидно, що x та − x різні, тобто не конгруентні між собою, інакше б виконувалася конгруенція 2x ≡ 0(mod p), тобто x ділився б на p , а це протиріччя до

вихідної конгруенції. Більше коренів бути не може за теоремою про кількість коренів конгруенції з простим модулем.

53

яких конгруенція (3) не має розв’ язку.

Тепер прояснимо питання кількості чисел a , для яких конгруенція (3) буде мати розв’язки. Очевидно, що a належить до класів, створених на повних системах абсолютно найменших або найменших лишків без нуля. Для простого модуля p таких класів p −1.

Але вище було відмічено, що x та − x (або x та p − x ) дають однакові квадрати, тобто (− x)2 = x 2 ≡ a(mod p). Отже, будемо мати чисел, для яких конгруенція (3) має розв’язок,

рівно половину з кількості елементів у повній системі лишків без нуля, тобто рівно p −1 2

лишки з повної системи лишків відповідають (3), а інша половина – ні. Нагадаємо, що p -

непарне, отже p −1 - ціле число. 2

Приклад.

Розглянемо повну систему абсолютно найменших лишків для чисел 5 та 7 і з’ясуємо, для яких лишків конгруенція (3) буде мати розв’язок, а для яких ні. В дужках будемо подавати відповідні лишки з повної системи найменших лишків.

p = 5, повна система абсолютно найменших лишків без нуля: − 2,−1,1,2 (1,2,3,4) .

Відповідні квадрати: (± 2)2 = 4 ≡ −1(mod 5), (± 1)2 = 1 ≡ 1(mod 5)

[(1)2 = 1 ≡ 1(mod 5), (2)2 = 4 ≡ 4(mod 5), ] (3)2 = 9 ≡ 4(mod 5), (4)2 = 16 ≡ 1(mod 5) .

Отже, якщо в (3) модуль дорівнює 5, а права частина a ≡ ±1(mod 5) (a ≡ 1,4(mod 5)), то конгруенція розв’язок має. Для a ≡ ±2(mod 5) (a ≡ 2,3(mod 5)) розв’язків немає. Тобто для

конгруенція розв’язок має. Для a ≡ −1,−2,3(mod 7) розв’язків немає. Тобто для 7 − 1 = 3 2

лишків розв’язок є і для 3-х – немає.

Висновок. Серед повної системи лишків для простого непарного модуля p p −1 2

елементів відповідає конгруенції (3) і p −1 елементів не відповідає. 2

Для таких елементів, що відповідають, виконується конгруенція

p−1

a 2 ≡ 1(mod p)

Для інших – конгруенція

p−1

a 2 ≡ −1(mod p)

54

Означення: Значення a , для якого конгруенція (3) має розв’язок, називається квадратичний лишок модуля p . Якщо для деякого a конгруенція (3) розв’язку немає, то

a носить назву квадратичний нелишок модуля p .

Наслідок з критерію Ейлера: У повній системі лишків простого непарного

модуля p кількість лишків завжди дорівнює кількості нелишків, а саме p −1 . 2

Теорема 3. (Теорема Ейлера).

Добуток двох лишків або двох нелишків за модулем p є лишок. Добуток лишку на нелишок за модулем p є нелишок.

Доведення: З критерію Ейлера:

Критерій Ейлера дає одразу і формулу обчислення символу Лежандра, але для великих p,a обчислення є досить складними. Наведемо властивості символу Лежандра,

які значно спрощують процес обчислення даного показника і, відповідно, визначення наявності розв’язків (1).

Властивості символу Лежандра.

55

Якщо взяти до уваги, що для усіх простих чисел 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