はじめに
今年の4月にFPGAをはじめたときにFPGAにDSP(乗算器)が多数あることを知った。 これでモンゴメリ乗算が高速化できるわけだがアルゴリズムをそのまま実装するとビット長の大きな累積加算が、ビット長とともに周波数が下がり性能がでない。 そこで分割して加算しても、正しい加算結果になるような方法を考えた。これを使ったSSLアクセラレータ ICF3-F(商用版)の実装を急いでいるところだが、証明もしておかないと、いけないかと思って、急いで公開することにしました。産業スパイによる海賊版を抑止する目的です。ちなみに他にも応用ができる方法ではないかと思います。 この証明にコメントしたい方が、いらしゃるのかわかりませんが、もしあれば公開日(2018年9月26日)の2日後、28日の午後12時からでお願いします。とりあえず、その記録は残すようにします。
問題
非負の整数の変数Aを2進数表現すると、最下位ビットからrビットづつ区切ってs個のブロックに分割して表現できる。
がrビットの場合はAはr×sビットの数を表現可能だが、が(r+1)ビットあってもr×sビットの数を表現できる。 最上位ビットを、それ以外をとするとになるが
として全加算してやればAは冗長性がなくなりr×s+2個のビットの数になる。 このような冗長性をもったAを考える。
--- (1)
--- (2)
t,uはnビットの数。B、Cはr×s-2ビットの数。 、と表す。
式(1)の右辺を計算した結果、任意のA、B、C、t、uにおいて、 同じ冗長性、すなわちが(r+1)ビットある左辺Aに正しく格納できることを証明せよ。
証明
式(1)右辺のカッコ内は
ここでとする。t,uがnビットであるからは最大でもr+n+2ビット。 の最上位ビットから2bitを、最上位ビットから2ビット、最下位ビットからnビットを除いたrビットを、 最下位ビットからnビットをとする。
--- (3)
(1)の右辺は
(3)より
k=0の項をシグマの外に出して整数にすると
ただしB、Cがr+n-2ビットなので必ず。
ここで式(2)の条件からr-nは2以上。 とするとはrビットの記憶素子を持つ1つの変数としてまとめられる。
これは(1)左辺のAとして次にようになる。
、ともにrビットの数なので加算してもr+1ビットの数である。k=0、k=s-1も同様にr+1ビット。 式(1)の右辺を計算した結果、同じ冗長性、すなわちが(r+1)ビットある左辺Aに正しく格納できる。
補足
実際の実装では最後に、全加算を行って冗長性をなくしてr×sビットのレジスタに格納します。 このとき桁あふれが発生する可能性がありますが、一般のCPUのレジスタと同じで桁あふれはアルゴリズム側の責任。 モンゴメリ乗算では最終的な計算結果はCの2倍以下になるので全加算後、r×sビットのレジスタに必ず格納できます。 計算過程においても、上記証明によって、桁あふれすることなく計算できていることがわかります。 この問題では積和の数が2個の場合ですがn個にした証明など一般化できるように思います。いづれまた。