информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Сетевые кракеры и правда о деле ЛевинаАтака на Internet
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
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Не, быстрая не нужна, нужна не медленная. 15.12.08 18:17  Число просмотров: 4555
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 15.12.08 18:19  Количество правок: 2
<"чистая" ссылка>
> Для чего тебе быстрая генерация простых
> чисел? Реально рабин-миллер дает приемлемый (и по скорости
> и по вероятности) результат на практически применимых
> длинах чисел.

Сейчас уж не вспомню, то ли полкило, то ли килобит за минуту - обидно, понимаешь, умеючи и за 1-10 сек двухкилобитный генерится. Причем у меня скорость падает примерно как квадрат от разрядности. В смысле в два раза больше разраядность, в четыре (а то и больше) раза дольше генерится.

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

Ну это приятнее - раза в полтора будет быстрее.

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

Меня это смутило. Причина моих сомнений проста - получается, что Миллера-Рабина без такой проверки полный бред выдаст, ошибится сможет, особенно, если делители маленькие. Потом решил, что это рекомендовалось сделать, чтоб отсеить заведомо составные (кратные 2, 3, 5, ...). В принципе тест М-Р может быть достаточно сложным, длинным и долгим, если "отлуп" наступит на одном из последних раундов. Если же взять произведение десятка-другого маленьких простых и найти с ним НОД, то после первого же деления (по Евклиду) получаем уже достаточно небольшое число. Поэтому не десяток, а несколько делений вместо немалого количества умножений может быть оправдано.

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

Пусть будет и то и то. Порой бывает надо быстро реализовать, а тут попадается теория, да еще оборваная на полуслове, типа додумай сам, для повышения соображалки.

> А при чем здесь gcc? gmp под цигвином/мингвом можно

А это разве не надстройки над gcc?

> собирать и без всяких дополнительных телодвижений. То что я
> дал - это gmp для visual studio.

Да, видел, 6 версии достаточно.

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

Странно, должно быть раза в четыре. Я для совместимости реализовывал на 16 битах - отсюда думаю и тормоза. 32 уже, полагаю хватило бы, если в четыре раза скорость бы поднялась. Жалко бросать, делал для себя, на с++ класс с перегрузкой операций, удобнее, чем структуры в функции передавать.

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

Как много в этом мире добрых людей!
<theory> Поиск 






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


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