Тест Ферма проверки чисел на простоту, числа Кармайкла — различия между версиями
м (добавлена категория) |
(→Тест Ферма) |
||
| Строка 11: | Строка 11: | ||
===Тест Ферма=== | ===Тест Ферма=== | ||
| − | Для любого <tex>n>1</tex> выбираем <tex> a>1</tex>, вычисляем <tex>a^{n-1} | + | Для любого <tex>n>1</tex> выбираем <tex> a>1</tex>, вычисляем <tex>a^{n-1}(mod n) </tex>, если результат не <tex>1</tex>, то <tex>n</tex> составное, если <tex>1</tex>, то <tex>n</tex> {{---}} слабовозможно простое. |
Часть чисел проходят тест Ферма и при этом являются составными, такие числа называются псевдопростыми. Для любого основания <tex>a</tex> существует бесконечно много псевдопростых чисел по основанию <tex>a</tex>. Мы можем сделать тест более точным, проведя его несколько раз для одного и того же числа, но с разными основаниями. Но даже в этом случае существуют числа Кармайкла, проходящие тест для всех чисел, не являющихся их делителями. | Часть чисел проходят тест Ферма и при этом являются составными, такие числа называются псевдопростыми. Для любого основания <tex>a</tex> существует бесконечно много псевдопростых чисел по основанию <tex>a</tex>. Мы можем сделать тест более точным, проведя его несколько раз для одного и того же числа, но с разными основаниями. Но даже в этом случае существуют числа Кармайкла, проходящие тест для всех чисел, не являющихся их делителями. | ||
[[Категория: Теория чисел]] | [[Категория: Теория чисел]] | ||
Версия 22:20, 25 декабря 2011
Эта статья находится в разработке!
| Теорема (Малая теорема Ферма): |
Если простое и любое, то
в частности, если не делитель , то |
На основании этой теоремы можно построить достаточно мощный тест на простоту:
Тест Ферма
Для любого выбираем , вычисляем , если результат не , то составное, если , то — слабовозможно простое.
Часть чисел проходят тест Ферма и при этом являются составными, такие числа называются псевдопростыми. Для любого основания существует бесконечно много псевдопростых чисел по основанию . Мы можем сделать тест более точным, проведя его несколько раз для одного и того же числа, но с разными основаниями. Но даже в этом случае существуют числа Кармайкла, проходящие тест для всех чисел, не являющихся их делителями.
