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

Чтобы узнать о тесте на определение того, является ли число Ферма простым, см. тест Пепена .

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

Концепция

Маленькая теорема Ферма утверждает, что если p — простое число и a не делится на p , то

$a^{p-1}\equiv 1{\pmod {p}}.$

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

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

Любое такое , что

$a^{n-1}\equiv 1{\pmod {n}}$

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

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

$a^{n-1}\not \equiv 1{\pmod {n}}$

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

Пример

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

$a^{n-1}=38^{220}\equiv 1{\pmod {221}}.$

Либо 221 — простое число, либо 38 — это лжец Ферма, поэтому берём ещё одно число , скажем 24:

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

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

Алгоритм

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

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

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

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

Выберите случайное число в диапазоне [2, n − 2]

Если $a^{n-1}\not \equiv 1{\pmod {n}}$, затем верните составной

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

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

Сложность

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

Недостаток

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

В общем, если $n$ — составное число, не являющееся числом Кармайкла, то не менее половины всех

$a\in (\mathbb {Z} /n\mathbb {Z} )^{*}$ (т.е. $\operatorname {gcd} (a,n)=1$)

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

$(a\cdot a_{i})^{n-1}\equiv a^{n-1}\cdot a_{i}^{n-1}\equiv a^{n-1}\not \equiv 1{\pmod {n}}$

и так все $a\cdot a_{i}$ для $i=1,2,...,s$ являются свидетелями Ферма.

Приложения

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

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

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

Ссылки

• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест , Клиффорд Стейн (2001). «Раздел 31.8: Тестирование на примитивность». Введение в алгоритмы (второе изд.). Массачусетский технологический институт Пресс; МакГроу-Хилл. п. 889–890. ISBN  0-262-03293-7 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )