Составители:
(a
1
⋅ a
2
⋅ … ⋅ a
16
) mod n.
Вместо этого следует выполнить только четыре малых умножения и
четыре приведения по модулю:
a
16
mod n = (((a
2
mod n)
2
mod n)
2
mod n)
2
mod n.
В свою очередь, вычисление a
x
mod n, где x не является
степенью 2, производят аналогичным образом. Для этого число x
представляют как сумму степеней 2:
x = 25
(10)
→ 1 1 0 0 1
(2)
, поэтому 25 = 2
4
+ 2
3
+ 2
0
.
Затем вычисляют рассмотренным выше способом:
a
25
mod n = (a ⋅ a
24
) mod n = (a ⋅ a
8
⋅ a
16
) mod n =
= a ⋅ ((a
2
)
2
)
2
⋅ (((a
2
)
2
)
2
)
2
mod n = ((((a
2
⋅ a)
2
)
2
)
2
⋅ a) mod n.
При сохранении промежуточных результатов вычислений в данном
случае потребуется только шесть умножений:
(((((((a
2
mod n) ⋅ a) mod n)
2
mod n)
2
mod n)
2
mod n) ⋅a) mod n.
Этот метод уменьшает трудоёмкость вычислений до 1,5k операций в
среднем, где k – длина числа в битах, что особенно заметно при работе с
числами длинной более 100 бит.
Так как многие алгоритмы шифрования основаны на возведении в
степень по модулю n, то целесообразно использовать рассмотренный
выше метод быстрого возведения
в степень.
П.1. Алгоритм вычисления наибольшего общего делителя
(алгоритм Евклида)
Целое число a делит без остатка целое число b, если b = k ⋅ a
для некоторого целого числа k. В этом случае число a называют
делителем числа b.
Пусть a – целое число, большее 1. Тогда а является простым числом,
если
его положительными делителями будут 1 и само а, в противном
случае а называется составным.
Любое целое n > 1 может быть представлено единственным образом с
точностью до порядка сомножителей как произведение простых [1, 15].
Существенным с точки зрения криптографии является тот факт, что
до настоящего времени не известно как эффективных алгоритмов
154
Страницы
- « первая
- ‹ предыдущая
- …
- 150
- 151
- 152
- 153
- 154
- …
- следующая ›
- последняя »
