Файл: Zastosuvannya_teoriyi_chisel_u_kriptografiyi_metodi.pdf

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

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

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

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

Добавлен: 07.06.2024

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

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

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

Множимо

конгруенції

k º k(mod m)

та a º b(mod m). За

властивістю 4 отримаємо ka º kb(mod m) .

 

 

 

 

 

 

Узагальнення

 

 

 

 

 

 

 

 

 

 

7. Якщо у

поліномі від k

змінних зі сталими коефіцієнтами

S = ∑ Aα1 ,...,αk x1

α1 ...xk αk

коефіцієнти Aα1 ,...,αk

замінити

на числа

 

 

 

 

xi (i =

 

)

Bα1 ,...,αk

, конгруентні

Aα1 ,...,αk

за модулем m , змінні

1, k

 

(i =

 

), то

замінити на конгруентні їм за модулем m змінні yi

1, k

новий

вираз

поліному

S

буде конгруентним

вихідному

поліному за модулем m .

S = ∑ Aα1 ,...,αk x1α1 ...xk αk º ∑ Bα1 ,...,αk y1α1 ...yk αk (mod m) .

Для доведення використовуються властивості 1-6. Зокрема, для полінома n -го степеня від однієї змінної:

 

º bi (mod m), xi º yi (mod m), (i =

 

)

ai

0, n

n

n

∑ai xn−i º ∑bi yn−i (mod m) .

i =0

i=0

8. Обидві частини конгруенції можна поділити на спільний дільник d , якщо (m, d ) =1 :

a º b(mod m), d | a, d | b, (d , m) = 1 a º b (mod m). d d

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

1. Обидві частини конгруенції і модуль можна помножити на одне й те саме число:

aº b(mod m) (a = mt + b)× k ka = kmt + kb ka º kb(mod km)

2.Обидві частини конгруенції і модуль можна розділити на будь-який їх спільний множник d :

a º b (mod m); a = a1d; b = b1d , m = m1d

(a1d = m1dt + b1d ) × 1 a1 º b1 (mod m1 ) . d

36

3. Якщо a та b можуть бути конгруентними за декількома модулями m1 , m2 ,..., mn , то конгруенція a і b виконується і за

модулем, що дорівнює НСК(m1 ,m2 ,...,mn ):

a ≡ b(mod M ),

M = НСК(m1 , m2 ,..., mn ).

 

4. Якщо одна частина конгруенції і модуль діляться на деяке

число k , то й інша

її частина ділиться

на

це число:

a ≡ b(mod m), a = mt + b,

c | a , c | m c | b (за

3

властивістю

подільності).

5.Якщо a ≡ b(mod m) то (a,m) = (b,m).

3.2.ПОВНА ТА ЗВЕДЕНА СИСТЕМИ ЛИШКІВ

3.2.1.ПОВНА СИСТЕМА ЛИШКІВ

Усі числа, які мають однакову остачу r від ділення на деякий модуль m створюють клас чисел за модулем m . Усі числа цього класу можна отримати з формули ділення числа із

остачею a = m × q + r ,

якщо надавати неповній частці q

усіх

значень з множини цілих чисел.

 

 

k

різним остачам від ділення за модулем m k < m будуть

відповідати

k різних класів.

Модуль m за остачі може мати

числа

0, 1,

2,..., m − 1.

Отже,

кількість таких класів

за

довільним модулем m становить m .

Кожне число з певного класу має назву лишок відносно усіх інших чисел класу. Якщо q = 0 , то лишок r називається

найменшим додатним лишком числа a за модулем m .

Найменший лишок за абсолютною величиною називається

абсолютно найменшим лишком числа a за модулем m і

позначається δ .

Приклад

Візьмемо за модуль число m = 7 . Тоді найменшими

37

додатними лишками будуть числа 1, 2, 3, 4, 5, 6 . Для кожного з них можна записати клас чисел за модулем 7:

a1 = 7 × q1 +1 a1 º 1(mod 7),

a4

= 7 × q4

+ 4 a4

º 4(mod 7),

a2

= 7 × q2 + 2 a2

º 2(mod 7), a5

= 7 × q5

+ 5 a5

º 5(mod 7),

a3

= 7 × q3 + 3 a3

º 3(mod 7)

a6

= 7 × q6

+ 6 a6

º 6(mod 7)

При цьому, створюючи відповідний клас i, (i = 1,6), неповна частка qi проходить всю множину цілих чисел.

Абсолютно найменшими лишками за модулем 7 будуть числа − 3 = 4 − 7 , − 2 = 5 − 7 , − 1 = 6 − 7 , 0, 1, 2, 3 .

Якщо порівняти їх з найменшими додатними лишками,

можна

помітити, що

для лишків r <

m

=

7

d = r , а для

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2

2

 

r >

m

=

7

 

 

 

d = r - m .

 

 

 

 

 

 

 

 

2

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Таким способом будується множина абсолютно найменших

лишків

за

будь-яким

модулем. Якщо модуль m є парним

числом,

то для r =

 

m

 

 

можна за абсолютно найменший лишок

 

 

 

 

 

 

 

 

2

 

 

 

 

 

 

 

брати або

m

, або -

m

.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2

2

 

 

 

 

 

 

 

Якщо з кожного класу лишків узяти по одному числу, то отримана система чисел має назву повна система лишків. Кількість членів повної системи лишків за модулем m є m . Звернемо увагу на те, що числа з двох різних класів

неконгруентні, оскільки мають різні залишки від ділення на модуль m .

Найменші додатні лишки 0, 1, ..., m −1 становлять повну систему найменших додатних лишків. Абсолютно найменші

лишки -

m −1

,...,-1, 0, 1,...,

m −1

для m непарного і

 

 

2

2

 

38

m

 

 

m

 

 

 

 

 

 

 

−

 

 

−1 ,...,−1,0,1,...,

 

 

для

m

парного становлять

повну

 

 

 

2

 

 

2

 

 

 

 

 

 

 

 

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

 

 

 

Узагальнення

 

 

 

 

 

 

 

 

 

 

1.

Будь-які

m

чисел,

які

попарно

не

конгруентні за

модулем m становлять повну систему

лишків за цим

модулем.

 

 

 

 

 

 

 

 

 

 

2.

Якщо (a, m) = 1 і у виразі

ax + b, b Z

x проходить усі

значення повної

системи

лишків за модулем m , то

ax + b

набуває усіх значень повної системи лишків.

 

 

Приклад

 

 

 

 

 

 

 

 

 

 

 

Перевірити,

 

чи

 

становить

сукупність

чисел

(9, 2,16, 20, 27, 39, 46, 85) повну систему лишків за модулем 8.

Розв’язання

Повна система лишків за модулем 8, складена з найменших додатних лишків, є (0, 1, 2, 3, 4, 5, 6, 7).

Необхідно впевнитися, що у сукупності чисел, наведеній в умові задачі, кожне число конгруентне за модулем 8 деякому числу цієї системи тільки один раз.

9 ≡ 1mod (8), 2 ≡ 2 mod (8), 16 ≡ 0 mod (8), 20 ≡ 4 mod (8), 27 ≡ 3mod (8), 39 ≡ 7 mod (8), 46 ≡ 6 mod (8), 85 ≡ 5 mod (8) .

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

3.2.2. ЗВЕДЕНА СИСТЕМА ЛИШКІВ

Згідно із властивістю лишків усі числа, які належать до одного класу лишків за модулем m мають з m однаковий найбільший спільний дільник:

39

a = m × q1 + r, b = m × q2 + r, (a, m) = (b, m).

Серед множини класів лишків за

певним модулем m

розглянемо такі

класи лишків, у яких

(m × qi + r, m) = 1 , тобто

класи , взаємно

прості з модулем m . Якщо взяти з кожного

такого класу по лишку, то складеться зведена система лишків за модулем m . Як правило зведену систему лишків виділяють з повної системи найменших додатних лишків, або з повної системи абсолютно найменших лишків.

Оскільки кількість чисел від 0 до m , взаємно простих з m , визначається функцією Ейлера j(m) , то відповідно і кількість

чисел у зведеній системі, і кількість класів, що відповідають зведеній системі, визначаються функцією Ейлера:

 

 

1

 

 

1

 

 

 

1

 

 

 

-

 

 

-

 

 

 

-

 

 

,

 

 

 

j(m) = m 1

 

1

 

 

×...× 1

 

 

 

 

p1

 

p2

 

 

pk

 

де p1 , p2 , ..., pk - прості числа з канонічного розкладання m .

Приклад 1

 

m =130 = 2 ×5 ×13, j(130) = (2 -1)(5 -1)(13 -1) = 48 ,

отже,

зведена система лишків за модулем 130 складається з 48 чисел, менших за 130 і взаємно простих з 130.

Приклад 2

m = 16 = 24 , j(16) = 24 - 23 = 8 , отже, зведена система лишків за модулем 16 складається з 8 чисел, менших за 16 і взаємно простих з ним. Ці числа такі: 1, 3, 5, 7, 9, 11, 13, 15 . Вони становлять зведену систему найменших лишків для числа 16.

Узагальнення

1. Будь-які j(m) чисел, попарно непорівнянні за модулем m та взаємно прості з модулем, створюють зведену систему лишків.

40

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