информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Все любят медСтрашный баг в Windows
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Ростелеком заподозрили в попытке... 
 Линуксовый ботнет, распространяющийся... 
 Конец поддержки Internet Explorer 
главная обзор 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
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Для чего тебе быстрая генерация простых чисел?... 14.12.08 00:01  Число просмотров: 4316
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
> Под "неполноценностью" я имел в виду не то, что он
> вероятностный, а то, что количество проверок может быть
> больше или меньше. Это сильно влияет на скорость, а
Для чего тебе быстрая генерация простых чисел? Реально рабин-миллер дает приемлемый (и по скорости и по вероятности) результат на практически применимых длинах чисел.

> количество проверок должно быть примерно равно двоичному
> логарифму. То есть тысяча для килобитного ключа, а это в
Натуральному. Я уже давал ссылку на распределение простых чисел. Расстояние между ними растет логарифмически (натурально логарифмически :-) )

> тысячу раз медленнее. Кроме того рекомендовалось зачем-то
> первоначально проверить делимость на маленькие простые
> числа.
Не знаю, по моему в случае рабина миллера это бессмысленно. Один gcd - это как минимум десяток делений. При этом число уменьшится незначительно и не слишком повлияет на скорость дальнейшей проверки.


> Я читал русскоязычную версию. И что они там везде мудрят,
> написали бы просто "вычислить то-то столько-то раз для
> такой-то точности, что хватит выше крыши".
Категорически не согласен. Если выбирать между примитивной реализацией и фундаментальными сведениями - то лучше пусть будет фундамент, а реализацию я как нибудь сам. С другой стороны лучше чтобы было и то и то.

> Это хорошо. Хотя я про gcc под винду (даже дос) слышал, но
> до "ввода в эксплуатацию" не дошло.
А при чем здесь gcc? gmp под цигвином/мингвом можно собирать и без всяких дополнительных телодвижений. То что я дал - это gmp для visual studio.

> Мне всего то нужен С++ с нормальной поддержной 32/64
> разрядности и хотелось бы добраться до gmp. А то самому с
> реализацией базового уровня надоело ковыряться.
Ну и vc и gcc умеют 32/64. Я кстати, используя вышеприведенный линк собирал 64-битный gmp для вычисления 9^(9^9)
Прирост в скорости от перехода 32->64 не очень большой, но процентов 10-15 есть.

> Спасиб. Я что-то в последнее время отстал от жизни. Мне
> ничего собирать не надо. Главное что gcc работал.
Бери бубунту и не слушай пингвинофанатов.

> Благо не за сам линукс.
Жаль :-)
<theory> Поиск 






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


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