Псевдопростое число Эйлера – Якоби

В теории чисел нечетное вероятным целое число n называется вероятным простым числом Эйлера–Якоби (или, чаще, простым числом Эйлера ) для основания a , если a и n , взаимно просты и

$a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}$

где $\left({\frac {a}{n}}\right)$ — символ Якоби .

Если n — нечетное составное целое число, удовлетворяющее приведенному выше сравнению, то n называется псевдопростым числом Эйлера–Якоби (или, чаще, псевдопростым числом Эйлера ) для основания a .

Характеристики

Мотивацией для этого определения является тот факт, что все простые числа n удовлетворяют приведенному выше уравнению, как объяснено в статье о критериях Эйлера . Уравнение можно проверить довольно быстро, что можно использовать для вероятностного тестирования простоты . Эти тесты более чем в два раза надежнее тестов, основанных на малой теореме Ферма .

Каждое псевдопростое число Эйлера – Якоби также является псевдопростым числом Ферма и псевдопростым числом Эйлера . Не существует чисел, которые были бы псевдопростыми по всем основаниям Эйлера – Якоби, как числа Кармайкла . Соловей и Штрассен показали, что для любого составного n , по крайней мере, для n /2 оснований меньше n , n не является псевдопростым числом Эйлера – Якоби.

Наименьшее псевдопростое число Эйлера-Якоби по основанию 2 равно 561. Существует 11347 псевдопростых чисел Эйлера-Якоби по основанию 2, которые меньше 25·10. ⁹ (см. OEIS : A047713 ) (стр. 1005 из ).

В литературе (например, ), псевдопростое число Эйлера – Якоби, определенное выше, часто называют просто псевдопростым числом Эйлера.

Реализация на Lua

function EulerJacobiTest(k)
        a = 2
        if k == 1 then return false
        elseif k == 2 then return true
        else
                if(modPow(a,(k-1)/2,k) == Jacobi(a,k)) then
                        return true
                else
                        return false
                end
        end
end

См. также

• Вероятное простое число