М24. Нахождение чисел, "предположительно" являющихся простыми

С помощью "решета Эратосфена" можно найти все простые числа, меньшие заданного числа N. Это - стандартный метод, если необходимо найти именно список всех простых чисел. Если же, однако, нам нужно только проверить, является ли конкретное число простым, то составлять список всех простых чисел вовсе не обязательно. К тому же, если число очень велико, то это потребует солидных затрат времени. К сожалению, в общем случае не существует никакого достаточно быстрого метода проверки простоты заданного большого числа N. Если N достаточно велико, чтобы рассматривать его в качестве кандидата для использования в методе RSA (например, порядка 10⁵⁰), то для точного доказательства его простоты потребуется непомерно большое время. В свете этого факта в 1976 г. Рабин (см. [12.8]), а в 1977 г. - в несколько другой форме - Соловей и Штрассен (см. [12.9]) предложили иной подход. В его основе заложена идея проверки некоторого условия относительно какого-либо числа, меньшего N. Это условие должно

1. никогда не выполняться, если N является простым;

2. выполняться чаще, чем не выполняться, если N не является простым.

Условие, предложенное Рабином, для составных N выполняется более чем в 75% случаев. Возьмем много чисел, меньших N (к примеру, m штук), и для каждого из этих m чисел проверим это условие. Если оно ни разу не выполнилось, то вероятность простоты числа N оценивается величиной (0.25)^m. Взяв m достаточно большим, эту вероятность можно сделать сколь угодно близкой к единице.

Описание условия Рабина можно найти в работе [1.2], в главе 9. Список научных работ по смежной тематике см. в [13.12].