Генерація великих простих чисел
Найбільш ефективним засобом побудови простих чисел є дещо модифікована мала теорема Ферма.
Нехай N, S --- непарні натуральні числа, N-1 = S*R, причому для кожного простого дільника q числа S існує ціле число a таке, що
Тоді кожен простий дільник p числа N задовольняє порівняння p = 1(mod 2S)
Якщо виконані умови теореми Ферма та R N-1 =1(mod N), НОД(a R -1, N)=1.
Якщо при обраному a ці співвідношення виконуються, то, згідно з слідством теореми Ферма, можна стверджувати, що число N просте. Якщо ж ці умови порушуються, потрібно вибрати інше значення a і повторювати ці операції, доки таке число не буде виявлено.
Припустимо, що побудоване число N справді є простим. Задамося питанням, наскільки довго доведеться перебирати числа a, доки не буде знайдено таке, для якого будуть виконані умови (12). Зауважимо, що для простого числа N перша умова (12), відповідно до малої теореми Ферма, виконуватиметься завжди. Ті самі числа a, котрим порушується друга умова (12), задовольняють порівнянні a R =1(mod N). Як відомо, рівняння x R =1 у полі відрахувань Fn має трохи більше R рішень. Одне їх x=1. Тому на проміжку 1 -1 ) знайти число a, для якого будуть виконані умови теореми Ферма, і тим довести, що N дійсно є простим числом.
Зауважимо, що побудоване у такий спосіб просте число N задовольнятиме нерівності N>S 2 , тобто. буде записуватися вдвічі більшою кількістю цифр, ніж вихідне просте число S. Замінивши тепер число S на знайдене просте число N і повторивши з цим новим S всі вищезазначені дії, можна побудувати ще більше просте число. Почавши з якогось простого числа, скажімо, записаного 10десятковими цифрами (простоту його можна перевірити, наприклад, розподілом на малі табличні прості числа), і повторивши зазначену процедуру достатню кількість разів, можна побудувати прості числа потрібної величини.
Обговоримо тепер деякі теоретичні питання, що виникають у зв'язку зі знаходженням числа R, що задовольняє нерівності S C де C - деяка досить велика абсолютна постійна. У припущенні справедливості розширеної гіпотези Рімана можна довести, що найменше таке просте число не перевищує c(e)*S 2+e за будь-якого позитивного e.
Таким чином, в даний час немає теоретичних гарантій для існування простого числа N=SR+1, S 38/61+e ), що, звичайно, не дуже добре для наших цілей. Разом про те існує так звана гіпотеза Крамера (1936г.), що pn+1-pn=O(ln 2 pn), дає цілком прийнятну оцінку. Приблизно такий самий результат випливає з розширеної гіпотези Рімана. Обчислення на ЕОМ показують, що найпростіші числа в арифметичних прогресіях розташовані досить щільно.
Як результат обговорення у цьому пункті підкреслимо наступне: якщо взяти на віру, що найменше просте число, а також відстань між сусідніми простими числами в прогресії 2Sn+1 при S 2 S), то описана схема побудови великих простих чисел має поліноміальну оцінку складності. Крім того, незважаючи на відсутність теоретичних оцінок часу роботи алгоритмів, що відшукують прості числа в арифметичних прогресіях з порівняно великою різницею, на практиці ці алгоритми працюють цілком задовільно. На звичайному персональному комп'ютері без особливих витрат часу будуються у такий спосіб прості числа 10 300 .
Звичайно, спосіб конструювання простих чисел для використання у схемі RSA має бути масовим, асамі прості числа мають бути в якомусь сенсі добре розподіленими. Це вносить низку додаткових ускладнень у роботу алгоритмів. Втім, описана схема припускає масу варіацій.
Нарешті, відзначимо, що існують методи побудови великих простих чисел, що використовують не тільки прості дільники N-1, а й дільники чисел N+1, N2+1, N2+-N+1$. В їх основі лежить використання послідовностей цілих чисел, що задовольняють лінійним рекурентним рівнянням різних порядків. Зазначимо, що послідовність a n , члени якої є у формулюванні малої теореми Ферма, становить рішення рекурентного рівняння першого порядку un+1=aun, u0=1.