Тест Ферма проверки чисел на простоту, числа Кармайкла

Эта статья находится в разработке!

Теорема (Малая теорема Ферма):

Если [math]p[/math] простое и [math]a[/math] любое, то [math]a^p\equiv a\pmod p[/math] в частности, если [math]p[/math] не делитель [math]a[/math], то [math]a^{p-1}\equiv 1\pmod p[/math]

На основании этой теоремы можно построить достаточно мощный тест на простоту:

Тест Ферма

Для любого [math]n\gt 1[/math] выбираем [math] a\gt 1[/math], вычисляем [math]a^{n-1}\mod n[/math], если результат не [math]1[/math], то [math]n[/math] составное, если [math]1[/math], то [math]n[/math] — слабовозможно простое.

Часть чисел проходят тест Ферма и при этом являются составными, такие числа называются псевдопростыми. Для любого основания [math]a[/math] существует бесконечно много псевдопростых чисел по основанию [math]a[/math]. Мы можем сделать тест более точным, проведя его несколько раз для одного и того же числа, но с разными основаниями. Но даже в этом случае существуют числа Кармайкла, проходящие тест для всех чисел, не являющихся их делителями.