Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Необязательно вычислять модуль после того, как вычислена... 15.12.04 17:18 Число просмотров: 5802
Автор: amirul <Serge> Статус: The Elderman
Отредактировано 15.12.04 17:18 Количество правок: 1
|
> Тут ведь на каждом шаге действительно значение не будет
> превышать n, однако прежде чем вычислить модуль, придётся
> так или иначе вычислить степень и тогда превышать n число
> будет с большой степенью вероятности. А если "забыть" о
> двоичной системе, то превышение может быть значительное.
Необязательно вычислять модуль ПОСЛЕ того, как вычислена степень. Одно из свойств сравнений:
Если a*b = c
то a*b ≡ c mod (M)
Даже никаких условий взаимной простоты не надо, как в большинстве других свойств. Таким образом ВСЕ операции можно выполнять по модулю - результат от этого не изменится.
Даже если не принимать во внимание существование алгоритмов модульного умножения, все равно ни одна операция при возведении в степень по модулю M не даст числа больше, чем M2 (промежуточный результат при умножении).
Так что максимальный размер чисел можно предсказать до выполнения операции.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
