このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ
  • 追加された行はこの色です。
  • 削除された行はこの色です。
  • 掛け算処理 へ行く。

*目次 [#q9a7c10d]

#contents

*足し算による掛け算処理 [#te34a10e]

 例えば、「3×5」を足し算で処理することを考える。

+3+3+3+3+3(3を5回足す)
+5×5×5(5を3回足す)

 ,茲雖△里曚Δ計算回数が少ない。


**CASL兇両豺 [#se8205de]

例:M(A)×M(B)を求めて、ANS番地に格納する。ただし、数値は正とする。

#code(asm){{
SMP0311   START     
          LD        GR0,=0
          LD        GR1,=1
          LD        GR3,A
          LD        GR4,B
          CPA       GR3,GR4
          JMI       LOOP
          JZE       LOOP
          LD        GR5,GR3
          LD        GR3,GR4
          LD        GR4,GR5
LOOP      ADDA      GR0,GR4
          JOV       OVF
          SUBA      GR3,GR1
          JPL       LOOP
          ST        GR0,ANS
          RET       
OVF       OUT       OVERFLOW,M8
A         DC        5
B         DC        3
ANS       DS        1
OVERFLOW  DC        'OverFlow'
M8        DC        8
          END       

}}

 最初のCPA命令とJMI命令とJZE命令のセットで、GR3とGR4の大小比較をしている。GR4が大きいようにして掛け算用のループで計算回数を少なくするためである。仮にGR4のほうがGR3より小さい場合は、GR5を作業用のレジスタとして活用して、GR3とGR4の中身を入れ替えている。なお、足し算のときオーバーフローが発生したら「OverFlow」と表示する。

*シフト演算利用による掛け算処理 [#yab0416d]

 ひとつ左シフトすると2倍されるが、うまく利用することで任意の掛け算を処理できる。

**CASL兇両豺 [#lb149c91]

例:M(A)×M(B)を求め、ANS番号に格納する。

#code(asm){{
SMP0321   START     
          LD        GR0,=0
          LD        GR3,A
          LD        GR4,B
LOOP      LD        GR1,GR3
          AND       GR1,MASK
          JZE       STEP
          ADDA      GR0,GR4
          JOV       OVF
STEP      SLL       GR4,1
          SRL       GR3,1
          JNZ       LOOP
          ST        GR0,ANS
          RET       
OVF       OUT       OVERFLOW,M8
          RET       
A         DC        3
B         DC        20
ANS       DS        1
MASK      DC        #0001
OVERFLOW  DC        'OverFlow'
M8        DC        8
          END       

}}


*高速べき乗法 [#zb9cdf81]

 [[ElGamal暗号]]、[[RSA暗号]]、[[Miler-Rabinテスト]]を解読するには次の合同方程式のタイプ(法がかかっていることに注意)のべき乗計算をする必要がある。

&mimetex("y=a^x \, \(mod \, n\)");

 単純な方式だとx-1回の乗算を行うことになってしまう。x-1≒2SUP{κ};なので指数時間がかかる。これでは多項式時間の計算しかできないアタッカー(poly-timeアルゴリズム)は歯が立たない。

 次のアルゴリズムで処理することで、計算量を減らすことができる。

p=aSUP{k}; (a,k,pは正の整数)

[]pに対して、p←1と初期値を代入する。

[]kの2進ビットパターンを上位ビットから1ビットずつ見ていき、各ビットに対して次を処理する。

(a)まずpを2乗する。~
p←p×p

(b)そのビットが1なら、さらにaをかける。~
p←p×a

 もし、法nで考えているなら、処理ごとに法nを適用する。そうすれば空間量も減らすことができる。

例:p=3SUP{20};を計算する(a=3,k=20)。

[]p=1

[]20の2進数は10100であるので、

[1]一番左のビット1に対して~
(a)p=p×p=1×1=1~
(b)p=p×a=1×3=3(=3SUP{1};)

[2]左から2ビット目に対して~
(a)p=p×p=3×3=9(=3SUP{2};)

[3]左から3ビット目に対して~
(a)p=p×p=9×9=81(=3SUP{4};)~
(b)p=p×a=81×3=243(=3SUP{5};)

[4]左から4ビット目に対して~
(a)p=p×p=243×243=59,049(=3SUP{10};)~

[5]左から5ビット目に対して~
(a)p=p×p=59,049×59,049=3,486,784,401(=3SUP{20};)

 p=3SUP{20};を単純計算すると19回乗算することになる(3に3を19回かけていく)。しかし、このアルゴリズムに適応してみると、7回の乗算で済んだはずだ。

&mimetex("\( \( \( 3^{2} \)^{2} 3 \)^{2} \)^{2}");

 この例のように2進数の桁が5のときは、最悪の場合でも10回の乗算で済むのである。

 指数をNとすると、普通の計算ではO(N)であるが、この方法だとO(logN)の計算量で済んでしまう。


*改良された高速べき乗法 [#we05e8a2]

 通常の高速べき乗法で使用する変数を減らすことができる。

 以下xSUB{k-1};=1と仮定する。

 まずy=aとおく。

 次にi=k-2から0まで以下を繰り返す。

[Step1]&mimetex("y_{i}=y^{2} \, \( mod \, n \)");

[Step2]xSUB{i};=1なら、&mimetex("y=y \times a \, \( mod \, n \)");

 このようにすると使用する変数はyのみで済む。

 このアルゴリズムにおける乗算回数は、x=(1,…,1)のとき最大となり2(k-1)回、平均で1.5(k-1)回である。

例:x=19=(10011)SUB{2};

&mimetex("y \overset{2}{\leftarrow} a^{2} = a^{\( 10 \)_{2}} \, \( mod \, n \)");

&mimetex("y \overset{2}{\leftarrow} y^{2} = a^{\( 100 \)_{2}} \, \( mod \, n \)");

&mimetex("y \overset{1}{\leftarrow} y^{2} \times a = a^{\( 1000 \)_{2}} \times a = a^{\( 1001 \)_{2}} \, \( mod \, n \)");

&mimetex("y \overset{1}{\leftarrow} y^{2} \times a = a^{\( 10010 \)_{2}} \times a = a^{\( 10011 \)_{2}} \, \( mod \, n \)");

 このとき、乗算回数は計6回である。


*参考文献 [#xa7ab7e0]

-『現代暗号の基礎数理』
-『情報処理試験 CASLII 〜CASLIIの講義と実習〜 [第2版]』