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

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

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

ЗАСТОСУВАННЯ ТЕОРІЇ ЧИСЕЛ У КРИПТОГРАФІЇ

КОНСПЕКТ ЛЕКЦІЙ

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

Суми Видавництво СумДУ

2010

2

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

Питання 1 Основні поняття та теореми. Питання 2 Найбільший спільний дільник (НСД). Питання 3 Найменше спільне кратне (НСК).

Питання 4 Прості числа. Єдиність розкладання довільного цілого числа на прості множники.

Питання 5 Ознаки подільності чисел. Питання 6 Неперервні дроби.

Ключові терміни

Цілі числа, дільник, кратне, власний дільник, нетривіальний дільник, просте число, складене число, неповна частка, залишок, спільний дільник, найбільший спільний дільник, взаємно прості числа, попарно прості числа, спільне кратне, найменше спільне кратне, алгоритм Евкліда, решето Ератосфена, канонічне розкладання, кількість дільників, неперервний дріб, підходящі дроби.

Питання 1 Основні поняття та теореми.

Теорія чисел розглядає цілі числа, тобто числа класу Z = 0,±1,±2... . та властивості цих

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

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

a = b × q

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

таких умов кратне числу b .

Інший запис подільності числа a на число b – aMb . Читається цей запис так: число a ділиться на число b без залишку і відповідає рівності

a = q Z b

Власний дільник числа a - будь-який додатний дільник 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 .

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

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

де q - неповна частка, r - залишок

Очевидно, що за умови r = 0 q є повна частка, а b | a .

3

Якщо просте число p є неоднократним дільником довільного цілого числа a (число a ділиться на p α -разів, α - ціле невід’ ємне число), то цей факт будемо позначати так: p α | a . В цьому випадку p α | a , а p α+1

Приклади.

1. Відомо, що неповна частка q ділення числа a = 56839 на деяке невідоме ціле число b дорівнює 224. Знайти число b і залишок від ділення r .

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

Число a = 56839 єдиним способом можна подати так: a = b × q + r . Підставимо у цей вираз відомі числа.

В останній рівності про всі доданки, крім першого відомо, що вони діляться на l . За властивістю 4 подільності чисел маємо, що k n Ml теж, тобто l | k , хоча за припущенням

α= k - нескорочуваний дріб. Прийшли до протиріччя. l

Висновок:

Отже, якщо даний поліном має раціональний корінь, то він цілий.

3. Показати, що якщо п’ятизначне ціле число ділиться на 41, то всі числа, отримані перестановкою цифр цього числа по колу теж діляться на 41.

Розв’язання

Будь-яке п’ятизначне число подається в десятковій системі числення так

Переставимо по колу старшу цифру на останнє місце

Висновок:

4

Якщо довільне п’ятизначне ціле число ділиться на 41, то всі числа, отримані перестановкою цифр цього числа по колу теж діляться на 41.

4. Показати, що "n Î N 2n |(n +1)×(n + 2)×...×(2n)

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

Звернемо увагу, що даний добуток складає другу половину 2n!. Якщо цей добуток умножити та поділити на n!, отримаємо

(2n)! = 1× 2 ×3×...× 2n

n! n!

Перегрупуємо чисельник, записавши спочатку усі непарні числа, а потім усі парні.

(2n)! = 1×3×5 ×...×(2n -1)× 2 × 4 ×6 ×...× 2n = 1×3×5 ×...×(2n -1)× 2n (1× 2 ×3×...× n) =

Число 30 = 6 ×5 = 3!×5

Розглянемо надане у прикладі число і застосувавши до нього формули алгебраїчних перетворень, спробуємо виділити відповідні послідовності чисел:

m5 - m = m(m4 -1)= m(m2 -1)(m2 + 1)= (m -1)m(m + 1)(m2 - 4 + 5)= (m -1)m(m +1)(m2 - 4)+

+ 5(m -1)m(m + 1) = (m - 2)(m -1)m(m +1)(m + 2) + 5(m -1)m(m + 1)

Упершому доданку маємо добуток 5-ти послідовних чисел. Тобто перший доданок ділиться націло на 5! = 120 = 30 × 40 . Перший доданок на 30 ділиться.

Удругому доданку маємо добуток послідовних 3-х чисел та числа 5, тобто другий доданок ділиться на 3!×5 = 6 ×5 = 30

Висновок: Обидва доданки розкладання числа m5 - m діляться на 30, отже і само число ділиться на 30.

Питання 2 Найбільший спільний дільник (НСД).

Не звужуючи загальної теорії будемо у подальшому розглядати тільки додатні дільники чисел.

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

(СК) цих чисел. Найбільший із всіх дільників носить назву найбільший спільний дільник (НСД) та позначається d = (a, b,...., l )

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

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

5

Приклад: Числа 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 (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 дорівнює останньому ненульовому залишку в ланцюжку ділень

за алгоритмом Евкліда. Узагальненням алгоритму Евкліду буде теорема:

Спільний дільник двох довільних цілих чисел d = (a,b) можна єдиним способом подати лінійною комбінацією цих чисел:

d = ax + by, x, y Î Z , x ¹ 0, y ¹ одночасно.

Доведення теореми витікає з алгоритму Евкліду, якщо всі залишки, починаючи з rn = d поступово виразити через попередні залишки, а потім і через a та b .

Приклад:

1. Знайти НСД a=648 та b=261. 2. Знайти x, y : d = ax + by .

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

1. Шукаємо НСД

6