Top / 掛け算処理

掛け算処理

目次 †

足し算による掛け算処理 †

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

1. 3+3+3+3+3（3を5回足す）
2. 5×5×5（5を3回足す）

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

CASL�兇両豺� †

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

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24

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」と表示する。

シフト演算利用による掛け算処理 †

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

CASL�兇両豺� †

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

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23

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       

高速べき乗法 †

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

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

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

p=ak　（a,k,pは正の整数）

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

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

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

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

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

例：p=320を計算する（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（=31）

[2]左から2ビット目に対して
(a)p=p×p=3×3=9（=32）

[3]左から3ビット目に対して
(a)p=p×p=9×9=81（=34）
(b)p=p×a=81×3=243（=35）

[4]左から4ビット目に対して
(a)p=p×p=243×243=59,049（=310）

[5]左から5ビット目に対して
(a)p=p×p=59,049×59,049=3,486,784,401（=320）

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

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

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

改良された高速べき乗法 †

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

　以下xk-1=1と仮定する。

　まずy=aとおく。

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

[Step1]

[Step2]xi=1なら、

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

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

例：x=19=(10011)2

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

参考文献 †

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