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

2.  - поліном нульового степеня. Якщо не ділиться на , то дана конгруенція не має розв’язків, бо вона зводиться до невірної конгруенції : .

Приклад. Знайти конгруенцію степені не вище 4, еквівалентну даній:

Розв’язання: Поділимо  на . Для полегшення ділення використаємо наслідок з малої теореми Ферма ().

Наслідок з теореми Ферма: Якщо .

Дійсно, нехай  За теоремою Ферма . Піднесемо цю конгруенцію до степені : . Помножимо отриману конгруенцію і конгруенцію , дістанемо:

, або

За допомогою цього слідства можна зменшити степені вихідного полінома, взявши замість даних степенів їх залишки за модулем 4:

Отримаємо:

, або ,

або, замінивши лишок -2 на лишок 3(mod5), отримаємо: , і остаточно:

Очевидні розв'язки останньої конгруенції  будуть також і розв'язками вихідної конгруенції.

Теорема 3. Якщо  — деякий розв'язок конгруенції го степеня , то має місце тотожна конгруенція:

                                                                                                 (2)

де  — поліном -го степеня. Старший коефіцієнт полінома  збігається з старшим коефіцієнтом вихідного полінома .

Доведення.

Поділимо на  і частку позначимо через , остачу – через :

.

За теоремою Безу , але оскільки  — розв'язок конгруенції, то

, отже справедливою буде конгруенція:

.

За таких умов кажуть, що  ділиться на  за модулем . Очевидно, що й навпаки: якщо  ділиться на  з нульовим залишком за модулем  (тобто ), то, використовуючи теорему Безу, можна стверджувати, що , звідки витікає, що  — розв'язок конгруенції.

Висновок. Конгруенція (1) має за корінь  тоді і тільки тоді, коли  ділить  за модулем .

Зауважимо, що теорема 3 і висновок з неї справедливі і для складеного модуля .

Теорема 4. Якщо  є різні корені конгруенції (1), то її можна подати у вигляді:

                                                               (3)

де  - такий поліном степеня не вище , що немає коренів за модулем , старші коефіцієнти у  та  співпадають.

Доведення.

Розглянемо  з (2). Нехай  - деякий його корінь. Тоді  можна подати за формулою (2):

,

де  - поліном степеня не вищого за .

Підставимо  у (2). Отримаємо

.

Якщо , то корінь  - кратний.

У інший бік:

Розглянемо  таке число, що .

Добуток двох або декількох чисел ділиться на просте число  тоді і тільки тоді, коли на  ділиться принаймні один з множників добутку. За умовою  та  не співпадають

.

Отже,  не ділиться на , і значить на  ділиться :

 ,

останнє означає, що  корінь конгруенції  і для нього вірне подання::

,

Підставимо останній вираз до (2):

Так поступово можна прийти до поліному , який не має коренів за даним модулем. Якщо конгруенція (1) має  коренів, то  - старшому коефіцієнтові конгруенції (1).

Висновок. Якщо конгруенція (1) -го степеня за простим модулем  (можна вважати ) має  різних розв'язків  то поліном  можна розкласти на  лінійних множників типу  та множник :

                                                                   (4)

Приклад.

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

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

По-перше, можна понизити степінь конгруенції, бо відносно степені конгруенції за слідством теореми Ферма можна записати: . Отже отримаємо еквівалентну конгруенцію:

Знайдемо корені еквівалентної конгруенції з повної системи абсолютно найменших лишків . Підстановкою з’ясовуємо, що коренями конгруенції будуть . Очевидно, що ці корені є коренями й вихідної конгруенції.

Застосуємо для розкладання вихідного поліному за модулем 5 схему Горнера:

1

1

-1

1

-2

-2

1

-1

1

-1

0

1

1

0

1

0

2

1

2

0

З останнього рядка отримаємо конгруенцію першого степеня .

Розв’язок її - , співпадає з першим коренем. Отже, маємо для вихідного полінома однократні корені  і корінь кратності 2 .

Вихідна конгруенція розкладеться так:

5.2 Кількість коренів конгруенції -го степеня за простим модулем.

Теорема 5. Конгруенція -го степеня за простим модулем не може мати більш ніж  різних розв'язків.

Доведення. Нехай  – деякий розв'язок, відмінний від , тобто

;