Lehmann

Другой, более простой тест был независимо разработан Леманном (Lehmann) [903]. Вот последовательность действий при проверке простоты числа р:

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

(2) Вычислите а^рА'² mod/;.

(3) Если а^рА'² Ф 1 или -1 (mod p), то р не является простым.

(4) Если cfi-V'¹ = 1 или -1 (mod p), то вероятность того, что число р не является простым, не больше 50 про­центов.

И снова, вероятность того, что случайное число а будет свидетелем составной природы числа р, не меньше 50 процентов. Повторите эту проверку t раз. Если результат вычислений равен 1 или -1, но не всегда равен 1, то р является простым числом с вероятностью ошибки I/²'.