Теорія чисел в криптографії

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

51

ТЕМА №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). Тобто за виконання додаткової умови розв’язок

2a

(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
				,
		L
	2	≡ C mod(pë	α ë	)
y

де p - просте число.

Розглянемо розв’язання (2) у випадках:

1.Модуль p > 2 - просте непарне число в першій степені.

2.Модуль pα - просте непарне число в степені α > 1.

3.Модуль p = 2

52

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

Розглянемо конгруенцію
x 2 ≡ a(mod p)	(3)

Якщо a ≡ 0(mod p), то (3) має один розв’язок.

Теорема 2. Критерій Ейлера.

Якщо a в конгруенції (3) не ділиться на p , тобто (a, p) = 1, то відповідна конгруенція має 2 різних розв’язки, якщо

p−1

a 2 ≡ 1(mod p),

або зовсім немає розв’язків, якщо

p−1

a 2 ≡ −1(mod p)

Доведення: Розглядаємо конгруенцію (3) за прости непарним модулем p .

Оскільки (a, p) = 1, то за теоремою Ферма a p−1 − 1 ≡ 0(mod p). Оскільки в нашому випадку p − 1 завжди парне, то вірним буде подання:

a

p−1

2

−1 a

p−1 2

	≡ 0(mod p)
+ 1

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

p−1

p−1

множників ділиться на це число. Одночасно числа

ділитися не

a

2

− 1

та a

2

+ 1 на p

можуть, бо їхня різниця дорівнює 2, не ділиться на p . Отже можливі два випадки:

p−1

p−1

≡ 1(mod p), або a

≡ −1(mod p)

a 2

2

Тепер згадаємо, що коли (3) має розв’язок, то існує x (та − x ) такий, що

(− x 2 ) ≡ x 2

≡ a(mod p), причому, оскільки (a, p) = 1, то і (± x, p) = 1. Для таких конгруенцій

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

степеня p −1 , отримаємо: 2

p−1

xp−1 ≡ a 2 (mod p).

За теоремою Ферма з урахуванням (x, p) = 1 маємо x p −1 ≡ 1(mod p), отже, виходячи з

існування розв’язку x конгруенції (3), отримали:

p−1

a 2 ≡ 1(mod p).

Висновок: якщо (3) має розв’ язки, то для неї виконується конгруенція

p−1

a 2 ≡ 1(mod p). В цьому випадку конгруенція має рівно 2 класи коренів, створених на лишках з повної системи абсолютно найменших лишків x та − x (або x та p − x з

повної системи найменших лишків) модуля p , оскільки (− x)2 = x 2 ≡ a(mod p)

Очевидно, що x та − x різні, тобто не конгруентні між собою, інакше б виконувалася конгруенція 2x ≡ 0(mod p), тобто x ділився б на p , а це протиріччя до

вихідної конгруенції. Більше коренів бути не може за теоремою про кількість коренів конгруенції з простим модулем.

53

p−1

Відповідно, іншій випадок - a 2

≡ −1(mod p) - виконується тільки для таких a , для

яких конгруенція (3) не має розв’ язку.

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

Але вище було відмічено, що x та − x (або x та p − x ) дають однакові квадрати, тобто (− x)2 = x 2 ≡ a(mod p). Отже, будемо мати чисел, для яких конгруенція (3) має розв’язок,

рівно половину з кількості елементів у повній системі лишків без нуля, тобто рівно p −1 2

лишки з повної системи лишків відповідають (3), а інша половина – ні. Нагадаємо, що p -

непарне, отже p −1 - ціле число. 2

Приклад.

Розглянемо повну систему абсолютно найменших лишків для чисел 5 та 7 і з’ясуємо, для яких лишків конгруенція (3) буде мати розв’язок, а для яких ні. В дужках будемо подавати відповідні лишки з повної системи найменших лишків.

p = 5, повна система абсолютно найменших лишків без нуля: − 2,−1,1,2 (1,2,3,4) .

Відповідні квадрати: (± 2)2 = 4 ≡ −1(mod 5), (± 1)2 = 1 ≡ 1(mod 5)

[(1)2 = 1 ≡ 1(mod 5), (2)2 = 4 ≡ 4(mod 5), ] (3)2 = 9 ≡ 4(mod 5), (4)2 = 16 ≡ 1(mod 5) .

Отже, якщо в (3) модуль дорівнює 5, а права частина a ≡ ±1(mod 5) (a ≡ 1,4(mod 5)), то конгруенція розв’язок має. Для a ≡ ±2(mod 5) (a ≡ 2,3(mod 5)) розв’язків немає. Тобто для

	5 − 1		= 2 лишків розв’язок є, для 2-х –	немає.
2			p = 7, повна система абсолютно найменших лишків без нуля: − 3,−2,−1,1,2,3
(1,2,3,4,5,6). Відповідні квадрати:
(± 3)2 = 9 ≡ 2(mod 7), (± 2)2 = 4 ≡ −3(mod 7), (± 1)2 = 1 ≡ 1(mod 7)
( (1)2			= 1 ≡ 1(mod 7), (2)2 = 4 ≡ 4(mod 7),	(3)2 = 9 ≡ 2(mod 7), (4)2 = 16 ≡ 2(mod 7),
(5)2		= 25 ≡ 4(mod 7), (6)2 = 36 ≡ 1(mod 7))
			Отже, якщо в (3) модуль дорівнює 7, а права частина a ≡ 1,2,−3(mod 7), то

конгруенція розв’язок має. Для a ≡ −1,−2,3(mod 7) розв’язків немає. Тобто для 7 − 1 = 3 2

лишків розв’язок є і для 3-х – немає.

Висновок. Серед повної системи лишків для простого непарного модуля p p −1 2

елементів відповідає конгруенції (3) і p −1 елементів не відповідає. 2

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

p−1

a 2 ≡ 1(mod p)

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

p−1

a 2 ≡ −1(mod p)

54

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

a носить назву квадратичний нелишок модуля p .

Наслідок з критерію Ейлера: У повній системі лишків простого непарного

модуля p кількість лишків завжди дорівнює кількості нелишків, а саме p −1 . 2

Теорема 3. (Теорема Ейлера).

Добуток двох лишків або двох нелишків за модулем p є лишок. Добуток лишку на нелишок за модулем p є нелишок.

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

p−1

p−1

p−1

≡ ±1(mod p), b

≡ ±1(mod p),

(ab)

≡ ±1(mod p),

a 2

2

2

„+”

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

Питання 3 Символ Лежандра.

Означення: Розглянемо конгруенцію x2 ≡ a(mod p)

(1)

Якщо p простий непарний модуль і (a, p) = 1 , символ Лежандра називається

величина

a

= 1 , якщо a - квадратичний лишок за модулем p і

a

= −1, якщо a -

p

p

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

a

p−1

≡ a 2 (mod p)

(2)

p

Критерій Ейлера дає одразу і формулу обчислення символу Лежандра, але для великих p,a обчислення є досить складними. Наведемо властивості символу Лежандра,

які значно спрощують процес обчислення даного показника і, відповідно, визначення наявності розв’язків (1).

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

1.

Якщо a ≡ b(mod p)

a

b

=

p

p

2.

ab

a b

=

, як наслідок:

p

p p

a n

a n

;

a 2

= 1;

ab

2

a

=

=

p

p

p

p

p

3.

1

= 1

p

− 1

p−1

4.

= (− 1)

2 .

p

55

Якщо взяти до уваги, що для усіх простих чисел p = 4k + 1 величина p -1 парна, а 2

для p = 4k + 3 , або p = 4k − 1 - непарна, то дану властивість можна прокоментувати так: для всіх модулів типу p = 4k + 1 число -1 є квадратичний лишок, а для модулів типу

p = 4k + 3 , або p = 4k − 1 - квадратичний нелишок.

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

a

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

за прости непарним

p

1

-1

2

q

модулем p до обчислення символів

,

,

,

, якщо q ¹ p - просте непарне

p

p p p

число.

2

p2 -1

5.

= (-1)

8

p

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

один з таких видів:

p = 8k + 1; p = 8k + 3; p = 8k + 5 (àáî

p = 8k − 3 );

p = 8k + 7 (àáî p = 8k − 1)

Якщо розглянути степінь

p 2 -1

для цих видів, то будемо мати:

8

p = 8k ± 1:

64k 2

+16k +1 -1

= 8k 2 + 2k;

64k 2 - 6k +1 -1

= 8k 2 - 2k - парні степені

8

8

p = 8k ± 3 :

64k 2

+ 48k + 9 -1

= 8k 2 + 6k +1;

64k 2

- 48k + 9 -1

= 8k 2 - 6k +1 - непарні

8

8

степені

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

Для чисел

2

= 1, тобто 2 є лишком за модулем

p = 8k ± 1 символ Лежандра

p = 8k ± 1

p

Для чисел

2

= -1, тобто 2 є нелишком за модулем

p = 8k ± 3 символ Лежандра

p

p= 8k ± 3

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

Якщо p та q два різних непарних простих числа, то для них виконується
співвідношення:
p q				p-1	×	q-1
		=	(-1) 2 2
q p
Число q , як і число p подається за модулем 4 або як 4k + 1, або 4k + 3. В першому

разі	q − 1	буде парним степенем, у другому – непарним. Добуток степенів	p -1	×	q -1	буде
			2
2				2

парним, якщо хоч один із множників парний.

56

Отже, якщо хоча б одне з чисел p та q має вигляд 4k +1, то			p		q
					=	.
			q		p
Якщо обидва числа мають вигляд 4k + 3, то	p			q
			= -
	q			p

Приклади:

1.Дослідити, чи має розв’ язки конгруенція x 2 º 438(mod 593)

Розв’язання

Спочатку спростимо конгруенцію: x 2 º -155(mod 593). Розкладемо a = -155 = (-1)×5 ×31

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

	-155		-1	5	31
		=
	593		593	593	593
						-1	148×2	= 1 ,
1) 593 = 148 × 4 +1, тобто							= (-1)
						593

2) (5,593) = 1, 593 = 148 × 4 +1, 5 = 4 ×1 +					5				593			3			5		2	,
				1				=			=			=		=
					593				5			5			3		3
						2			1		= -1
3 = 8 × 0 + 3 , отже 2 є нелишком по модулю 3,								= (-1)
						3
3) (31,593) = 1, 593 =			31		593	=		4			22		= 1
		4 ×148 +1		=					=
			593		31			31			593
	-155	= -1
4)	= 1× (-1)×1
	593

Висновок: Конгруенція x 2 º 438(mod 593) розв’язків немає.

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

Розв’язання

Спочатку спростимо конгруенцію: x 2 º 792(mod1231). Розкладемо

a = 792 = 8 × 9 ×11 = 23 × 32 ×11

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

23		× 32 ×11		2	11
				=
	1231
				1231 1231
1) 1231 = 153 ×8 -1, тобто								2	= 1
							1231
2) 11 = 2 × 4 + 3, 1231 = 4 ×									11		1231			-1	= 1
						307 + 3					= -		= -
									1231		11			11
		23 × 32 ×11
3)					= 1
		1231		= 1×1

Висновок: Конгруенція x 2 º 792(mod1231) має 2 розв’язки.

57

Питання 4. Символ Якобі.

Якобі узагальнив символ Лежандра на випадок, коли модуль конгруенції P є

непарне число, яке складене з простих чисел, тобто P = p1 p2 ... pk , pi можуть

повторюватися.

Означення:

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

a

a

a

a

,

=

...

P

p1 p2 pk

a

a

a

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

де

,

,...,

p1

p2

pk

Нехай a = q1q2 ...qm - розкладання числа a на прості множники. Тоді за

властивостями символу Лежандра

a

q

q

q

a

q

q

q

a

q

q

q

, тобто

=

1

2

...

m ;

= 1

2 ...

m ;...;

= 1

2 ...

m

p1

p1 p1

p1

p2

p2 p2 p2

pk

pk pk pk

a

qi

=

∏

P

i =1,m

p j

j =1,k

Теорема 1.

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

853

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

Розв’язання:
853 = 4 × 213 +1			853		=	1409		=	556			22 ×139			139		853			853	19
										=					=	=			=		=
												853
			1409			853			853						853		139		139		139
						19			139				6		2	3
19 = 4 × 4 + 3; 139 = 4 ×34 + 3									= -			= -			= -
						139			19				19		19 19
19 = 8 ×		2					+ 3		3			19			1
		2 + 3	= -1; 3 = 4 × 0								= -			= - = -1
		19							19				3		3
	853	= (-1)× (-1)× (-1)		= -1
1409

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

–Квадратична конгруенція має такий загальний вигляд:

ax 2 + bx + c º 0(mod m);

– Зведена квадратична конгруенція має вигляд: y 2 º C(mod P) ;

– Якщо (C, P) = P , то квадратична конгруенція y 2 º C(mod P) завжди має єдиний розв’язок y ≡ 0(mod P)

58

– Якщо модуль є складеним числом m = p1α1 p2α2 ...pk α k , то розв’язання квадратичної конгруенції зводиться до розв’язання системи конгруенцій виду:

y 2		≡ C mod(p		α1	)
			1
		≡ C mod(p2		α 2	)
y 2
					,
			L
	2	≡ C mod(pë		α ë	)
y
	де p - просте число;
		–	В разі простого непарного модуля квадратичні конгруенції мають такі

особливості розв’язання:

квадратична конгруенція, в якій не ділиться на p , тобто (C , p) = 1, має 2 різних

розв’язки, якщо

p−1

C 2 ≡ 1(mod p),

або зовсім немає розв’язків, якщо

p−1

C 2 ≡ −1(mod p)

Причому розв’язками є класи лишків з повної найменшої системи лишків або з абсолютно найменшої системи лишків.

–Якщо конгруенція y 2 ≡ C(mod p) має розв’язки, то C носить назву

лишка за модулем p , якщо розв’язків немає, то C - нелишок за модулем p .

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

a			p −1
y 2 ≡ a(mod p)є символ Лежанндра		≡ (−1) 2			(mod p) . Обчислити символ
p

Лежандра можна використовуючи 6 властивостей.

– Узагальненням символу Лежандра є символ Якобі. Якщо розглядається конгруенція y 2 ≡ a(mod P), де P = p1 p2 ... pk , то символом Якобі називається показник

a

a

a

a

a

a

a

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

=

...

, де

,

,...,

P

p1

p2

pk

p1

p2

pk

Після вивчення теми 4 ви повинні вміти:

– Визначати, чи має квадратична конгруенція y 2 ≡ a(mod m) нульовий розв’язок.

–Спираючись на властивості символу Лежандра, обчислити його для конгруенції

y 2 ≡ a(mod p), ( p - просте число) визначивши тим самим чи є лишком за модулем

pчисло a .

–В разі складного модуля квадратичної конгруенції y 2 ≡ a(mod m) обчислювати для неї символ Якобі.

Контрольні питання до теми №4.

1.Дайте означення квадратичної конгруенції за довільним модулем.

2.Укажіть в якому випадку квадратична конгруенція має єдиний нульовий розв’язок.

3.Назвіть спосіб розв’язання квадратичної конгруенції за складеним модулем.

4.Назвіть критерій Ейлера про наявність розв’язків конгруенції x2 ≡ a(mod p)

59

5.Дайте означення лишка і нелишка за модулем p

6.Назвіть слідство з критерію Ейлера про наявність розв’язку квадратичної конгруенції.

7.Назвіть теорему Ейлера про взаємодію лишків і нелишків по певному простому модулю.

8.Назовіть 6 властивостей символу Лежандра.

9.За допомогою символу Лежандра з’ясуйте, чи є лишком 139 за модулем 5, якщо так, знайдіть розв’язок квадратичної конгруенції x2 ≡ 139(mod 5)

10.За допомогою символу Лежандра з’ясуйте, чи є лишком 98 за модулем 5, якщо так, знайдіть розв’язок квадратичної конгруенції x2 ≡ 98(mod 5)

11.Які лишки з повної системи найменших додатних лишків за модулем 7

a = {0,1,2,3,4,5,6} є лишками для квадратичної конгруенції x2 ≡ a(mod 7)? Скільки таких лишків?

12.Дайте означення символу Якобі за складеним модулем P = p1 p2 ... pk

13.Обчисліть символ Якобі для 393 за модулем 455.

60