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

a1 x º b1

(mod m1 ),

(a1 , m1 ) = 1,

a

x º b

(mod m ),

(a

, m ) = 1,

2

2

2

2

2

(1)

K K K K K K K

a

x º b (mod m ),

(a

, m ) = 1

k

k

k

k

k

2

2

),

x º c

(mod m

(2)

K K K K

x º c

(mod m ),

k

k

Нехай дані k попарно простих чисел m1 , m2 ,..., mk та чисел c1, c2 ,..., ck , таких, що

0 £ ci £ mi

-1,

i =

. Тоді існує таке єдине ціле число α , у якого залишок від ділення на

1, k

mi становить ci (тобто a º ci (mod mi )).

Доведення.

Доводити будемо побудовою числа α . Позначимо через M НСК всіх модулів.

Оскільки вони попарно прості, то M = m1m2 ...mk . Далі побудуємо систему чисел

=

M

=

m1m2 ...mi ...mk

= m m

i =

M

i

...m

m

...m

,

1, k

mi

mi

1

2

i−1

i+1

k

Кожне M i

є взаємно простим з числом mi

, тому для нього існує обернений елемент

M

i

−1 º M

ϕ(mi )−1 mod(m )

i

i

k

−1ci

Побудуємо число: a = ∑ M i M i

i=1

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

x º a(mod M )

Дійсно, підставимо α у першу конгруенцію системи (2):

M

1

M

1

−1c + M

2

M

−1c

2

+ ... + M

k

M

k

−1c

k

º c (mod m )

1

2

1

1

Всі доданки, починаючи з другого діляться на m1 , бо цей модуль присутній у M i , як

множник. Тому всі ці доданки конгруентні 0 за модулем m . Добуток M

M

−1

º 1(mod m ) за

1

1

1

1

побудовою,

(M1, m1 ) = 1 . Залишається тотожна конгруенція c1 º c1 (mod m1 ).

У другому рівнянні не конгруентним 0 за модулем m2

буде тільки доданок

M 2 M 2

−1c2 . Отже α є розв’язком для другої конгруенції і т. д.

Розв’язок підійде до кожної конгруенції в силу своєї структури.

Висновок: Розв’ язок системи (2) існує, і це є клас чисел

x = α + Mt,

t Z

x º 3(mod13);

x º -2(mod 5)

x º 1(mod 3)

x º -1(mod

7)

M i : M1 = 5

× 3

× 7 = 105; M 2 = 13 × 3 × 7 = 273; M 3 = 13 × 5 × 7 = 455; M 4 = 13 × 5 × 3 = 195

Знайдемо обернені значення до M i ,

i = 1,2,3,4 :

105M1−1 º 1mod(13): 105 = 13 ×8 +1

273M 2

−1 º 1mod(5): 273 × 2 = 546 = 545 +1

105 º 1(mod13) M1−1 º 1(mod13)

M 2

−1 º 2 (mod 5)

455M 3

−1 º 1mod(3):

195M 4

−1 º 1mod(7): 195 × 6 = 1170 = 167 × 7 +1

455 × 2 = 910 = 909 +1 M 3

−1 º 2(mod 3)

M 4

−1 º 6 (mod 7) º -1(mod 7)

328 = 25 ×13 + 3; 328 = 65 × 5 + 3 = 66 × 5

- 2;

328 = 109 × 3 +1; 328 = 46 × 7 + 6 = 47 ×8

-1

Система розв’язана вірно.

Відповідь: розв’язком системи є клас лишків x = 328 + 13 × 5 × 3 × 7 × t

за модулем, що

дорівнює НСК 13, 5, 3, 7

Якщо у системі (1) для будь якої конгруенції ai x º bi (mod mi )

(ai , mi ) = d > 1, d | bi , то

a

i

b

m

скорочуючи конгруенцію на d , переходимо до конгруенції

x º

i

mod

i

і вже цю

d

d

d

x º c + t

mi

(mod m ), t

=

0, (d -1), отже необхідно розглянути, відповідно, d систем, в

j d

i

i

j

m1m2 ...mk

це буде розв’язок за модулем, рівним НСК модулів системи: x º a mod

(m , m ,..., m )

1 2

k

Розглянемо для прикладу систему з двох конгруенцій. Будемо вважати, що її

можна звести до вигляду:

x º c1

(mod m1 )

x º c2

(mod m2 )

Нехай (m1 , m2 ) = d > 1,

′

′

′

′

m1 = m1 × d

, m2 = m2 × d ,

(m1

, m2 ) = 1

Будемо розв’язувати систему методом підстановки. З першої конгруенції можна

записати:

′

x = c1 + m1dt .

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

конгруенцію:

′

′

′

′

c1 + m1dt º c2 (mod m2 d ),

m1dt º c2

- c1 (mod m2d )

Отже виникла умова:

Якщо d | c2 - c1 , то друга конгруенція розв’ язок має. В іншому випадку –

ні.

Нехай умова виконується. Тоді розглядаємо конгруенцію m¢t º

c2 - c1

(mod m¢ ).

1

d

2

Підставимо значення t

у вираз для x :

= c + m′(c − c )(m′)

+ m

t =

x = c + m′dt = c + m′d

c2

− c1

(m′)

+ m′t

m2

−1

−1

1

1

1

1

d

1

2 2

1 1 2 1 1

1

d

2

= c + m′(m′)−1

(c

2

− c ) +

m1m2

t

2

1

1

1

1

d

Позначимо c + m′(m′)−1

(c

2

− c ) = x ,

m1m2

= M .

1

1

1

1

1

d

x ≡ c1

(mod m1 )

1.Система з двох рівнянь виду

x ≡ c2

(mod m2 ) в разі (m1 , m2 ) = d > 1

буде мати

f (x) ≡ 0(mod p),

f (x) = a

xn + a xn−1

+ ... + a

n−1

x + a

n

,

(1)

0

1

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

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

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

f (x) ≡ 0(mod p), f (x) = xn + b xn−1 + ... + b

x + b

1

n−1

n

Справді,

через те що p —

просте і a0

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

p завжди існує єдине число,

обернене до a0 : a0 a0

−1 ≡ 1(mod p),

a0

−1 ≡ a0 p−2 (mod p) . Помноживши конгруенцію (1) на a0

−1 ,

якщо у (1)

n ³ p , то

≡ 0(mod p)

a xn + a xn−1

+ ... + a

n−1

x + a

n

≡ b x p−1

+ b x p− 2

+ ... + b

p− 2

x + b

p−1

0

1

0

1

Доведення.

Поділимо

f (x) на x p − x . Частку від ділення позначимо черезQ(x) , залишок – через

f (x) = (x p − x)Q(x) + R(x)

де Q(x) –

поліном, степеня n − p ,

R(x) – поліном степеня,

не

більшого за p − 1 .

Коефіцієнти

Q(x) , R(x) – цілі числа.

За теоремою Ферма якщо

p

– просте число, то

1.

(x p − x)| f (x) . Тоді R(x) ≡ 0(mod p) - тотожна, 0 ≡ 0(mod p), тобто вірна для будь

якого x .

R(x) ≡ bp−1 (mod p) - поліном нульового степеня. Якщо bp−1 не ділиться на p , то дана

2.

Очевидні розв'язки останньої конгруенції x1 ≡ 2(mod 5), x2 ≡ 3(mod 5)

будуть також і

розв'язками вихідної конгруенції.

Теорема 3. Якщо α1 —

деякий розв'язок конгруенції n − го степеня

f (x) ≡ 0(mod p),

то має місце тотожна конгруенція:

f (x) ≡ (x − α1 ) f1 (x)(mod p)

(2)

де f1 (x) — поліном

n − 1 -го

степеня. Старший коефіцієнт

полінома f1 (x) збігається з

старшим коефіцієнтом вихідного полінома

f (x) .

Доведення.

на x − α1

Поділимо f (x)

і частку позначимо через

f1 (x), остачу –

через R(x):

(x − α1 ) f1 (x) + R(x) ≡ 0(mod p).

За теоремою Безу R(x) = f (α1 ), але оскільки α1

—

розв'язок конгруенції, то

f (α1 ) ≡ 0(mod p) , отже справедливою буде конгруенція:

(x − α1 ) f1 (x) ≡ 0(mod p).

f (x) ділиться на

x − α1 за модулем

За таких умов кажуть,

що

p . Очевидно, що й

навпаки: якщо

f (x)

ділиться на

x − α1

з

нульовим

залишком за

модулем p (тобто

R(x) ≡ 0 mod(p) ),

то,

використовуючи

теорему

Безу,

можна

стверджувати, що

f (α1 ) = R(x) ≡ 0(mod p), звідки витікає, що α1 —

розв'язок конгруенції.