- 55 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/05 22:37]
- M→C'は問題ないと思いますのでC'→Cの求め方
label1:
cZ+c"=dW+d"…壱
となる最小の値を(cd)"とします。
壱を少し変形して
cZ-dW=d"-c"…弐
拡張ユークリッドの互除法を用いて
cZ'-dW'=1となるZ'またはW'を求めます。
両辺d"-c"倍してやって
c(Z'*(d"-c"))-d(W'*(d"-c"))=d"-c"…参
弐と参を比較して
Z=Z'*(d"-c") W=W'*(d"-c")
∴壱は
cd*Z_W+(cd)"=cZ+c"=dW+d"(Z_Wは0以上の整数)
と表されます。
今度は
cd*Z_W+(cd)"=bY+b"
となるような最小の値(bcd)"を求めます。
goto label1;
と、どんどん繰り返していってCが求めれます。
復号はこの逆を行えばいいわけです。
