Застосування теорії чисел в криптографії

Страницы работы

Содержание работы

ЗМІСТ

Стор.

1 Подільність цілих чисел. 3

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

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

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

1.4 Прості числа. 5

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

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

2 Найважливіші функції в теорії чисел. 10

2.1 Функції виділення цілої та дробової частини дійсного числа. 10

2.2 Мультиплікативні функції. 10

3 Порівняння (конгруенції). Властивості порівнянь. 13

3.1 Основні поняття та теореми. 13

3.2 Повна та зведена системи лишків. 15

3.3 Повні та зведені системи лишків, як структури теорії груп. 17

4 Конгруенції з одним невідомим. 19

4.1 Основні відомості. 19

4.2 Конгруенції першого степеня. 20

4.3 Обернений елемент за множенням. 23

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

5. Конгруенції n-го степеня. 26

5.1 Конгруенції n-го степеня за простим модулем. 26

5.2 Кількість коренів конгруенції -го степеня за простим модулем. 29

5.3 Конгруенції n-го степеня за складеним модулем. 30

5.4 Конгруенції 2-го степеня . Ошибка! Закладка не определена.

5.5 Квадратична конгруенція за простим непарним модулем .. Ошибка! Закладка не определена.

5.6 Символ Лежандра. Ошибка! Закладка не определена.

5.6 Символ Якобі. Ошибка! Закладка не определена.


1 Подільність цілих чисел.

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

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

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

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

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

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

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

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

2.  Якщо  та , то .

3.  Якщо  та , то .

4.  Узагальнення: якщо у рівності  про всі числа, крім одного відомо, що вони кратні числу , то і це останнє є кратним .

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

,

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

Очевидно, що за умови   є повна частка, а .

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

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

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

1. Будь яке ціле , яке одночасно ділить числа  носить назву спільного дільника цих чисел. Найбільший із всіх дільників носить назву найбільший спільний дільник (НСД) та позначається

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

Приклад: Числа 6, 10, 15 – взаємо прості, бо , але вони не попарно прості. Числа 7, 13, 23 – попарно прості, бо , і одночасно вони взаємо прості.

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

1. Якщо , то  і кількість дільників у чисел  та  співпадає з кількістю дільників .

2. Якщо , то кількість дільників  співпадає із кількістю спільних дільників  та , зокрема

 ( витікає з властивості 4. п.1.1)

3. Якщо

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

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

Останнє ділення – ділення без залишку, тобто

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

Отже,

-  сукупність дільників  та  співпадає з сукупністю дільників їх НСД.

-  НСД  та  дорівнює останньому ненульовому залишку в ланцюжку ділень за алгоритмом Евкліда.

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

Спільний дільник двох довільних цілих чисел  можна єдиним способом подати лінійною комбінацією цих чисел:

,  одночасно.

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

Приклад: 1. Знайти НСД a=648 та b=261. 2. Знайти .

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

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

Останній ненульовий залишок - . Отже,

2. Шукаємо подання НСД лінійною комбінацією:

Отже

Деякі властивості НСД:

1.  Якщо .

2.  Якщо , зокрема , тобто два будь яких цілих числа, поділених на НСД цих чисел є взаємо простими числами.

3.  Якщо ;

4.  Якщо ;

5.  Якщо  взаємо прості з кожним з , то добуток  взаємо простий з добутком

Похожие материалы

Информация о работе

Предмет:
Криптография
Тип:
Конспекты лекций
Размер файла:
2 Mb
Скачали:
0