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





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Если тебе для RSA, то они генерятся несколько иначе :-) 15.12.08 19:59  Число просмотров: 4494
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
> Сейчас уж не вспомню, то ли полкило, то ли килобит за
> минуту - обидно, понимаешь, умеючи и за 1-10 сек
> двухкилобитный генерится. Причем у меня скорость падает
> примерно как квадрат от разрядности. В смысле в два раза
> больше разраядность, в четыре (а то и больше) раза дольше
> генерится.

Если тебе для RSA, то они генерятся несколько иначе :-)
Там ведь еще куча условий, необходимых для стойкости ключа.
http://en.wikipedia.org/wiki/RSA#Key_generation_2

> Меня это смутило. Причина моих сомнений проста -
> получается, что Миллера-Рабина без такой проверки полный
> бред выдаст, ошибится сможет, особенно, если делители

Нет, от делителей результат теста вообще не зависит.

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

Ага, я протормозил - только что понял, что там используется модулярная арифметика - то бишь деление на N на каждом раунде возведения в степень. Таки да - лучше сразу отсеять лишнее. А в случае с nextprime - так вообще за один вызов gcd отсеять ВСЕ лишние числа. Тут даже и большое (хотя бы 1000) количество маленьких простых можно использовать.

> деления (по Евклиду) получаем уже достаточно небольшое
> число. Поэтому не десяток, а несколько делений вместо
> немалого количества умножений может быть оправдано.
В случае с nextprime - еще как оправдано. Но не при наивной реализации (проверка делимости на малые простые при каждой проверке на простоту).

> > А при чем здесь gcc? gmp под цигвином/мингвом можно
> А это разве не надстройки над gcc?
Нет. Это и есть gcc, собранный под винду.

> > собирать и без всяких дополнительных телодвижений. То
> что я
> > дал - это gmp для visual studio.
> Да, видел, 6 версии достаточно.
6-й версии студии? Выкинь ее срочно. :-)
Она ж появилась даже раньше, чем стандарт C++ (а стандарт с тех пор еще пару рас апдейтился), да и баги никто не отменял. Хочешь лицензионной чистоты - бери vs express и не мучайся

> Странно, должно быть раза в четыре. Я для совместимости
Не, не должно
Теоретический максимум - 2 раза. Это если все что ты будешь делать - перемалывать лимбы (лимб увеличился в 2 раза - тебе придется делать в 2 раза меньше работы): у умножения на таких числах сложность почти линейная: O(n (log n) (log log n)), но кроме самой работы с лимбами есть еще и куча вспомогательной работы - отсюда и 15%.

> реализовывал на 16 битах - отсюда думаю и тормоза. 32 уже,
> полагаю хватило бы, если в четыре раза скорость бы
> поднялась. Жалко бросать, делал для себя, на с++ класс с
> перегрузкой операций, удобнее, чем структуры в функции
> передавать.
Ну дык
# include <gmpxx.h>
и вперед. Там в частности реализованы отложенные вычисления, то бишь
a += b * c;
скомпилится не в 2 (или не дай бог 3) вызова, а в один mpz_addmul
<theory> Поиск 






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


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