Тест на простоту Ферма - Fermat primality test

Тест на простоту Ферма - это вероятностный тест, позволяющий определить, является ли число вероятным простым числом .

Концепция

Малая теорема Ферма утверждает , что если р является простым и не делится на р , то

{\ displaystyle a ^ {p-1} \ Equiv 1 {\ pmod {p}}.}

Если кто-то хочет проверить, является ли p простым, мы можем выбрать случайные целые числа a, не делящиеся на p, и посмотреть, выполняется ли равенство. Если равенство не выполняется для значения a , то p составное. Это сравнение маловероятно для случайного a, если p составное. Следовательно, если равенство действительно выполняется для одного или нескольких значений a , мы говорим, что p , вероятно, простое число .

Однако заметим, что при указанное выше сравнение выполняется тривиально. Это также тривиально выполняется, если p нечетно и . По этой причине в интервале обычно выбирают число a . ${\ Displaystyle а \ экви 1 {\ pmod {p}}}$ ${\ Displaystyle а \ экви -1 {\ pmod {p}}}$ ${\ Displaystyle 1 <а <р-1}$

Любое таким образом, что

{\ Displaystyle а ^ {п-1} \ эквив 1 {\ pmod {п}}}

когда n составное, a известен как лжец Ферма . В этом случае n называется псевдопервичным числом Ферма для основания a .

Если мы делаем выбрать таким образом, что

{\ Displaystyle а ^ {п-1} \ not \ эквив 1 {\ pmod {п}}}

тогда a известен как свидетель Ферма для составности n .

Пример

Предположим, мы хотим определить, является ли n = 221 простым. Случайным образом выберите 1 < a <220, скажем, a = 38. Мы проверяем указанное выше равенство и обнаруживаем, что оно выполняется:

{\ displaystyle a ^ {n-1} = 38 ^ {220} \ Equiv 1 {\ pmod {221}}.}

Либо 221 - простое число, либо 38 - лжец Ферма, поэтому возьмем еще один a , скажем 24:

{\ displaystyle a ^ {n-1} = 24 ^ {220} \ Equiv 81 \ not \ Equiv 1 {\ pmod {221}}.}

Итак, 221 составной, а 38 действительно был лжецом Ферма. Кроме того, 24 - свидетельство Ферма о составности 221.

Алгоритм

Алгоритм можно записать следующим образом:

Входные данные : n : значение для проверки на простоту, n > 3; k : параметр, определяющий, сколько раз проверять простоту

Вывод : составной, если n составное, в противном случае, вероятно, простое

Повторить k раз:

Pick случайным образом в диапазоне [2, п - 2]

Если , то вернуть составной

{\ Displaystyle а ^ {п-1} \ not \ эквив 1 {\ pmod {п}}}

Если составной никогда не возвращается: возврат, вероятно, простое

Значения a 1 и n -1 не используются, поскольку равенство выполняется для всех n и всех нечетных n соответственно, поэтому их тестирование не добавляет значения.

Сложность

Используя быстрые алгоритмы для модульного возведения в степень и умножения с множественной точностью, время работы этого алгоритма составляет $O (k log 2 n log log n) = Õ (k log 2 n)$ , где k - количество раз, когда мы проверяем случайное a , и n - значение, которое мы хотим проверить на простоту; подробности см. в тесте простоты Миллера – Рабина .

Недостаток

Во-первых, псевдопространство Ферма бесконечно много .

Более серьезный недостаток состоит в том, что чисел Кармайкла бесконечно много . Это числа, для которых все значения с являются лжецами Ферма. Для этих чисел повторное применение теста простоты Ферма работает так же, как простой случайный поиск факторов. Хотя числа Кармайкла существенно реже, чем простые числа (верхняя граница Эрдеша для числа чисел Кармайкла ниже, чем функция простых чисел n / log (n) ), их достаточно, что критерий простоты Ферма не часто используется в приведенном выше форма. Вместо этого чаще используются другие более мощные расширения теста Ферма, такие как Бейли – PSW , Миллер – Рабин и Соловей – Штрассен . ${\ displaystyle n}$ ${\ displaystyle a}$ ${\ Displaystyle \ OperatorName {gcd} (а, п) = 1}$

В общем, если это составное число, не являющееся числом Кармайкла, то по крайней мере половина всех ${\ displaystyle n}$

{\ Displaystyle а \ в (\ mathbb {Z} / п \ mathbb {Z}) ^ {*}}

(т.е. )

{\ Displaystyle \ OperatorName {gcd} (а, п) = 1}

являются свидетелями Ферма. Для доказательства этого, пусть будет свидетелем Ферма и , ..., быть Ферма лжецы. потом ${\ displaystyle a}$ ${\ displaystyle a_ {1}}$ ${\ displaystyle a_ {2}}$ ${\ displaystyle a_ {s}}$

{\ Displaystyle (а \ CDOT а_ {я}) ^ {п-1} \ эквив а ^ {п-1} \ CDOT а_ {я} ^ {п-1} \ эквив а ^ {п-1} \ не \ Equiv 1 {\ pmod {n}}}

и так все для свидетелей Ферма. ${\ Displaystyle а \ раз а_ {я}}$ ${\ displaystyle i = 1,2, ..., s}$

Приложения

Как упоминалось выше, в большинстве приложений используется критерий простоты Миллера – Рабина или Бейли – PSW . Иногда сначала выполняется тест Ферма (вместе с некоторым пробным делением на маленькие простые числа) для повышения производительности. GMP, начиная с версии 3.0, использует тест Ферма по основанию 210 после пробного разделения и перед запуском тестов Миллера – Рабина. Libgcrypt использует аналогичный процесс с базой 2 для теста Ферма, но OpenSSL этого не делает.

На практике с большинством библиотек с большими числами, такими как GMP, тест Ферма не заметно быстрее теста Миллера – Рабина и может быть медленнее для многих входных данных.

В качестве исключения OpenPFGW использует только тест Ферма для проверки вероятного простого числа. Программа обычно используется с многозначными входами с целью максимальной скорости с очень большими входами. Другая хорошо известная программа, которая полагается только на тест Ферма, - это PGP, где она используется только для тестирования самогенерируемых больших случайных значений (аналог с открытым исходным кодом, GNU Privacy Guard , использует предварительный тест Ферма, за которым следуют тесты Миллера – Рабина).

Languages

In other projects