Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Для чего тебе быстрая генерация простых чисел?... 14.12.08 00:01 Число просмотров: 4674
Автор: 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 работал.
Бери бубунту и не слушай пингвинофанатов.
> Благо не за сам линукс.
Жаль :-)
|
|
|
подробно о проекте
Анализ криптографических сетевых...
