- 948 名前：デフォルトの名無しさん [2007/05/11(金) 09:07:12 ]
- >>947の続き
ユーグリッドの互助法の拡張定理により、互いに素であるyとaに対して
a*x+b*y=1となるxを求める。
作業用のローカル変数(s,t,u,v)を次のように初期化
s=a; t=y; u=1; v=0;
while(sが正の間){
q=t/s(切捨て)
w=t-q*s
t=s
s=w
w=v-q*u
v=u
u=w
}
v<0ならばv+yがv>0ならばvが求めるxになる
このときの公開鍵が(e,n)で秘密鍵が(d,n)である。ただしpとqも秘密にする必要がある
(4) 暗号化と複合化
平分Mの暗号化Me%n -> C
暗号文Cの複合化Cd%n -> M
MeやCｄの計算をそのまま行うとあっという間にオーバーフローしてしまいます。Word=2の31乗を超えて
しまうのです。そこで次のような手順で計算するようなプログラムにしてください。
たとえば111の37乗%323という計算をする場合は次のように計算させます
111の2乗%323=111*111%323=2321%323=47
111の3乗%323=111*47%323=5217%323=49
111の4乗%323=111*49%323=5439%323=271
・
111の37乗%323=111*305%323=33855%323=263
このように計算させることにより圧倒的に計算量が少なくなります。
|
 |
