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

Скачать файл (0,61Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 04.06.2024

Просмотров: 38

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Отже x º 26,6,31,19,34,24(mod 35)

Тепер розглянемо конгруенцію (1) в разі, якщо m = p1α1 × p2 α2 ×... × pk αk :

f (x) º 0(mod p α1	× p	α2	×... × p	αk )	(2)
1		2		k

Розв’язання такої конгруенції зводиться до розв’язання конгруенцій виду

f (x) º 0(mod pα )

(3)

Розв’язання останньої конгруенції зводиться до розв’язання конгруенції

f (x) º 0(mod p)

Для доведення цього факту нам необхідно буде згадати ряд Тейлора для розкладання полінома у околі точки x0 :

¢(x

)

¢¢(x

)

f (n ) (x

)

f (x) = f (x )

(x - x ) +

(x - x

)

+ ... +

- x

) .

Розглянемо конгруенцію (3), її розв’язок x º x1 (mod p), що еквівалентно запису

x = x1 + pt1,

t Î Z .

(**)

Підставимо це значення у конгруенцію

f (x) º 0(mod p2 ),

і розкладемо

f (x)

у ряд Тейлора у околі точки x1 :

f ¢(x

)

f ¢¢(x

)

(n) (x )

f (x + pt ) = f (x ) +

+ pt - x

) +

+ pt - x )

+ ... +

(x + pt - x

) ,

або

f ¢(x1 )

f ¢¢(x1 )

f (n ) (x1 )

º 0(mod p2 )

f (x + pt ) = f (x )+

p2t

+ ... +

pnt n

Відпросимо усі складові, кратні

p2 :

f (x ) + f ¢(x )pt

º 0(mod p2 )

f (x), отже конгруенцію можна скоротити:

Оскільки x1 є розв’язком (3), то p |

f (x1 )

+ f ¢(x )t

º 0(mod p), або

f ¢(x )t º -

f (x1 )

(mod p). (Візьмемо випадок, коли

f ′(x )

не ділиться на

p .)

t1 º u1 (mod p).

Знайдемо

розв’язок

цієї

конгруенції,

позначимо

його

Отже

t1 = u1 + pt2 . Підставимо значення t

у (**):

x = x + p(u

+ pt

) = x + pu + p2t

Î Z .

Якщо позначити

x + pu

= x

то

будемо

мати:

x º x2 (mod p2 ), або x º x2 + p2t2

(***)

Підставляємо його у конгруенцію

f (x) º 0(mod p3 ),

Розкладаємо за рядом Тейлора в околі x2 , відкидаємо всі складові, кратні p3 :

f (x2 ) + f ¢(x2 )p2t2 º 0(mod p3 )

Зауважимо, що оскільки x1 º x2 (mod p) f ′(x1 ) º f ′(x2 )(mod p) f ′(x2 ) не ділиться на p2 , а f (x2 ) - ділиться. Скоротимо конгруенцію на p2 . Будемо мати:

f (x22 ) + f ¢(x2 )t2 º 0(mod p). Розв’язок t2 = u2 + pt3 підставимо до (***) p

x = x2 + p2 (u2 + pt3 ) = (x2 + p2u2 )+ p3t3 , x2 + p2u2 = x3 x º x3 (mod p3 )

Продовжуючи таким чином, знайдемо кінець кінцем конгруенцію x º xα (mod pα ), яка є розв’язком конгруенції (3).

Висновок: Будь який розв’язок x º x1 (mod p) конгруенції

f (x) º 0(mod p) за умови,

що f ′(x1 ) не ділиться на p , дає єдиний розв’язок конгруенції (3).

Приклад.

Розв’язати конгруенцію x4 + 7x + 4 º 0(mod 27)

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

Маємо x4 + 7x + 4 º 0(mod 33 ). Отже спочатку шукаємо розв’язок конгруенції

x4 + 7x + 4 º 0(mod 3).

По-перше, спростимо її: x0 + x +1 º 0(mod 3), або x º -2(mod 3) . Маємо розв’ язок:

x º 1(mod 3),

x = 1 + 3t . Підставимо цей x у конгруенцію x4 + 7x + 4 º 0(mod 9) .

f ¢(x) = 4x3 + 7;

f ¢(1) = 11 º 2(mod 9) - не ділиться на

f (1) = 14 + 7 + 4 = 12 º 3(mod 9);

p = 3

′

×3t1 º 0(mod 9). Поділимо конгруенцію на p = 3 :

f (1)+ f (1)

f (1)

+ f ¢(1)t

º 0(mod 3) 1 + 2t

º 0(mod 3), 2t

º -1(mod 3); t

º 1(mod 3); t = 1 + 3t

x : x = 1 + 3t1 = 1 + 3(1 + 3t2 ) = 4 + 9t2 .

Підставимо

значення t1 у формулу для

Отже

знайшли розв’язок x º 4(mod 9).

x = 4 + 9t2

підставимо до конгруенції x4 + 7x + 4 º 0(mod 27).

f (4) = 256 + 7 × 4 + 4 = 288 º 18(mod 27); f ¢(x) = 4x3 + 7;

f ¢(4) = 4 × 43 + 7 = 263 º 20(mod 27)

′

9t2 º 0(mod 27). Поділимо конгруенцію на

= 9 :

f (4) + f (4)×

f (4)

+ f ¢(4)t

2 º 0(mod 3) 2 + 20t2 º 0(mod 3),

2t2 º -2(mod 3); t2

º -1(mod 3); t2

= 2 + 3t3 .

x = 4 + 9t2 = 4 + 9(2 + 3t3 ) = 22 + 27t3 x º 22(mod 27)

Отже розв’язком конгруенції x4 + 7x + 4 º 0(mod 27)

буде

клас чисел

x = 22 + 27t .

Розв’язок єдиний.

Висновки Після вивчення теми 4 ви повинні знати такі факти:

–Алгебраїчною конгруенцією з одним невідомим називається конгруенція виду:

f (x) ≡ 0(mod m), m Z , f (x) = a	n	x n + a	n−1	x n−1 + ... + a x + a	0	;
	n		n−1	1	0

–розв’язати конгруенцію означає знайти усі такі xi , які задовольняють конгруенцію;

–дві конгруенції з одним невідомим називаються еквівалентними, якщо всякий

розв'язок x однієї конгруенції є розв’язком іншої.

–за один розв’язок конгруенції приймається весь клас лишків, до яких належить x .

–конгруенція має стільки розв’язків, скільки класів її задовольняють;

–конгруенція 1-го степеня має вигляд ax º b(mod m)

–	конгруенція 1-го степеня ax º b(mod m) має єдиний розв’ язок в разі, якщо (a ,m) = 1
–	за умови, що (a ,m) = d > 1 конгруенція має розв’язок, якщо d \| b . Цих розв’язків є
	рівно d штук ( d класів). Перший з розв’язків знаходиться із скороченої на d
	конгруенції, інші обчислюються, як x2 = x1 + m1 ,..., xd = x1 + (d -1)m1

–якщо у конгруенції ax º b(mod m) (a ,m) = d > 1 і d не ділить b , то така конгруенція розв’язку немає;

–найвідомішими методами розв’язання конгруенцій 1-го порядку є: за властивостями, за допомогою оберненого елементу, якщо він існує, за допомогою неперервних дробів;

–система лишків за простим модулем 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.В якому разі система з двох конгруенцій не має розв’язку?

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

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

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

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

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

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

Питання 1 Загальні положення.
Квадратична конгруенція має загальний вигляд:
ax 2 + bx + c ≡ 0(mod m)	(1)

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

y 2 ≡ C(mod 4am)

(2)

Дійсно, за властивостями конгруенцій, які відповідають зміні модуля конгруенції, можемо помножити усі складові конгруенції на множник 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). Тобто за виконання додаткової умови розв’язок

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

Наслідок.
Якщо модуль є складеним числом m = p					α1	p	α 2	... p	α k , то розв’язання конгруенції (2)
				1			2		k
зводиться до розв’язання системи конгруенцій виду:
y 2		≡ C mod(p	α1	)
		1
		≡ C mod(p2	α 2	)
y 2		≡ C mod(p2	α 2	)
				,
		L
	2	≡ C mod(pë	α ë	)
y		≡ C mod(pë		)