|
2. Прості і взаємно прості числа. Дискретний логарифм і первісні корені. Будуть потрібні для розуміння і дослідження двоключових (несиметричних) криптоалгоритмів і криптосистем, а також криптографічних протоколів на їх основі.
2.1. Прості числа.
Натуральне число а, більше 1, називається простим, якщо воно не має натуральних дільників, відмінних від 1 і самого числа а. Кількість простих чисел нескінченна.
Приклад. Початок множини простих чисел, які менші за 100:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, . . . . .
Взагалі, кількість Р простих чисел, менших N, приблизно дорівнює
N / (In N).
Як видно з наведеного вище прикладу, при N = 100, кількість простих чисел, менших 100 дорівнює точно 25 (від 2 до 97). А за оціночною формулою маємо:
N = 100, In N 4.6, Р = N / (In N) 22
Ще приклади:
N = 1000, In N 4.6, Р = N / (In N) 145
N = 10000, In N 9.2, Р = N / (In N) 1087
Доведено, що будь-яке натуральне число, відмінне від 1, є або простим, або може бути представлено у вигляді добутку простих чисел однозначно з точністю до порядку співмножників в добутку (це – так звана основна теорема арифметики).
Приклад: 969 = 3*17*19;
Звернімо особливу увагу на таке. Навіть якщо співмножники – дуже великі числа, обчислення їх добутку принципово не складна задача: існують і розроблені ефективні алгоритми її вирішення.
Але на сьогодні поки що не винайдено достатньо ефективних алгоритмів розкладання довільного цілого числа на прості множники навіть тоді, коли відомо, що воно розкладається в добуток двох простих простих чисел.
Відсутність ефективних алгоритмів з доказовими оцінками складності дозволило покласти проблему розкладання натуральних чисел на прості множники в основу деяких несиметричних криптографічних систем, зокрема, RSA і обґрунтувати їх практичну криптостійкість.
Підмножину простих чисел, які не перевищують заданого N, починаючи з 2, можна сформувати з множини натуральних чисел, використовуючи алгоритм, який відомий як Решето Ератосфена. За допомогою цього алгоритму можна створити таблицю простих чисел потрібного розміру. Подивитися наочне графічне пояснення роботи Решета Ератосфена і приклади його реалізації на Java та Python можна за адресою https://habr.com/ru/post/333350/
При реалізації несиметричних криптоалгоритмів для забезпечення їх надійності (криптостійкості) потрібні дуже великі прості числа. Тому на практиці для вибору простого числа потрібного розміру можна послуговуватися не таблицею простих чисел, а діяти в інший спосіб.
Припустимо, потрібно обрати просте число Р певної розрядності. Для цього можна обирати непарне число N відповідної розрядності і перевірити, чи є воно простим. Для цього застосовуються так звані тести на простоту.
Один з тестів виконується шляхом повного перебору всіх можливих потенційних дільників даного обраного числа N. Якщо при виконанні тесту окрім 1 і самого N знайдеться хоча-б ще один дільник, то N не просте. Тоді слід обирати інші числа N', N'', N'''. . . і тестувати їх доти, доки не поточне з них не пройде тест.
Опис простішого алгоритму.
Виконується перебір усіх цілих чисел від 2 до числа j, яке дорівнює квадратному кореню з N (з округленням у більшу сторону) і обчисленні залишку від ділення N на кожне з цих чисел j. Якщо залишок від ділення на поточне число j дорівнює 0, то j є дільником N. У цьому випадку N оголошується не простим (складеним), і алгоритм закінчує роботу. Після досягнення j значення квадратного кореня з N і виявленій неможливості скоротити N ні на одне з чисел j, N оголошується простим і алгоритм закінчує роботу.
Завдання 4. Розробіть на Python:
1) допоміжну функцію testprime (N), де N – число, яке перевіряється на простоту. Функція повинна повертати ознаку простоти n, наприклад 0, якщо N – непросте, або 1, якщо N – просте.
2) функцію theprime (N1, N2) пошуку простого числа Р, яка виконує цикл перевірки чисел на простоту з використанням функції testprime (N) в межах діапазону [N1, N2] доти, доки не буде знайдено перше ж просте Nі [N1, N2], яке і буде прийматися як шу́кане Р.
2.2. Взаємно прості числа.
Два числа називаються взаємно простими, якщо вони не мають жодного спільного дільника окрім одиниці.
Приклад. Числа 27 і 28 взаємно прості (у них немає спільних дільників крім одиниці), а числа 27 і 33 - ні (у них є спільний дільник 3).
Нехай а і b - два цілих позитивних числа. Найбільший спільний дільник (НСД) чисел а і b є найбільше число с, яке ділить і а і b:
Do'stlaringiz bilan baham: |
