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

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

Концепция

Маленькая теорема Ферма заявляет, что если п прост и а не делится на п, тогда

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

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

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

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

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

когда п составной а известен как Ферма лжец. В таком случае п называется Псевдопросто Ферма основать а.

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

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

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

пример

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

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

Либо 221 - простое число, либо 38 - лжец Ферма, поэтому берем другой а, скажем 24:

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

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

Алгоритм

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

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

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

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

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

Если ${ Displaystyle а ^ {п-1} not эквив 1 { pmod {п}}}$, затем вернитесь составной

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

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

Сложность

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

Недостаток

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

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

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

${ Displaystyle а в ( mathbb {Z} / п mathbb {Z}) ^ {*}}$ (т.е. ${ Displaystyle НОД (а, п) = 1}$)

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

${ Displaystyle (а cdot a_ {i}) ^ {n-1} эквив а ^ {п-1} CDOT а_ {я} ^ {п-1} эквив а ^ {п-1} not Equiv 1 { pmod {n}}}$

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

Приложения

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

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

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

использованная литература

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