информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Spanning Tree Protocol: недокументированное применениеЗа кого нас держат?
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор 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  Число просмотров: 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 уже бить начинают? Определенно прогресс.
<theory> Поиск 






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


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