2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

 
 
 
 Re: Тест Ферма
Сообщение23.11.2015, 13:21 
MestnyBomzh в сообщении #1075916 писал(а):
Так что вероятность приведена для составных


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

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

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

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group