5.3. Тест на простоту Соловея-Штрассена.

Символ Якоби отличается от символа Лежандра тем, что в первом знаменатель – составное число, а во втором – простое. Алгоритм вычисления символа Якоби и символа Лежандра одинаков, но для символа Якоби не выполняется критерий Эйлера.

Пусть мы имеем нечетное число n, о котором неизвестно, простое оно или составное. Символ является символом Лежандра, еслиn – простое, и тогда для него выполняется критерий Эйлера, то есть .

Если же n – составное число, то символ является символом Якоби, и тогда вышеуказанное сравнение, возможно, не выполняется. (Мы говорим «возможно», так как для некоторыхa и n, в силу случайного совпадения, сравнение может оказаться верным.)

Поэтому если найдется такое a (1 < a < n), что , то можно наверняка утверждать, что числоn – составное. На этом факте основан тест Соловея-Штрассена.