Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
А они используют "неполноценный" :-) (тест Рабина-Миллера)... 12.12.08 21:20 Число просмотров: 6185
Автор: amirul <Serge> Статус: The Elderman
|
> Как они умудряются за секунду сотни чисел протестировать. > Все таки полноценный тест на простоту не так уж и быстр?
А они используют "неполноценный" :-) (тест Рабина-Миллера). Основан на малой теореме Ферма.
x^(n - 1) mod n = 1 для любого простого n
Если случайно выбирать x и проверять равенство, то можно с любой заданной вероятностью проверить является ли число простым. Собственно если тест дает ответ составное, то число 100% составное, если тест дает ответ простое, то число простое с некоторой вероятностью (чем больше разных x-ов проверено - тем выше вероятность). Для какого нибудь Mersenne Sieve это не подходит, а вот для практических задач вероятность порядка 2^-100 гораздо меньше, чем вероятность того, что детерминированный тест выдаст неправильный результат из-за случайного глюка, наведенного внешним излучением
http://en.wikipedia.org/wiki/Miller–Rabin_primality_test
> GMP только под Линукс или или попроще есть? Нет не только. http://letmegooglethatforyou.com/?q=gmp+windows
http://fp.gladman.plus.com/computing/gmp4win.htm
> Может есть что попроще GMP? Есть другие. Но GMP ни фига не сложный В ИСПОЛЬЗОВАНИИ, так что попроще - вряд ли.
> Среди Линкус дистрибов что-нибудь изменилось? Что сейча > поинтереснее и где его лучше взять? Неа. Все такой же отстой, который "скоро захватит мир". Взять - смотря чего тебе надо. Если просто поковыряться с минимумом проблем (совсем без проблем не получится, хаха) - бери убунту и не слушай слишком красноглазых. Если хочется "полного контроля над системой" - генту как раз для тебя (disclaimer: тебе нужен будет очень мощный компьютер, чтобы он собирал @$илды быстрее, чем выходят новые, а глаза твои покраснеют от постоянного недосыпа).
> (Спрашивал на рынке/развале - чуть не побили). :-)
Даже так? Неужто сейчас за вопросы про leenooks уже бить начинают? Определенно прогресс.
|
|
|