Генерація простих чисел
Для генерації великих простих чисел в ГОСТ 34.310 використовується процедура, що базується на наступній теоремі: Нехай , де q — непарне просте, и N – парне число, . Число p є простим, якщо виконуються наступні умови:
1) .
2) .
Алгоритм генерації простого числа має побудований наступним чином.
Нехай потрібно побудувати просте число довжиною . Для цього будуємо убиваючий набір натуральних чисел , де та , для яких виконується умова .
Далі, послідовно формуються прості числа , при цьому для довжина дорівнює значенню . Вихідне значення обирається як випадкове просте число шляхом перевірки на простоту випадкових чисел за методом решета Ератосфена.
Генерація випадкового простого числа за допомогою простого здійснюється по формулі:
,
де N – випадкове парне число, таке, що довжина числа дорівнює значенню . Число вважається побудованим, якщо одночасно виконані умови теореми 1) та 2):
1) .
2) .
Якщо хоча б одна з умов не виконана, то значення N збільшується на 2, обчислюється нове значення , яке знову ж тестується щодо відповідності обом вказаним умовам. Така процедура виконується поки не буде отримане просте число .
Дата добавления: 2016-06-15; просмотров: 1351;