Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Разбираюсь с тестом простоты Ферма. Всё бы хорошо, но я не понимаю момент про вероятность ошибки теста. Там сказано, что вероятность ошибки: . И при этом говорится, что это меньше, чем . Почему это правда?
arseniiv
Re: Тест Ферма
23.11.2015, 04:12
Последний раз редактировалось arseniiv 23.11.2015, 04:14, всего редактировалось 1 раз.
Странно. Если — простое, , и , если . С составными такое тоже бывает.
MestnyBomzh
Re: Тест Ферма
23.11.2015, 09:19
Если число простое, то алгоритм Ферма будет работать. Он с вероятностью выдаст, что число простое. Другое дело - составные числа, на них он, порой, ошибается. Так что вероятность приведена для составных
Вообще-то это вероятность ошибки не для обыкновенных составных, а для чисел Кармайкла. И более актуален вопрос - есть ли хотя бы одно число Кармайкла, для которого это отношение было бы меньше ?
Разбираюсь с тестом простоты Ферма. Всё бы хорошо, но я не понимаю момент про вероятность ошибки теста. Там сказано, что вероятность ошибки: . И при этом говорится, что это меньше, чем . Почему это правда?
По-видимому, в текст лекции незаметно "вкрался" тест Соловея-Штрассена.