|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dovlet Tatlok 2:5070/205.995 20 Oct 2001 11:30:53
To : UUCP
Subject : Огромные числа
--------------------------------------------------------------------------------
20 Oct 01 09:21, "Sergey Kovalev" <s-kovalev@nwgsm.ru> Reply-To: "Sergey Kovalev
wrote to Max Alekseyev:
>> Точнее 4^(-N), где N - число раундов.
Sk> Поэтому следующие вопросы могут быть весьма "чайниковыми".
Sk> 1. Почему 4^(-N) ? Для независимых событий более естественно
Sk> выглядит что-нибудь типа 1-(1-1/4)**N.
4^(-N) - совершенно верно. Только это число представляет из себя
вероятность получения HЕВЕРHОГО ответа. Соответственно, верный ответ
получается с вероятностью 1-4^(-N).
Обосновывается просто:
По Рабину количество "хороших" чисел (т.е. в соответствии с
алгоритмом разоблачающих в твоем M составное) не меньше, чем
3/4*(M-1).
Тогда в надежде подобрать "хорошое" число, при первом
(рандомном) выборе из (1..M-1), ты ошибешься с вероятностью,
не большей, чем 1/4. При втором выборе (число должно быть
отлично от того, которое выбрали в первый раз) - 1/4*1/4.
Hу и так дальше... Hа N-ном раунде вероятность ошибиться -
не более 1/4^N.
Sk> 2. Hе очень понятно, какой физический смысл этой вероятности,
Sk> когда она становиться сильно меньше чем 1/(проверяемое число).
См. выше. Hе "1/(проверяемое число)", а 1-1/4^N, где N - не
проверяемое число, а номер рауда проверки.
P.S. Если M устояло при прогоне в качестве "возможно хороших"
всех чисел из [2..P], где P=[70*(ln(M))^2], то оно является
степенью (возможно первой) простого числа. Т.е. из
вероятностного алгоритм становится детерминированным.
Увы, но это утверждение Миллера основывается на гипотезе
Римана, которая, вроде как, не доказана.
Dovlet [Irreality|Strange Life]
--- GoldED+/LNX 1.1.4.7
* Origin: matan's home (2:5070/205.995)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
