Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Если тебе для RSA, то они генерятся несколько иначе :-) 15.12.08 19:59 Число просмотров: 4912
Автор: 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
|
|
|
подробно о проекте
Анализ криптографических сетевых...
