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

Для генерації великих простих чисел в ГОСТ 34.310 використовується процедура, що базується на наступній теоремі: Нехай , де q — непарне просте, и N – парне число, . Число p є простим, якщо виконуються наступні умови:

1) .

2) .

Алгоритм генерації простого числа має побудований наступним чином.

Нехай потрібно побудувати просте число довжиною . Для цього будуємо убиваючий набір натуральних чисел , де та , для яких виконується умова .

Далі, послідовно формуються прості числа , при цьому для довжина дорівнює значенню . Вихідне значення обирається як випадкове просте число шляхом перевірки на простоту випадкових чисел за методом решета Ератосфена.

Генерація випадкового простого числа за допомогою простого здійснюється по формулі:

,

де N – випадкове парне число, таке, що довжина числа дорівнює значенню . Число вважається побудованим, якщо одночасно виконані умови теореми 1) та 2):

1) .

2) .

Якщо хоча б одна з умов не виконана, то значення N збільшується на 2, обчислюється нове значення , яке знову ж тестується щодо відповідності обом вказаним умовам. Така процедура виконується поки не буде отримане просте число .