はじめに
1999年に世界一高速なRSA暗号のLSIを開発したが、その後、いろいろ研究していたときに見つけたのが7で割った余りを高速に演算する論理だった。
今では高校の数学で整数の性質で習う合同式を使えば簡単に証明できるが、それは2014年以降の話で、2000年頃にはまだそういうものはなかった。
3で割った余りが何の役に立つの？
LSIではノイズや宇宙線によってビットが反転し正しく動作しないことがある。パリティによってチェックすることもあるが乗算器のビット反転はパリティでは不可能だ。
乗算器を2重化すればいいが、トランジスタ数が増大する。そこでレシジュという方法が用いられていた。乗数と被乗数の3で割った余りを乗算して、乗算結果と比較するのだ。
3で割った余りどうしの乗算なので2bitの乗算器程度のトランジスタ数でいいためトランジスタ数の増大を防げる。
このときあった3で割った余りを計算する演算器を5、7に応用したのが「3、5、7で割った余りを計算する演算器」です。
3で割った余りを計算してくれる演算器に証明がついていれば良かったのだが、そういう便利なものはなく、自分で証明するしかなかった。ちなみに15で割った余りも可能です。
「すべてがFになる(計算機工学版)」がなぜ計算機工学なのかは、そういう理由からです。
3、5、7で割った余りが何の役に立つの?
3ではなく5や7で割った余りを使えば乗算器の誤りを検出する精度が上がる。が、それはおいておいて
素数判定をするにはミラー・ラビン素数判定法のような確率的アルゴリズムでも時間のかかる処理です。
そういった時間のかかる素数判定の前処理として「3、5、7で割った余りを計算する演算器」を使えば素数判定を高速化できる、、、と思っていた。
事実、GNUのGMPというライブラリでmpz_nextprime()という関数は3、5、7のような小さい素数で割り切れるかをテストしている。
しかし与えられた数よりも大きい素数を探すのに毎回、3、5、7で割れるかを判定しているわけではなく、前回の結果を記録しておいて、
増分を計算して判定するため、「3、5、7で割った余りを計算する演算器」の高速性は活かされないことが判明した。
VHDLなどの論理シミュレータでレシジュのシミュレーションを高速化できるなどの超マイナーな用途は、見つけたが、みなさんにも
考えてもらえるといいかなぁと。
7で割った余りを高速に演算する方法
7で割った余りが演算できることの証明
計算機なので2進数です。3bitづつにまとめて8進数で考えます。
8進数は
と表せます。
mが1以上の任意の整数に対して次が成り立ので
あとはAnからA0を7で割った余りを求めながら加算していけば答えが計算されます。
これは7以外の3、15、31でも同じ方法で証明できます。
3,5で割った余りは、どうするの？
3だけなら7と同じ方法でいいのですが15で割った余りを計算してから3と5で割った余りを計算すると
一度に3,5が計算できます。
最後に
ここにあるような余りを求める計算など整数の性質が実社会で何の役に立つか？
僕の経験を話します。
IBMの暗号LSIを買ってきて日立の大型コンピュータの暗号装置として製品化することがあった。
国内向けの需要で暗号LSIから秘密鍵をバックアップできる必要があった。
しかしIBMが、その方法を教えてくれるはずもなかった。
なぜなら秘密鍵の盗難の方法を教えるのと同じだからだ。
別の暗号装置にリストアすることはできないが、同一の暗号装置ならバックアップできる方法はあった。
暗号装置にRSAの公開鍵暗号を設定することで、それが可能になる。
説明は省略するがRSAの鍵は周期が大きくなるように作る。
そこに敢えて1とnを繰り返す周期の鍵を設定する。
暗号装置内部で生成される乱数によって1かnかになる。確率50%で1になる。
1であることがわかれば、それを利用してバックアップする方法が見つかった。
確率50%では、何度か繰り返せば、普通にバックアップが可能だ。
この話が整数の性質の学習の動機付けになればと思います。
