Файл: Zastosuvannya_teoriyi_chisel_u_kriptografiyi_metodi.pdf

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

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

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

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

Добавлен: 07.06.2024

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

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

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

x2

º 9 +11× 2 = 31(mod 55) ,

 

 

 

x3

º 9 +11×3 = 42 (mod 55) , x4

º 9 +11× 4 = 53(mod 55) .

Якщо додати ще

один

модуль

11, то отримаємо

x5 º 9 + 5 ×11 = 64 º 9(mod 55).

 

 

 

Тобто розв’язки x0 , x1 , x2 , x3 , x4

не конгруентні між собою за

модулем 55, а x5

º x0 (mod 55) .

 

 

 

Отримали 5

неконгруентних

між

собою класів, які є

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

загальному вигляді

розв’язок можна подати так:

 

 

 

x º 9 +11t(mod 55),

t = [0,..., d -1]= [0,...,4].

в) Розв’язати конгруенцію 10x º 33(mod 55).

Розв’язання

(10,55) = 5 > 1, але 33 на 5 не ділиться, отже, ця конгруенція не має розв’язків.

4.2.2. ВИКОРИСТАННЯ ПІДХІДНИХ ДРОБІВ ДЛЯ РОЗВ’ЯЗАННЯ КОНГРУЕНЦІЙ.

Випадок ax º b(mod m) , (a, m) = 1. Розкладемо у неперервний дріб відношення

m

= q +

1

.

 

 

a

1`

q2 + ...

 

 

 

+ 1 qn

Будемо мати набір неповних часток q1 , q2 ,..., qn . За відомою

схемою побудуємо підхідні дроби di

=

Pi

. Розглянемо два

 

 

 

Qi

51

останніх підхідних дроби: δn−1 =

Pn−1

, δn

=

Pn

=

m

.

 

Qn

 

 

 

 

Qn−1

 

 

a

 

З

властивостей

підхідних

 

дробів

відомо:

PnQn−1 − Qn Pn−1 = (− 1)n , отже

mQn−1 − aPn−1 = (− 1)n .

Враховуючи,

що Qn−1

ціле число, можна mQn−1 вважати за модульний період,

який можна відкинути. Тобто маємо

aPn−1 = (− 1)n−1 mod(m).

Помножимо ліву і праву частини на число (−1)n b :

 

a(− 1)n−1 bPn−1 ≡ b(mod m).

Отже, розв’язок конгруенції буде x ≡ (− 1)n Pn−1b(mod m) .

Приклад

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

Розв’язання

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(256,337) = 1

 

–

розв’язок

єдиний.

Розкладемо

відношення

 

337

 

у неперервний дріб:

 

 

 

 

 

 

 

 

 

 

 

256

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

337

= 1+

 

81

; q = 1;

256

= 3 +

13

; q = 3;

 

 

 

 

 

 

 

 

 

 

 

 

 

256

 

 

 

256

 

 

1

 

81

 

 

 

81

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

81

= 6 +

 

3

; q = 6;

 

13

= 4 +

1

; q

 

= 4;

 

 

 

 

 

 

 

 

 

 

4

 

 

 

 

13

 

 

13

 

3

 

 

3

 

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3

= 3; q5

= 3 .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Будуємо схему.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

і

 

0

 

 

 

 

1

 

 

 

 

2

 

 

 

 

3

 

4

5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

qi

 

 

 

 

 

 

 

1

 

 

 

 

3

 

 

 

 

6

 

4

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Pi

 

1

 

 

 

 

1

 

 

 

 

4

 

 

 

 

25

 

104

337

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Qi

 

0

 

 

 

 

1

 

 

 

 

3

 

 

 

 

19

 

79

256

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

52

n = 5, Pn−1 = P4 = 104, b = 179

x = (-1)4 104 ×179 (mod 337);

104 ×179

= 55 +

81

.

337

 

 

337

 

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

4.2. ОБЕРНЕНИЙ ЕЛЕМЕНТ ЗА МНОЖЕННЯМ

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

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

Щоб дати відповідь на це питання, необхідно розглянути розв’язання конгруенції

ax º 1(mod m) .

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

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

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

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

Отже, для складеного модуля m обернений елемент існує

тільки для його зведеної системи лишків. Для будь-якого елемента a з класу зведеної системи лишків він дорівнює

53

a−1 ≡ aϕ(m )−1 (mod m) .

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

для нього збігається з повною системою лишків.

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

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

Знайти обернений елемент просто, використовуючи неперервні дроби.

a−1 = (− 1)n −1 Pn −1

Приклад

Знайти обернений елемент для числа a = 131 за модулем m = 437 .

Розв’язання

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Розглянемо

 

 

дріб

a

=

437

.

Подамо

цей

 

дріб через

 

 

 

 

131

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

m

 

 

 

 

 

 

 

 

 

 

 

ланцюжок неповних часток:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

437

= 3

44

 

;

 

q = 3;

131

= 2

43

;

q

 

= 2;

 

44

= 1

1

 

;

 

 

 

 

 

 

 

2

 

 

 

131

131

 

 

 

1

 

44

 

44

 

 

 

 

43

 

43

 

 

 

 

 

 

 

 

 

 

 

 

 

 

q = 1;

43

= 43;

q

 

= 43 .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3

 

 

 

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Отже,

437

= [3,2,1,43]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

131

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Будуємо таблицю підхідних дробів.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

і

 

0

 

 

 

 

 

 

1

 

 

2

 

 

 

 

3

 

 

 

4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

qi

 

 

 

 

 

 

 

 

 

3

 

 

2

 

 

 

 

1

 

 

 

43

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

m

 

 

Pi

 

1

 

 

 

 

 

 

3

 

 

7

 

 

 

 

10

 

 

437

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

a

 

 

Qi

 

0

 

 

 

 

 

 

1

 

 

2

 

 

 

 

3

 

 

 

131

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Використовуючи властивості підхідних дробів, можна записати:

54

P ×Q - P ×Q = (-1)4 або 437 ×3 -10 ×131 =1.

4 3 3 4 123

≡0 (mod 437 )

Отже, можемо записати (-10)×131 º1(mod 437) .

Звідси 131−1 º -10(mod 437) або 131−1 º 427(mod 437).

Відповідь

Обернений елемент для числа a = 131 за модулем m = 437

становить a −1 = -10 (серед

повної

 

системи абсолютно

найменших лишків), що відповідає

a −1

 

= 427 серед повної

системи найменших додатних лишків.

 

 

 

 

4.3. СИСТЕМИ КОНГРУЕНЦІЙ ПЕРШОГО СТЕПЕНЯ З ОДНИМ

 

 

 

 

НЕВІДОМИМ

 

 

 

 

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

 

 

 

 

 

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 ) . Помноживши кожне рівняння системи на свій зворотний елемент, перейдемо до еквівалентної системи:

55

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