Тест Ферма на простоту

Вход: число n – для проверки на простоту, t – параметр надежности.

1. Повторяем t раз:

а) Случайно выбираем a [2, n-2]

б) Если a^n–1 1 (mod n) «n – составное». Выход.

2. «n – простое с вероятностью 1– ε^t »

Этот тест может принять составное число за простое, но не наоборот.

Вероятность ошибки есть ε^t, где ε

В случае составного числа n, имеющего только большие делители, ε, то есть существуют числа, для которых вероятность ошибки при проверке их на простоту тестом Ферма близка к 1.

Для теста Ферма существуют так называемые числа Кармайкла – такие составные числа, что a: (a,n) = 1 a^n–1 ≡ 1(mod n). То есть числа Кармайкла – это такие составные числа, которые всегда принимаются тестом Ферма за простые, несмотря на то, как велико число t – параметр надежности теста.

Теорема Кармайкла

n – число Кармайкла 1)n свободно от квадратов (т.е. n = p₁∙p₂∙…∙p_k);

2) (p_i – 1)\(n – 1), i = 1,…,k ;

3) k .

Наименьшее известное число Кармайкла n=561 = 3∙11·17