Почему Миллер-Рабин вместо теста на примитивность Ферма?

Из доказательства Миллера-Рабина , если число проходит тест на примарность по Ферму , оно также должно пройти тест Миллера-Рабина с тем же основанием (переменная в доказательстве). И сложность вычислений такая же. $a$

Следующее из теста примитивности Ферма :

В то время как числа Кармайкла существенно реже, чем простые числа 1, их достаточно, чтобы критерий примарности Ферма часто не использовался в вышеуказанной форме. Вместо этого чаще используются другие более мощные расширения теста Ферма, такие как Baillie-PSW, Miller-Rabin и Solovay-Strassen.

В чем преимущество Миллера-Рабина и почему он считается более мощным, чем критерий примитивности Ферма?

algorithms primes ZijingWu
источник

Ответы:

Алгоритм Рабина-Миллера также проверяет, учитывая число , имеет ли нетривиальный корень Unity. $n$ $Z_n$

Числа Carmichael пройти тест Ферма (для каждого базиса ), но и для каждого числа Carmichael , существует много чисел таким образом, что тест на корни единства терпит неудачу на (то есть последовательность конечном итоге отображает нетривиальный корень единства). $a$ $n$ $a$ $a$ $a,2a,...,2^ra$

Таким образом, мы имеем следующее:

Для теста Ферма, если составное число не Кармайкл, то вероятность того, что тест будет обнаруживать композитность составляет по меньшей мере . Тем не менее, тест не пройдёт все числа Кармайкла. $n$ $1/2$

Для теста Рабина-Миллера, каждое составное число будет обнаружен с вероятностью по крайней мере . Это означает, что вероятность правильности не зависит от входных данных (нет «жестких» входных данных). Это то, что делает этот алгоритм сильнее. $1/2$

Shaull
источник

Вы имеете в виду, что Кармайкл номер n может успешно пройти тест Ферма, но потерпел неудачу на Рабине-Миллере, используя ту же базу a?

ZijingWu

Номера Carmichael пройти тест Ферма для каждого

, но в течение некоторого

a

$a$

a

$a$ «S будет провалить тест Рабина-Миллера ( в частности, корень теста Unity).

Шал

Но Кармайкл не пройдет тест Ферма для каждого

, верно? Например, первое число Кармайкла 561 = 3 * 11 * 17 не пройдет тест Ферма для

= 3, 11 или 17.

a

$a$

a

$a$

ZijingWu

Когда мы говорим «пройти», мы имеем в виду, что они не будут обнаружены как составные числа. Таким образом, число Carmichael будет пройти тест для каждого

a

$a$

a

$a$

Смысл «более сложных» тестов состоит в том, что доля лежащих оснований (скажем, число может быть простым, если это не так) имеет гарантированный предел менее 1. Т.е. в Миллере-Рабине можно показать, что самое большее 1/4 лжи (IIRC, и граница довольно пессимистична).

vonbrand

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

См., Например, статью Pomerance / Selfridge / Wagstaff на странице Википедии Миллер-Рабин:

https://math.dartmouth.edu/~carlp/PDF/paper25.pdf

где мы видим диаграмму на странице 2, показывающую, что псевдоприложения Эйлера являются подмножеством псевдоприемов Ферма, а сильные псевдоприложения являются подмножеством их. Таким образом, критерий Соловея-Штрассена является более проницательным, чем критерий Ферма, а критерий Миллера-Рабина более чем любой. Они оба избегают критической проблемы чисел Кармайкла. Они имеют практически одинаковую производительность, поэтому мы предпочитаем использовать тест Миллера-Рабина.

DanaJ
источник

Должно быть очевидно, что Миллер-Рабин лучше Ферма.

$a^{p-1}$

$a^{p-1}$ $p-1 = s·2^k$ $a^s$ $a^{p-1}$

Опять же, если результат не равен 1 (по модулю p), то p является составным. Но если результат равен 1 по модулю p, то мы проверяем, получили ли мы это 1, возводя в квадрат промежуточный результат, который не был +1 или -1, и в этом случае x также доказано составным.

Таким образом, мы выполняем точно такой же объем работы, но есть больше способов доказать, что x является составным.

gnasher729
источник