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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Тест Ферма)
Строка 4: Строка 4:
 
|about=Малая теорема Ферма
 
|about=Малая теорема Ферма
 
|statement=
 
|statement=
Если <tex>p</tex> простое и <tex>a</tex> любое, то <tex>a^p\equiv a\pmod p</tex>
+
Если <tex>p</tex> простое и <tex>a</tex> не делится на <tex>p</tex>, то <tex>a^{p-1}\equiv 1\pmod p</tex>
 
 
в частности, если <tex>p</tex> не делитель <tex>a</tex>, то <tex>a^{p-1}\equiv 1\pmod p</tex>
 
 
}}
 
}}
 
На основании этой теоремы можно построить достаточно мощный тест на простоту:
 
На основании этой теоремы можно построить достаточно мощный тест на простоту:

Версия 18:25, 18 июля 2019

Эта статья находится в разработке!
Теорема (Малая теорема Ферма):
Если [math]p[/math] простое и [math]a[/math] не делится на [math]p[/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]. Мы можем сделать тест более точным, проведя его несколько раз для одного и того же числа, но с разными основаниями. Но даже в этом случае существуют числа Кармайкла, проходящие тест для всех чисел, не являющихся их делителями.