Роберт Соловэй (Robert Solovay) и Фолькер Штрассен (Volker Strassen) разработали алгоритм вероятностной проверки простоты числа [1490]. Для проверки простоты числа р этот алгоритм использует символ Якоби:
(1) Выберите случайно число а, меньшее/;.
(2) Если НОД(а,/;) (1, тор не проходит проверку и является составным.
(3) Вычислите; = а(р-)12 mod/;.
(4) Вычислите символ Якоби ](а,р).
(5) Если j Ф J(a,p), то число р наверняка не является простым.
(6) Если; = J(a,p), то вероятность того, что число р не является простым, не больше 50 процентов.
Число а, которое не показывает, что р наверняка не является простым числом, называется свидетелем. Если р - составное число, вероятность случайного числа а быть свидетелем не ниже 50 процентов. Повторите эту проверку г раз с г различными значениями а. Вероятность того, что составное число преодолеет все t проверок, не превышает 1/2(.