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

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

1) .

2) .

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

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

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

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

,

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

1) .

2) .

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

 






Дата добавления: 2016-06-15; просмотров: 279; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2017 год. Материал предоставляется для ознакомительных и учебных целей. | Обратная связь
Генерация страницы за: 0.006 сек.