Главная | Обратная связь

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

Детерминированной зависимости распределения простых чисел не существует. Также не существует детерминированного алгоритма их генерации. Наилучшие результаты дают вероятностные тесты числа на простоту из которых на практике наиболее применим тест Рабина-Миллера [13]:

Выбрать для тестирования число p. Вычислить b – число делений p – 1 на 2 (то есть 2^b – это наибольшая степень числа 2, на которую делится p – 1). Затем вычислить m, такое, что p = 1 + 2^b · m.

1) Выбрать случайное число a, меньшее p.

2) Установить j = 0 и z = a^m mod p.

3) Если z = 1 или если z = p – 1, то p проходит тест и может быть простым числом.

4) Если j > 0 и z = 1, то p не относится к простым числам.

5) Установить j = j + 1. Если j < b и z ¹ (p – 1), установить z = z² mod p и вернуться к шагу 4). Если z = p – 1, то p проходит тестирование и может быть простым числом.

6) Если j = b и z ¹ (p – 1), то p не относится к простым числам.

Считается, что число, прошедшее тест пять раз с вероятностью более 95% является простым.

Задача 2.4. Провести тест простоты Рабина-Миллера для числа p при помощи заданного числа a.

Пример решения.

Дано: p = 241 a = 99	Решение:
Повести тест простоты

Варианты заданий ко второй части