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

–система лишків за простим модулем p створює скінчене поле. Таке поле має p елементів. Позначається FG(p) і носить назву поле Галуа.

– система конгруенцій ai x ≡ bi (mod mi ), i = 1,k за умови ( i = 1,k (ai ,mi ) = 1) завжди має єдиний розв’язок. Якщо умова не виконується, необхідно проводити поступовий аналіз конгруенцій системи на наявність розв’язку.

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

–Використовуючи властивості конгруенцій спростити конгруенцію n-го степеня з одним невідомим;

–Застосувати схему Горнера для знаходження розв’язків конгруенції n-го степеня з одним невідомим

–Знаходити обернений елемент до числа a за модулем m у випадку, коли (a ,m) = 1 з використанням неперервних дробів;

–Розв’язувати конгруенції першого степеня

1.за властивостями,

2.за допомогою неперервних дробів,

3.у випадку, коли a = 2k

–Розв’язувати системи конгруенцій першого порядку.

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

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

2.Дати означення конгруенції першого степеня з одним невідомим. Яка структура є розв’язком конгруенції.

3.Дана конгруенція ax ≡ b(mod m). З яких умов вона має єдиний розв’язок, декілька розв’язків, немає розв’язків?

4.Які конгруенції називаються еквівалентними?

5.Які ви знаєте методи розв’язання конгруенцій першого степеня з одним невідомим?

6.Чи існує єдиний обернений елемент за множенням до кожного елементу найменшої додатної системи лишків за простим модулем? На базі якої теореми можна знайти відповідь на це питання?

7.Яку алгебраїчну структуру створює повна система лишків за простим модулем? Чиїм ім’ям названа ця структура?

8.Дайте означення розв’язку системи конгруенцій першого порядку з одним невідомим.

9.Сформулюйте Китайську теорему про залишки.

10.В якому разі система конгруенцій розпадається на низку систем?

11.В якому разі система з двох конгруенцій не має розв’язку?

51

ТЕМА №5 КОНГРУЕНЦІЇ 2-ГО СТЕПЕНЯ .

Питання 1. Загальні положення

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

Питання 3. Символ Лежандра Питання 4 Символ Якобі

Ключові терміни

Квадратична конгруенція, критерій Ейлера, квадратичний лишок модуля, квадратичний нелишок модуля, символ Лежандра, властивості символу Лежандра, закон взаємності двох простих непарних чисел, символ Якобі

Теорема 1. Конгруенцію (1) завжди можна звести до конгруенції виду

Дійсно, за властивостями конгруенцій, які відповідають зміні модуля конгруенції, можемо помножити усі складові конгруенції на множник 4a :

4a 2 x 2 + 4abx + 4ac ≡ 0(mod 4am)

Виділимо ліворуч повний квадрат:

(2ax + b)2 − b2 + 4ac ≡ 0(mod 4am) (2ax + b)2 ≡ b2 − 4ac(mod 4am)

Позначимо 2ax + b = y, b 2 − 4ac = C , отримали вираз (2).

Якщо конгруенція (2) має розв’язок y ≡ y1 (mod 4am), то можна знайти розв’язок

x ≡ y − b (mod m) за умови, що 2a | (y − b). Тобто за виконання додаткової умови розв’язок

2a

(2) є розв’язком (1). Якщо (2) не має розв’язку, то (1) теж немає розв’язку.

де p - просте число.

Розглянемо розв’язання (2) у випадках:

1.Модуль p > 2 - просте непарне число в першій степені.

2.Модуль pα - просте непарне число в степені α > 1.

3.Модуль p = 2

52

Питання 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