Застосування теорії чисел в криптографії, страница 13

 повна система абсолютно найменших лишків без нуля:  . Відповідні квадрати:  (  )

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

Висновок. Серед повної системи лишків для простого непарного модуля   елементів відповідає конгруенції (3) і  елементів не відповідає.

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

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

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

Наслідок з критерію Ейлера: У повній системі лишків простого непарного модуля  кількість лишків завжди дорівнює кількості нелишків, а саме .

Теорема 3. (Теорема Ейлера). Добуток двох лишків або двох нелишків за модулем  є лишок. Добуток лишку на нелишок за модулем  є нелишок.

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

,

„+” буде за умови, що знаки біля 1 однакові, „-” – різні.

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

Означення: Розглянемо конгруенцію                                         (1)

Якщо  простий непарний модуль і , символом Лежандра називається величина

, якщо  - квадратичний лишок за модулем  і , якщо  - квадратичний нелишок за модулем . Тобто, враховуючи критерій Ейлера,

                                                                                                   (2)

Критерій Ейлера дає одразу і формулу обчислення символу Лежандра, але для великих  обчислення є досить складними. Наведемо властивості символу Лежандра, які значно спрощують процес обчислення даного показника і, відповідно, визначення наявності розв’язків (1).

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

1.  Якщо

2.   як наслідок:

3. 

4.  .

Якщо взяти до уваги, що для усіх простих чисел  величина  парна, а для , або  - непарна, то дану властивість можна прокоментувати так: для всіх модулів типу  число -1 є квадратичний лишок, а для модулів типу , або  - квадратичний нелишок.

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

Властивість 2 зводить обчислення символу Лежандра за прости непарним модулем  до обчислення символів  якщо  - просте непарне число.

5. 

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

Якщо розглянути степінь  для цих видів, то будемо мати:

:  - парні степені

:  - непарні степені

Тобто властивість 5. можна подати так:

Для чисел  символ Лежандра , 2 є лишком за модулем

Для чисел  символ Лежандра , 2 є нелишком за модулем

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

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

Число , як і число  подається за модулем 4 або як , або . В першому разі  буде парним степенем, у другому – непарним. Добуток степенів  буде парним, якщо хоч один із множників парний.

Отже, якщо хоча б одне з чисел  та  має вигляд , то             .

Якщо обидва числа мають вигляд , то                              

Приклади:

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

Розв’язання

Спочатку спростимо конгруенцію: . Розкладемо

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

1) , тобто ,

2) , , отже 2 є нелишком по модулю 3,

3)

4)

Висновок: Конгруенція  розв’язків немає.

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

Розв’язання

Спочатку спростимо конгруенцію: . Розкладемо

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

1) , тобто

2)

3)

Висновок: Конгруенція  має 2 розв’язки.

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

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

Означення:

Символом Якобі називається показник

,

де  - є звичайні символи Лежандра.

Нехай  - розкладання числа  на прості множники. Тоді за властивостями символу Лежандра

, тобто

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

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

Розв’язання: