информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Страшный баг в WindowsВсе любят медЗа кого нас держат?
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Кавычки уличили Google в заимствовании... 
 Некоторые пароли от G Suite хранились... 
 Microsoft выпустила Windows Sandbox 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
А они используют "неполноценный" :-) (тест Рабина-Миллера)... 12.12.08 21:20  Число просмотров: 4539
Автор: 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 уже бить начинают? Определенно прогресс.
<theory> Поиск 








Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2019 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach