Учбово-методичний посібник для виконання лабораторних робіт з дисципліни „Основи теорії криптографії і криптоаналізу”, страница 18

-  Решето числового поля чисел (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]

1.3.12.  Квадратні корені по модулю n

Визначення 3.12.1. Якщо n – добуток двох простих чисел, то можливість обчислити квадратні корені по модулю n обчислювально еквівалентна можливості розкласти число n на множники. Іншими словами, той, хто знає прості множники числа n, може легко обчислити квадратні корені будь-якого числа по модулю n, але для будь-кого іншого таке обчислення виявиться таким же важким, як і розкладання на прості множники числа n. [6]

1.3.13.  Генерація простих чисел

Для алгоритмів з відкритими ключами потрібні прості числа. Генерація випадкових чисел з наступною спробою розкладання їх на множники – це неправильний спосіб пошуку простих чисел. Існують різні імовірнісні перевірки на простоту чисел, що визначають, чи є число простим, із заданим ступенем імовірності. За умови, що ця "ступінь імовірності" достатня велика, такі способи перевірки досить гарні. [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;

}

Тест Леманна