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

Вероятностный тест на простоту

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

Концепция

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

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

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

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

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

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

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

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

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

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

Пример

Предположим, мы хотим определить, является ли n  = 221 простым числом. Случайным образом выбираем 1 < a < 220, скажем, a  = 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.

Алгоритм

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

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

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

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

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

Если , то вернуть составной ${\displaystyle 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 — значение, которое мы хотим проверить на простоту; подробности см. в тесте Миллера–Рабина на простоту .

Недостаток

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

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

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

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

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

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

Приложения

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

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

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

Ссылки

1. Карл Померанс ; Джон Л. Селфридж ; Сэмюэл С. Вагстафф, младший (июль 1980 г.). «Псевдопростые числа до 25·109» (PDF) . Математика вычислений . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 . JSTOR  2006210.
2. Alford, WR ; Granville, Andrew ; Pomerance, Carl (1994). «Существует бесконечно много чисел Кармайкла» (PDF) . Annals of Mathematics . 140 (3): 703–722. doi :10.2307/2118576. JSTOR  2118576.
3. Пол Эрдеш (1956). «О псевдопростых числах и числах Кармайкла». Опубл. Математика. Дебрецен . 4 : 201–206. МР  0079031.
4. Джо Хёрд (2003), Проверка вероятностного теста Миллера-Рабина на простоту , стр. 2, CiteSeerX 10.1.1.105.3196 

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein (2001). "Раздел 31.8: Проверка простоты". Введение в алгоритмы (Второе издание). MIT Press; McGraw-Hill. стр. 889–890. ISBN 0-262-03293-7.{{cite book}}: CS1 maint: multiple names: authors list (link)