Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Ни фига не правильно 15.12.04 15:27 Число просмотров: 5458
Автор: amirul <Serge> Статус: The Elderman
|
> > Однако для вычислений с большим ключом (чаще d),
> который
> > можно разложить на сомножители, оказывается более
> быстрым
>
> Все, собственно, верно, но фраза какая-то странная "для
> вычислений с большим ключом (чаще d), который можно
> разложить на сомножители". Можно то оно можно... Раз уж
> речь идет о большом ключе (более 100 бит)... Попробуйте
> несколько_сот_битное (я уж не говорю о килобитном) число
> разложить на сомножители, если их всего два.
Это алгоритм эспонирования методом возведения в квадрат. Суть его в том, чтобы представить
pm = pm0*20 + m1*21 + ... + mi*2i
где mi..m1,m0 - просто двоичные знаки числа
Тогда pm = pm0*20 * pm1*21 * ... * pmi*2i
Эффективность возведения в степень будет зависить только от эффективности алгоритма умножения и алгоритма возведения в квадрат (зачастую есть более эффективные алгоритмы, чем прямое умножение n*n)
Ну и сложность примерно O(log2(m)). Опять же отмечу, если нужно модульное возведение в степень, то ни один из шагов этого алгоритма не дает чисел больших, чем модуль, по которому производятся вычисления
|
|
|
подробно о проекте
Анализ криптографических сетевых...
