- Решето числового поля чисел (Number field sieve, NFS). Решето загального числового поля – це найшвидший з відомих алгоритм для чисел розміром 110 і більш розрядів. У своєму первісному вигляді він був непрактичний, але за останні кілька років він був послідовно поліпшений. Рання версія використовувалася для розкладання на множники дев'ятого числа Ферма: 2512+1.
- Квадратичне решето (Quadratic sieve, QS). Це найшвидший з відомих і найчастіше використовуваний алгоритм для чисел, довжина яких менше 110 десяткових розрядів. Більш швидка версія цього алгоритму називається множинним поліноміальним квадратичним решетом. Найшвидша версія називається подвійною варіацією множинного поліноміального квадратичного решета з великим простим числом.
- Метод еліптичної кривої (Elliptic curve method, ECM). Цей метод використовувався для пошуку не більш ніж 43-розрядних множників.
- Алгоритм Монте-Карло Полларда (Роllаrd's Monte Carlo algorithm). (Цей алгоритм також приведений у Кнута в томі 2 [13].)
- Алгоритм безперервних дробів (Continued fraction algorithm). Цей алгоритм не підходить по часу виконання.
- Перевірка розподілом (Trial division). Цей самий старий алгоритм розкладання на множники складається з перевірки кожного простого числа, меншого або рівного квадратному кореневі з числа, що розкладається.
Якщо число n на множники розкладається, то евристичний час виконання найшвидших варіантів QS асимптотично дорівнює:
NFS набагато швидше, оцінка його евристичного часу виконання:
У 1970 році було розкладено на множники 41-розрядне важке число. ("Важким" є таке число, у якого немає маленьких множників, і яке не має спеціальну форму, що дозволяє спростити процес.) Десять років потому розкладання в два рази більш довгого числа зайняло лише кілька годин на комп'ютері Cray. [1]
У 1988 році Карл Померанс (Carl Pomerance), використовуючи звичайні ЗВІС, спроектував пристрій для розкладання на множники. Розмір числа, яке можна було розкласти, залежав тільки від розмірів пристрою, який так і не був побудований.
У 1993 році за допомогою квадратичного решета було розкладено на множники 120-розрядне важке число. Розрахунок, що потребував 825 MIPS-років, був виконаний за три місяці реального часу.
Сьогодні для розкладання на множники використовуються комп'ютерні мережі. Для розкладання 116-розрядного числа Аржен Ленстра (Arjen Lenstra) і Марко Манасс (Mark Manasse) протягом декількох місяців використовували вільний час масиву комп'ютерів, розкиданих по усьому світі, що склало 400 MIPS-років.
У березні 1994 року за допомогою подвійної варіації множинного поліноміального QS командою математиків під керівництвом Ленстри було розкладено на множники 129-розрядне (428-бітове) число. Трудомісткість обчислень була в діапазоні від 4000 до 6000 MIPS-років. Комп'ютери з'єднувалися по електронній пошті, передаючи свої результати в центральне сховище, де виконувався остаточний аналіз. [6]
Майбутній розвиток NFS, очевидно, буде відбуватися у формі зменшення константи: 1,923. Для ряду чисел спеціальної форми, таких як числа Ферма, константа наближається до 1,5. Якби для важких чисел, використовуваних у сьогоднішній криптографії, константу теж можна було знизити до цього рівня, то 1024-бітові числа розкладалися б на множники вже сьогодні. Одним із способів зменшити константу є виявлення кращих способів представлення чисел як поліномів з маленькими коефіцієнтами. [1]
Визначення 3.12.1. Якщо n – добуток двох простих чисел, то можливість обчислити квадратні корені по модулю n обчислювально еквівалентна можливості розкласти число n на множники. Іншими словами, той, хто знає прості множники числа n, може легко обчислити квадратні корені будь-якого числа по модулю n, але для будь-кого іншого таке обчислення виявиться таким же важким, як і розкладання на прості множники числа n. [6]
Для алгоритмів з відкритими ключами потрібні прості числа. Генерація випадкових чисел з наступною спробою розкладання їх на множники – це неправильний спосіб пошуку простих чисел. Існують різні імовірнісні перевірки на простоту чисел, що визначають, чи є число простим, із заданим ступенем імовірності. За умови, що ця "ступінь імовірності" достатня велика, такі способи перевірки досить гарні. [1]
Припустимо, що одна перевірка з 264 – помилкова. Це означає, що з імовірністю 1/1019 перевірка оголосить простим складене число. (Просте число ніколи не буде оголошено складеним при перевірці.) Якщо з якоїсь причини знадобиться велика вірогідність простоти числа, рівень помилки можна понизити.
Тест Соловея-Штрассена
Роберт Соловей (Robert Solovay) і Фолькер Штрассен (Volker Strassen) розробили алгоритм імовірнісної перевірки простоти числа. Для перевірки простоти числа p цей алгоритм використовує символ Якобі: [6]
1. Виберіть випадкове число a, менше p.
2. Якщо (а, p) ≠ 1, то p не проходить перевірку і є складеним.
3. Обчислите j = a(p-1)/2 mod р.
4. Обчислите символ Якобі J(a, p).
5. Якщо j ≠ J(a, p), то число p напевно не є простим.
6. Якщо j = J(a, p), то імовірність того, що число p не є простим, не більше 50 відсотків.
Визначення 3.13.1. Число а, що не показує, що p напевно не є простим числом, називається свідком. [1]
Якщо p – складене число, імовірність випадкового числа a бути свідком не нижче 50 відсотків. Повторите цю перевірку t раз з t різними значеннями а. Імовірність того, що складене число переборе всі t перевірок, тоді не перевищує 1/2t.
Приведемо алгоритм мовою C++, що тестує число p на простоту, задану кількість разів: [6]
bool Solovay_Strassen_Test(unsigned long Iterations,unsigned long p)
{
Randomize();
unsigned long a=0;
for(unsigned long i=1;i<=Iterations;i++)
{
a=RandomRange(2,p);
if(NOD(a,p)!=1)return false;
if(PowerMod(a,(p-1)/2,p)!=Jacobi(a,p))return false; else return true;
}
return true;
}
Тест Леманна
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.