Во многих ассиметричных алгоритмах шифрования требуется применение простых чисел с длиной сотни, а иногда и тысячи бит. Генерация простого числа такой длины (за приемлемое время) является задачей нерешенной. Вместо этого поступают, как правило, следующим образом.
1. Генерируется битовая строка требуемой длины со случайным набором бит (0 или 1).
2. Первый и последний бит устанавливается равным 1.
3. Полученное число n тестируется на простоту.
При тестировании на простоту можно попытаться применить алгоритмы разложения числа n на множители и, если среди множителей только единица и само число, то сделать вывод, что число простое. Однако рассмотренные выше и известные на текущий момент алгоритмы разложения также неприемлемы по времени. Для проверки простоты числа существуют детерминированные и вероятностные тесты. Некоторые детерминированные тесты простоты:
- перебор возможных делителей;
- тест Миллера;
- решето Эратосфена;
– полиномиальный тест распознавания простоты;
- и др.
Перебор делителей
Аналогичен алгоритму факторизации числа n. Выполняется перебор всех возможных потенциальных делителей от 2 до 
. При нахождении числа из этого диапазона, делящего n на цело, поиск прекращается, т.к. n - составное.
Тест Миллера
Тест базируется на числах, называемых свидетелями простоты. Пусть n - нечётное число большее 1. Число n - 1 однозначно представляется в виде n – 1 = 2k * q, где q нечётно (например, n = 561, тогда n – 1 = 560 = 24 * 35). Целое число b, называется свидетелем простоты числа n, если выполняется условие:
bq mod n = 1, (8.5)
или существует s (0 ≤ s < k) такое, что
mod n = n - 1, (8.6)
По гипотезе Римана, если n – составное число, тогда найдется b < 2 ln2n1, которое не будет являться свидетелем простоты. Проверка одного основания b не дает стопроцентной гарантии простоты n. Например, тест для числа n = 2047 = 23 * 89 по основанию b = 2 будет говорить о том, что n – простое. Для стопроцентной уверенности необходимо проверить все свидетели простоты от 2 до 2 ln2n. Для числа n = 60000 число проверяемых свидетелей простоты примерно равно числу проверяемых делителей по процедуре с полным перебором от 2 до (≈ 240). Учитывая простоту теста с перебором делителей, он более эффективен с вычислительной точки зрения, чем тест Миллера. Однако при n = 109 + 1 (1110111001 1010110010 1000000001)2, при полном переборе делителей необходимо проверить ≈ 31600 делителей, а по тесту Миллера ≈ 860. Сравните n с рекомендованными для RSA числами, длиной в 1028 бит.
Если положительное нечетное целое число n составное, а тест Миллера для одного b (1 < b < n – 1) его не распознал, то оно называется строго псевдосоставным (сильно псевдосоставным). Для основания b = 2 псевдопростых чисел от 1 до 109 всего 1282, что говорит об эффективности данного теста. Наименьшее строго псевдосоставное число одновременно по основаниям 2, 3 и 5 – 25 326 001.
Решето Эратосфена
Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:
Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
Пусть переменная p изначально равна двум — первому простому числу.
Зачеркнуть в списке числа от 2p до n считая шагами по p (это будут числа кратные p: 2p, 3p, 4p, …).
Найти первое незачёркнутое число в списке, большее чем p, и присвоить значению переменной p это число.
Повторять шаги 3 и 4, пока возможно.
Теперь все незачёркнутые числа в списке – это все простые числа от 2 до n.
Практическое применение детерминированных тестов затруднено из-за их большой вычислительной сложности. В связи с этим на практике используются вероятностные тесты простоты:
- тест Ферма;
- тест Миллера – Рабина
– критерий Вильсона;
- тест Соловея – Штрассена;
- и др.