Зачастую криптостойкость алгоритмов шифрования с открытыми ключом существенно зависит от того, насколько велики простые числа.
Общая схема для большинства методов получения простых чисел состоит из следующих двух шагов:
1. Выбор большого нечетного числа.
2. Тестирование этого числа на простоту.
Если оно оказалось простым, то алгоритм заканчивает работу. Иначе перейти на шаг 1.
Существует два подхода к реализации второго шага:
§ Вероятностный тест (проверка простоты): с вероятностью 1 можно определить – является ли число составным; и только с вероятностью близкой к 1 можно определить случай простого числа.
Общая схема вероятностного подхода состоит в проведении некоторого эвристического теста над числом – кандидатом. С каждой новой итерацией теста увеличивается вероятность того, что число простое.
§ Детерминированный тест (построение больших простых чисел): результатом данного теста является доказуемое высказывание о том, что тестируемое число простое (составное).
Различные варианты тестов на простоту рассматриваются в лабораторной работе номер 6.