Тест Ферма

[MestnyBomzh]

Разбираюсь с тестом простоты Ферма. Всё бы хорошо, но я не понимаю момент про вероятность ошибки теста. Там сказано, что вероятность ошибки: $\frac{\varphi(n)}{n}$. И при этом говорится, что это меньше, чем $\frac{1}{2}$. Почему это правда?

[arseniiv]

Странно. Если $p$ — простое, $\varphi(p) = p-1$, и $\frac{\varphi(p)}p > \frac12$, если $p>2$. С составными такое тоже бывает.

[MestnyBomzh]

Если число $p$ простое, то алгоритм Ферма будет работать. Он с вероятностью $1$ выдаст, что число простое. Другое дело - составные числа, на них он, порой, ошибается. Так что вероятность приведена для составных

[Cash]

MestnyBomzh в сообщении #1075916 писал(а):

Так что вероятность приведена для составных

Вообще-то это вероятность ошибки не для обыкновенных составных, а для чисел Кармайкла. И более актуален вопрос - есть ли хотя бы одно число Кармайкла, для которого это отношение было бы меньше $\frac 12$?

[Батороев]

MestnyBomzh в сообщении #1075861 писал(а):

Разбираюсь с тестом простоты Ферма. Всё бы хорошо, но я не понимаю момент про вероятность ошибки теста. Там сказано, что вероятность ошибки: $\frac{\varphi(n)}{n}$. И при этом говорится, что это меньше, чем $\frac{1}{2}$. Почему это правда?

По-видимому, в текст лекции незаметно "вкрался" тест Соловея-Штрассена.