Информатика и выч. техника \ Криптография

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

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

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

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

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

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

, або

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

Отримаємо:

, або ,

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

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

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

(2)

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

Доведення.

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

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

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

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

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

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

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

(3)

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

Доведення.

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

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

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

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

У інший бік:

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

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

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

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

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

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

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

(4)

Приклад.

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

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

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

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