|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Doroshev 2:5020/400 06 Apr 2002 10:20:38
To : Alexander Topolskiy
Subject : Re: Пpостые числа... - fido7.ru.algorithms
--------------------------------------------------------------------------------
Dear Alexander!
> RM>>> ЗЫ: кстати, благодаpя такомy отсеиванию и тестy Рабина-Миллеpа,
> MA>> ИМХО, пpи использовании Милеpа-Рабина смысл использовать
> MA>> пpосеивание пpопадает.
> WS> тест Рабина-Миллеpа для больших чисел pаботает дольше,
> WS> чем пpосеивание, поэтомy лyчше сначала сделать пpосеивание :)
> А можно узнать что это за тест?
Вероятностный тест.
Если число простое, то оно пройдёт все проверки ("раунды").
Если число составное, то с вероятностью 3/4 будет получен ответ о том, что оно
составное.
После нескольких десятков проверок вероятность ошибки меньше любого разумного
предела.
Реализацию на паскале кидал Max Alekseyev с месяц назад. Поройся в архивах эхи.
> Истина где-то рядом, Wowa...
Дословный перевод может быть иным:
Истины здесь нет.
Andrew Doroshev
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
