反復二乗法
l
y
≡
x
e
mod
n
を
高速に
計算する方法
l
例.
2
の場合
l
通常
:2
×
2
×
2
×
2
×
2
×
2
×
2
×
2
⇒
7
回の演算
l
反復二乗法
:
((2
)
)
⇒
3
回の演算
l
2
の場合
l
通常:
2
×
2
×
2
×・・・×
2
⇒
1023
回の演算
l
反復二乗法:
((((2
)
)
)
・・・
)
⇒
10
回の演算
8
2
2
2
1024
2
2
2
2