Тема: Алгоритм Міллера-Рабіна і мала теорема Ферма
У багатьох випадках потрібно з'ясувати, чи є велике число n простим. Наприклад, у системі відкритого ключа RSA і різних системах, заснованих на завданні дискретного логарифмування в кінцевих полях, нам потрібно знайти велику "випадкове" просте число.
Тест на простоту являє собою критерій того, що число n не є простим. Якщо n "Проходить" цей тест, то воно, можливо, просте число. Якщо воно "Проходить" цілий набір тестів на простоту, то досить імовірно, що воно дійсно є простим. З іншого боку, якщо n не проходить хоча б одного тесту на простоту, то воно зовсім виразно є складовим. Однак при цьому залишається невирішеною важке завдання знаходження простих дільників числа n (задача факторизації). У загальному випадку для розкладання на множники великого числа, про якому відомо, що воно складене (оскільки вона не пройшла тесту на простоту), потрібно близько величини. Надійність криптосистеми RSA грунтується на тому припущенні, що значно легше знайти два надзвичайно великих простих числа n і q , ніж, знаючи n = p * q , але не p або q , знайти подільники числа n .
Псевдопростие числа
Нехай n - велике непарне число, і ми хочемо визначити чи є n простим.
Теорема (Ферма). Якщо n - просте число, то відповідно до малої теоремі Ферма для будь-якого такого b , що НСД ( b, n) = 1, . (1)
Якщо n - не проста число, то (1) теж може виконуватися (хоча це малоймовірно).
Визначення. Якщо n - непарне складене число, b - ціле число, НСД ( n, b) = 1 , і (1) виконується, то n називається псевдопростим числом по підставі b .
Іншими словами, "псевдопростое" число - це число n , яке "претендує" бути простим, проходячи тест (1).
Приклад 1. число n = 91 - псевдопростое по підставі b = 3 , так як. Однак, 91 не їсти псевдопростое число по підставі 2, так як. Якби ми ще не знали, що 91 складене число, то співвідношення довело б нам це.
Сильно псевдопростое число. Розглянемо тепер ще один вид критеріїв простоти, який у певному сенсі навіть краще тесту Соловея - Штрассена, заснованого на визначенні псевдо простати по Ейлера. Це тест Міллера-Рабіна, заснований на вводимом нижче понятті "сильно псевдо простати". Припустимо, що n - велике непарне натуральне число і. Нехай, далі, n - псевдопростое по підставі b, тобто . Ідея критерію сильної псевдо простати така. Нехай, t - непарній. Якщо послідовно обчислювати, то при простому n першим елементом, відмінним від 1, має бути елемент
1, так як при простому n єдиними рішеннями порівняння є +1 та-1. практично дії виконуються "у зворотному напрямку". Вважаємо, t - непарній. Обчислюємо за модулем n. Якщо, будуємо в квадрат за модулем n, отримуємо, потім знову зводимо в квадрат і т.д. до тих пір, поки не отримаємо 1:. Тоді, якщо n - просте, попереднім числом має бути - 1, в іншому випадку ми отримуємо доказ того, що n складене.
Визначення. Нехай n - непарне складене число і n-1 = 2 s t, t - непарній. Нехай. Якщо n і b задовольняють одну з умов:
1);
2) існує таке r,, що
(2)
то n називає сильно псевдопростим по підставі b.
Тест Міллера-Рабіна. Припустимо, що ми хочемо визначити, є велике натуральне число n простим або складеним. Уявімо n-1 у вигляді, t непарній, і виберемо випадкове ціле число b, 0
Застосування цих теорем можна побачити в наступних алгоритмах:
Алгоритм RSA
RSA (від прізвищ криптографів Rivest, Shamir і Adleman) криптографічний алгоритм шифрування з відкритим ключем і цифровий підписом.
Криптографічні системи з відкритим ключем використовують односпрямовані функції, які мають властивість:
Якщо х відомо, то f (x) обчислити відносно просто
Якщо відомо y = f (X), то для x немає простого шляху обчислення
Під одне спрямованістю розуміється практична неможливість обчислити зворотне значення, використовуючи сучасні обчислюва...
