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

Тоді розв’язок системи буде мати вигляд:

x ≡ x1 (mod M )

Висновки.

розв’язок тільки за умови, що d | c2 − c1 . В іншому разі система не сумісна. Якщо умова виконана і розв’язок є, він буде знайдений за модулем, який дорівнює НСК m1 та m2

2. Якщо система складається з k > 2 конгруенцій з модулями, що мають НСД>1, то перевірку необхідно проводити поступово. В разі, коли хоча б одна з отриманих конгруенцій в ході розв’язку немає розв’язку, то і вся система не сумісна. Якщо розв’язок є, то це буде конгруенція по НСК усіх модулів.

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

Розглянемо загальні теореми, які стосуються конгруенцій n-го степеня за простим модулем p . Припустимо, що задано конгруенцію

отримаємо еквівалентну конгруенцію із старшим коефіцієнтом b0 ≡ 1(mod p)

Теорема 2. Якщо степінь конгруенції (1) не менший від модуля конгруенції, то вона еквівалентна деякій конгруенції степеня, не вище за p − 1 (за тим самим модулем). Тобто,

R(x). Тоді на підставі алгоритму ділення з остачею дістанемо:

x p − x ≡ 0(mod p) для будь-якого цілого х. Отже, отримаємо еквівалентну конгруенцію:

f (x) ≡ R(x)(mod p)

Висновок: Конгруенції f (x) ≡ 0(mod p) та R(x) ≡ 0(mod p) мають однакові корені.

44

Частинні випадки:

конгруенція не має розв’язків, бо вона зводиться до невірної конгруенції : bp−1 ≡ 0(mod p). Приклад. Знайти конгруенцію степені не вище 4, еквівалентну даній:

f (x) = x17 + 2x11 + 3x8 − 4x7 + 2x − 3 ≡ 0(mod 5)

Розв’язання: Поділимо f (x) на x5 − x . Для полегшення ділення використаємо наслідок з малої теореми Ферма ( a p−1 ≡ 1(mod p), (a, p) = 1 ).

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

Якщо (a, p) = 1, n ≡ m(mod p − 1) an ≡ am (mod p).

Дійсно, нехай n > m, n = m + q(p − 1), За теоремою Ферма a p−1 ≡ 1(mod p). Піднесемо цю конгруенцію до степені q : a( p−1)q ≡ 1(mod p). Помножимо отриману конгруенцію і конгруенцію am ≡ am (mod p), дістанемо:

a( p−1)q+m ≡ am (mod p) , або an ≡ am (mod p)

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

17 ≡ 1(mod 4); 11 ≡ 3(mod 4); 8 ≡ 0(mod 4); 7 ≡ 3(mod 4)

Отримаємо:

R(x) = x1 + 2x3 + 3x0 − 4x3 + 2x − 3 ≡ 0(mod 5) , або − 2x3 + 3x ≡ 0 mod(5),

або, замінивши лишок -2 на лишок 3(mod5), отримаємо: 3x3 + 3x ≡ 0 mod(5), і остаточно:

x3 + x ≡ 0 mod(5)

45

Приклад.

Розкласти конгруенцію за даним модулем: x4 + x3 - x2 + x - 2 º 0(mod 5)

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

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

x3 - x2 + x -1 º 0(mod 5)

46

Знайдемо корені еквівалентної конгруенції з повної системи абсолютно найменших лишків (- 2,-1,0,1,2). Підстановкою з’ясовуємо, що коренями конгруенції будуть x ≡ −2,1,2 .

Очевидно, що ці корені є коренями й вихідної конгруенції.

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

З останнього рядка отримаємо конгруенцію першого степеня x + 2 º 0(mod 5). Розв’язок її - x º -2(mod 5) , співпадає з першим коренем. Отже, маємо для вихідного полінома однократні корені x1 º 1(mod 5), x2 º 1(mod 5) і корінь кратності 2 x3,4 º -2(mod 5).

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

(x + 2)2 (x -1)(x - 2) º 0(mod 5)

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

Доведення.

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

b ¹ ai (mod p), i = 1, n ;

Підставимо в (4) β замість x :

Оскільки модуль простий, значить хоча б один з множників повинен ділитися на модуль p . Лінійні множники не діляться на модуль за допущенням доведення. Старший коефіцієнт конгруенції теж не ділиться на модуль, бо інакше степінь конгруенції був би нижчим. Отже приходимо до висновку, що конгруенція (4*) не можлива. Отже β не може бути коренем і не співпадати хоча б з одним значенням з набору a1 , a2 ,..., an .

Слід зауважити, що по-перше, ця теорема не підтверджує, взагалі, наявності

має більше ніж n розв'язків тоді і тільки тоді, коли вона тотожна, тобто коли всі її коефіцієнти діляться на p .

Дійсно, якщо коефіцієнти даної конгруенції діляться на p , то конгруенція виконується за будь-якого значення x , тобто вона тотожна, число її розв'язків (що дорівнює p ) буде більше ніж n .

Питання 6 Конгруенції n-го степеня за складеним модулем.

Розглянемо конгруенцію

47

то конгруенція рівносильна системі:

Якщо позначити через Ti кількість розв’язків i − ї конгруенції системи, то загальна кількість розв’язків вихідної конгруенції дорівнює:

T = T1 ×T2 ×... ×Tk

Справедливість цієї теореми витікає з властивостей конгруенцій. Зокрема, якщо конгруенція виконується за модулем m , то вона виконується і за будь яким дільником m .

Схему розв’язання конгруенцій n -го степеня за модулем, чкий є добутком простих чисел, розглянемо на прикладі.

Приклад.

Розв’язати конгруенцію: x4 + 2x3 + 8x + 9 º 0(mod 35)

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

35 = 5 × 7 , отже дана конгруенція відповідає системі:

Після спрощення система буде мати вигляд:

системи абсолютно найменших лишків (- 3,-2,-1,0,1,2,3): 0, 1 – не розв’язки, x1 º -1(mod 7) – розв’язок. Інші розв’язки шукаємо за схемою Горнера. Знайдемо ще два -

x2 º -2(mod 7), x3 º 3(mod 7).

Отже маємо 2 розв’ язки у першій конгруенції і 3 розв’язки у другій. Загалом система, а отже і вихідна конгруенція має T = 2 × 3 = 6 розв’язків. Для того, щоб їх знайти необхідно розглянути 6 систем виду:

Але ми можемо розв’ язати дану систему у загальному вигляді і маючи її загальний розв’язок, підставити потрібні значення b1 , b2 :

або

x º 21b1 +15b2 (mod 35) - загальна формула розв’язку.

Залишилось тільки по черзі підставити у неї значення b1 = (1,4), b2 = (- 2,-1,3)

48