Документ: Теорія чисел в криптографії, страницы 46-50

Висновок.		Конгруенція (1)		має за корінь x = a1				тоді і тільки тоді,		коли x - a1
ділить f (x) за модулем p .
Зауважимо, що теорема 3 і висновок з неї справедливі і для складеного модуля m .
Теорема 4.		Якщо	a1 , a2 ,..., ak ; (k £ n)			є різні корені конгруенції (1),			то її можна
подати у вигляді:
f (x) = (x - a1 )(x - a2 )...(x - ak ) fk (x) º 0 mod(p)										(3)
де	fk (x) - такий поліном степеня не вище n − k ,						що немає коренів за модулем p ,
старші коефіцієнти у f (x) та fk (x) співпадають.
Доведення.		f1 (x) з (2). Нехай a2 - деякий його корінь. Тоді f1 (x) можна подати за
Розглянемо
формулою (2):
f1 (x) º (x - a2 ) f2 (x)(mod p),
де	f2 (x) - поліном степеня не вищого за n − 2 .
Підставимо		f1 (x) у (2). Отримаємо
f (x) = (x - a1 )(x - a2 ) f2 (x) º 0 mod(p).
Якщо a2 = a1 , то корінь a1 - кратний.
У інший бік:			таке число, що (α 2			− α1 ) f1 (α 2 ) ≡ 0(mod p ).
Розглянемо a2 ¹ a1			таке число, що (α 2			− α1 ) f1 (α 2 ) ≡ 0(mod p ).
Добуток двох або декількох чисел ділиться на просте число								p тоді і тільки тоді, коли на p
ділиться принаймні один з множників добутку. За умовою a1 та a2 не співпадають
a1 ¹ a2 (mod p).
Отже, (a2 - a1 ) не ділиться на p , і значить на p ділиться							f1 (x):
f1 (a2 ) º 0(mod p),						f1 (x) º 0(mod p) і для нього вірне подання
останнє означає, що a2 —			корінь конгруенції			f1 (x) º 0(mod p) і для нього вірне подання
(x - a2 ) f2 (x) º 0(mod p) .
Підставимо останній вираз до (2) (x - a1 )(x - a2 ) f2 (x) º 0(mod p)
Так поступово можна прийти до поліному fk (x), k £ n , який не має коренів за даним
модулем.	Якщо	конгруенція (1)		має	n	коренів,	то	fk (x) = f0 (x) = a0	-	старшому
коефіцієнтові конгруенції (1).
Висновок.		Якщо конгруенція (1)			n -го степеня за простим модулем					p (можна

вважати n ≤ p ) має n різних розв'язків a1 , a2 ,..., an то поліном			f (x) можна розкласти на n
лінійних множників типу (x - ai ), i =		та множник a0 :
	1, n
f (x) = a0 (x - a1 )(x - a2 )...(x - an ) º 0(mod p)			(4)

Приклад.

Розкласти конгруенцію за даним модулем: 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 схему Горнера:

	1	1	-1	1	-2
-2	1	-1	1	-1	0
1	1	0	1	0
2	1	2	0

З останнього рядка отримаємо конгруенцію першого степеня 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 :

a0 (b - a1 )(b - a2 )...(b - an ) º 0(mod p)

(4*)

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

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

розв'язків конгруенції n -го степеня за простим модулем			p і, по-друге, для складених
модулів вона несправедлива, наприклад, у конгруенції першого степеня
16x º 32(mod 48) НСД (a, m) = (16,48) = 16,		16 \| 32, . Отже,		конгруенція має шістнадцять
розв'язків.
Висновок.
Конгруенція f (x) º 0(mod p), f (x) = a	xn + a xn−1 + ... + a		n−1	x + a	n
0		1

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

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

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

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

f (x) º 0(mod m),	f (x) = a	xn	+ a xn−1	+ ... + a	n−1	x + a			,	(1)
	0		1		n−1			n
Якщо в конгруенції (1)
m = m1m2 ×... × mk ,	(mi , m j ) = 1		"i ¹ j i, j =				,
m = m1m2 ×... × mk ,	(mi , m j ) = 1		"i ¹ j i, j =		1, k		,

47

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

f (x) º 0(mod m1 );
f (x) º 0(mod m2 );
	L

f (x) º 0(mod m );
	k

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

T = T1 ×T2 ×... ×Tk

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

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

Приклад.

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

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

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

	4	+ 2x	3	+ 8x + 9	º 0(mod 5)
x
x4		+ 2x3 + 8x + 9 º 0(mod 7)

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


	0	+ 2x	3	+ 3x -1 º 0(mod 5)
x		+ 2x		+ 3x -1 º 0(mod 5)
x4 + 2x3 + x + 2 º 0(mod 7)
Перша конгруенція:					2x2 + 3 º 0(mod 5); 2x2 - 2 º 0(mod 5);	x2 º 1(mod 5);
Розв’язки: x1 º1(mod 5); x2 º 4(mod 5)
Друга			конгруенція:		x4 + 2x3 + x + 2 º 0(mod 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 систем виду:

x º b1 (mod 5)			b1 Î (1,4)
x º b		(mod 7)	b Î (- 2,-1,3),
	2		2

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

x º b1 (mod 5) x = b1 + 5t					(*)
Підставимо x у друге рівняння системи:
b + 5t º b (mod 7) 5t º b			- b (mod 7);	5−1 º 3(mod 7) t º 3(b	- b )(mod 7).
1	2	2	1	2	1
Отже t = 3(b2 - b1 ) + 7t1
Підставимо t		до (*): x = b1 + 5(3(b2 - b1 )+ 7t1 ) = b1 +15b2 -15b1 + 35t2 = -14b1 +15b2 + 35t1 ,

або

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

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

48

Отже 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 :

f

¢(x

)

f

¢¢(x

0

)

2

f (n ) (x

0

)

n

f (x) = f (x )

+

0

(x - x ) +

(x - x

0

)

+ ... +

(x

- x

0

) .

0

1!

0

2!

n!

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

x = x1 + pt1,

t Î Z .

(**)

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

f (x) º 0(mod p2 ),

і розкладемо

f (x)

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

f ¢(x

)

f ¢¢(x

)

2

f

(n) (x )

n

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

1

(x

+ pt - x

) +

1

(x

+ pt - x )

+ ... +

1

(x + pt - x

) ,

1

1!

1

2!

1

n!

1

або

f ¢(x1 )

f ¢¢(x1 )

f (n ) (x1 )

º 0(mod p2 )

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

pt

+

p2t

2

+ ... +

pnt n

1

1!

1

2!

1

n!

1

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

p2 :

f (x ) + f ¢(x )pt

º 0(mod p2 )

1

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

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

f (x1 )

+ f ¢(x )t

º 0(mod p), або

f ¢(x )t º -

f (x1 )

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

f ′(x )

p

1

p

1

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

p .)

t1 º u1 (mod p).

Знайдемо

розв’язок

цієї

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

позначимо

його

-

Отже

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

у (**):

x = x + p(u

+ pt

2

) = x + pu + p2t

2

,

t

2

Î Z .

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

x + pu

= x

2

,

то

будемо

1

мати:

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).

49

Висновок: Будь який розв’язок 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) .

1

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

.

2

3

1

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). Поділимо конгруенцію на

p

2

= 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 .

9

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-го порядку є: за властивостями, за допомогою оберненого елементу, якщо він існує, за допомогою неперервних дробів;

50

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

Смотрите также: