Файл: Zastosuvannya_teoriyi_chisel_u_kriptografiyi_metodi.pdf

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ

СУМСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ

3108 Методичні вказівки з дисципліни «Застосування теорії

чисел у криптографії»

для студентів спеціальностей «Інформатика» та «Прикладна математика» заочної форми навчання

Суми

Сумський державний університет

2011

3

Методичні вказівки з дисципліни «Застосування теорії чисел у криптографії» / укладач О. І. Оглобліна. – Суми: Сумський державний університет, 2011. – 65 с.

Кафедра прикладної та обчислювальної математики

4

ТЕМА 1 ПОДІЛЬНІСТЬ ЦІЛИХ ЧИСЕЛ

1.1. Основні поняття і теореми.

1.2 Найбільший спільний дільник (НСД).

1.3.Найменше спільне кратне (НСК).

1.4.Ознаки подільності чисел.

1.5.Неперервні дроби.

1.1. ОСНОВНІ ПОНЯТТЯ І ТЕОРЕМИ

Означення

Для довільних цілих чисел a і b визначається, що b ділить a , якщо існує таке ціле число q , для якого виконується рівність

a = b × q

Позначається цей факт так: b | a . При цьому b називається

додатний дільник a , відмінний від a . Нетривіальним дільником a називається будь-який додатний дільник a , який не дорівнює 1 або a .

Простим числом називається таке ціле число, яке має за дільники тільки 1 та a . Ціле число, яке має хоча б один нетривіальний дільник, називається складеним числом.

Властивості подільності цілих чисел

1.Якщо b | a і c - будь-яке додатне ціле число, тоb | a ×c .

2.Якщо b | a та c | b , то c | a .

3.Якщо b | a та b | c , то b | a + c .

4. Узагальнення: якщо у рівності k + l + ... + n = p + q + ... + s про всі числа, крім одного відомо, що вони кратні деякому числу b , то і останнє число є кратним b .

3

Теорема про ділення з остачею. Будь-яке ціле число a єдиним способом подається за допомогою додатного цілого числа b рівністю:

a = b × q + r, 0 £ r < b ,

де q - неповна частка, r - остача.

1.2.НАЙБІЛЬШИЙ СПІЛЬНИЙ ДІЛЬНИК (НСД).

1.Будь-яке ціле di , яке одночасно ділить числа a, b,...., l ,

називають спільним дільником (СК) цих чисел. Найбільший із усіх дільників має назву найбільший спільний дільник (НСД)

та позначається d = (a, b,...., l ) .

2. Якщо (a, b,...., l ) = 1, то числа a, b,...., l - взаємно прості,

якщо кожне число з наведеного набору є взаємно простим з кожним іншим числом цього набору, то ці числа – попарно прості. Попарно прості числа є одночасно і взаємно простими,

але не навпаки.

Приклад

Числа 6, 10, 15 – взаємно прості, оскільки (6,10,15) = 1, але вони не попарно прості. Числа 7, 13, 23 – попарно прості, оскільки (7,13) = (7, 23) = (13, 23) = 1 , і одночасно вони взаємно прості.

НСД двох цілих чисел а і b.

1. Якщо b | a , то (a, b) = b і кількість дільників у чисел a

та b збігається з кількістю дільників b .

2. Якщо a = bq + r , то кількість дільників a збігається із кількістю спільних дільників b та r , зокрема

(a, b) = (b, r ) (витікає з властивості 4. п.1.1).

3. Якщо a0 = cq0 + r0 , a1 = cq1 + r1 ,..., an = cqn + rn

4

(a0 , a1 ,..., an , c) = (c, r0 , r1,...rn ) .

Алгоритм Евкліда для знаходження НСД двох чисел a і b

Цей алгоритм ґрунтується на попередніх твердженнях. Розглянемо a та b , причому a ³ b . Тоді можна записати обмежений ланцюжок ділень із остачею:

Досліджуючи цей ланцюжок з останнього ділення уверх, отримаємо

rn | rn−1 rn | rn−2 (rn−2 , rn−1 ) = rn ;

rn | rn−2 rn | rn−3 (rn−3 , rn−2 ) = (rn−2 , rn−1 ) = rn ;

.......................................

Отже, з вищеподаного випливає:

–сукупність дільників a та b збігається зі сукупністю дільників їх НСД;

–НСД a та b дорівнює останній ненульовій остачі в

ланцюжку ділень за алгоритмом Евкліда.

1.3. НАЙМЕНШЕ СПІЛЬНЕ КРАТНЕ (НСК).

Подані числа a1 , a2 ,..., am . Довільне число, що є кратним кожному з даних чисел, називається спільним кратним (СК)

5

цих чисел. Найменше з чисел, кратних поданому набору чисел,

називається їх найменшим спільним кратним (НСК).

Позначення НСК

m = [a1 , a2 ,..., am ] .

Остання ненульова остача r2 = 9 .

6

Отже, d = (648, 261) = 9 .

2. m = [648, 261] знайдемо, використавши формулу (1),

= [ ] = 648 × 261 = 169128 =

m 648, 261 18792 .

Відповідь: d = (648, 261) = 9, m = [648, 261] = 18792 .

Приклад 2

Знайти d = (420,126, 525) .

Розв’язання

Для знаходження найбільшого спільного дільника трьох чисел використаємо властивість 3.

а) Найменшим з чисел 420, 126 і 525 є число 126. Ділимо два інших числа на 126 і визначаємо остачу від ділення:

б) За властивістю 3 (525, 420, 126) = (126, 42, 29) .

Найменше число – 29.

126 = 4 × 29 +10 ;

29

42 = 1× 29 +13.

29 в) За властивістю 3 (525, 420, 126) = (126, 42, 29) = (29,13,10) .

Оскільки числа 29 і 13 – прості, то (29,13,10) =1. А це означає, що (525, 420, 126) =1 .

Відповідь: задані числа є взаємно простими.

7