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

Скачать файл
Заказать решение

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

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

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

Добавлен: 04.06.2024

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

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

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

Із схеми маємо:

n = 5, P

= P = 104, b = 179 x = (-1)4

104 ×179(mod 337);

 

104 ×179

= 55 +

81

 

 

n−1

4

 

337

 

337

 

 

 

 

Отже, x º 81(mod 337)

e. Розв’ язання конгруенцій типу 2k x º b(mod m), (2, m) = (2, b) = 1

2k x = b + mt Обираючи t = 1 або t = −1 отримуємо b ± m º 0(mod 2s ). Чим більший степінь 2, ти краще. Нехай δ найбільший степінь 2, такий, що 2δ | b ± a . Якщо δ > k , маємо:

x = b ± m (mod m) 2k

Якщо δ < k , скорочуємо конгруенцію на 2δ та повторюємо процедуру для

еквівалентної конгруенції 2k −δ x = b ±δm (mod m) 2

Приклад:

Розв’язати конгруенцію: 256x º 179(mod 337)

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

256 = 28 , отже можна вихідну конгруенцію подати так:

28 x º 179(mod 337)

а)Обчислимо b + m = 179 + 337 = 516 = 22129 b + m º 0(mod 4)

b - m = 179 - 337 = -158 = -2 × 79 b - m º 0(mod 2)

Обираємо b + m = 516 . Найбільша степінь 2, яка ділить b + m є 2 < 8 , отже переходимо до еквівалентної конгруенції:

 

б) 26 x º 129(mod 337)

 

 

129 + 337 = 466 = 2 × 233;

129 - 337 = -208 = -16 ×13 = -2413

 

Обираємо b - m = -2413;

d = 4 < 6 , отже, еквівалентна конгруенція буде

 

в) 22 x º -13(mod 337)

 

 

 

b + m = -13 + 337 = 324 = 4 ×81 = 2281;

b - m = -350 = -2 ×175

 

Обираємо b + m = 2281;

d = 2 = k = 2 , отже

x =

b + m

mod(m) =

2281

mod(337) = 81(mod 337)

 

 

 

 

22

 

22

 

 

 

 

Відповідь:

x = 81(mod 337) - розв’язок співпадає з попереднім.

Питання 3 Обернений елемент за множенням. Повернення до питання про системи лишків, як структури теорії груп.

Отримавши правила для розв’язання конгруенцій з одним невідомим, можемо дати відповідь на питання:

ДЛЯ ЯКИХ ЕЛЕМЕНТІВ ПОВНОЇ СИСТЕМИ ЛИШКІВ ЗА ДОВІЛЬНИМ МОДУЛЕМ m ІСНУЄ ОБЕРНЕНИЙ ЕЛЕМЕНТ З МНОЖЕННЯ?

Щоб дати відповідь на це питання, треба розглянути розв’язання конгруенції ax º 1(mod m)

Виходячи з вимог існування розв’язку такої конгруенції – (a, m) = 1, бо права частина

конгруенції дорівнює 1. Якщо за a взяти елементи повної системи залишків (як базу для всіх класів чисел за модулем m ), то очевидно, що конгруенція не завжди буде мати розв’язок. Наприклад, m = 15, a = 5 . Отже, з повної системи треба відкинути всі елементи,

кратні модулю. Отримаємо зведену систему лишків, кількістю j(m) елементів. Для будь

40

якого елементу зведеної системи за модулем m обернений елемент буде розв’язком конгруенції ax º 1(mod m) :

x º aϕ(m )−1 (mod m)

Позначимо обернений елемент через a−1 .

Отже для складеного модуля m обернений елемент існує тільки для його зведеної системи лишків і для будь якого елементу a з класу зведеної системи лишків дорівнює:

a−1 º aϕ(m )−1 (mod m)

Якщо модуль є просте число p , то зведена система лишків для нього співпадає з повною системою лишків.

Отже для будь якого елементу повної системи лишків за простим модулем p обернений елемент заданий та єдиний:

a−1 º a p−2 (mod p).

Висновки.

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

абелеву групу.

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

додавання і множення створює поле. Оскільки кількість елементів у повній системі лишків скінчена, то такі поля теж скінчені і носять назву полів Галуа.

Питання 4. Системи конгруенцій першого степеня з одним невідомим.

Розглянемо систему конгруенцій

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

 

з одним невідомим за різними модулями. Будемо вважати також, що m1 , m2 ,..., mk -

попарно прості: (mi , m j )= 1, i = 1, k; j = 1, k; i ¹ j .

Розв’ язок системи конгруенцій з одним невідомим є таке ціле число α , яке задовольняє усі конгруенції даної системи.

По-перше, спростимо дану систему. Оскільки (ai , mi ) = 1, i = 1, k , то для ai існує обернений елемент ai −1 : ai × ai −1 º 1(mod mi ) . Помноживши кожне рівняння системи на свій зворотній елемент, перейдемо до системи, еквівалентної даній:

x º c1 (mod m1 ),

 

2

2

),

x º c

(mod m

 

 

 

(2)

K K K K

 

x º c

(mod m ),

 

k

k

 

Отже, розв’язавши систему (1), ми тим самим знайдемо розв’язок системи (2). Відповідь про існування та структуру розв’ язку системи (2) дає

Китайська теорема про залишки:

41

 

Нехай дані 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 º 16(mod13);x º 128(mod 5)x º 82(mod 3)x º 55(mod 7)

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

По-перше спростимо систему:

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)

42

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)

Будуємо розв’язок:

a = 105 ×1× 3 + 273 × 2 × (- 2)+ 455 × 2 ×1 +195 × (-1)× (-1) = 315 -1092 + 910 +195 = 328

Перевірка:

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

 

 

конгруенцію підставляємо до системи. Якщо для нової системи збереглася попарна простота модулів, то вона має єдиний розв’язок, згідно з китайською теоремою про залишки. Але в цьому випадку i -та конгруенція має d розв’язків:

x º c + t

 

mi

(mod m ), t

 

=

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

j d

 

i

i

j

 

 

кожній з яких на i − му місці буде стояти відповідний розв’язок конгруенції.

Якщо модулі системи конгруенцій не є попарно простими, тобто (mi , m j )= d > 1 , то для розв’язання системи треба додатково досліджувати існування розв’язку. Якщо він є, то

 

 

 

 

 

 

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 = c2 - c1 (m1¢)−1 (mod m¢2 ). d

Розв’язок можна подати так: t = c2 - c1 (m1¢)−1 + m2¢t1 . d

43

Смотрите также файлы