説明をする太田さん
証明をする太田さん
前幹事の並木さん. お疲れさまでした
東京工業大学大岡山キャンパスは，東急目蒲線/大井町線
大岡山駅下車徒歩１分です．
会場の西７号館までは正門横の学内地図を参考にお越し
ください．
西７号館入口までお越しいただければ，会場の204号室
までは簡単に到達できます．詳しくは
東京工業大学のページを御覧下さい.
公開鍵暗号系の基本演算は、多倍長ｍｏｄｕｌａｒ整数乗算とべ き乗である。これらの演算を高速に行う方式として、前処理や後処理に より数の表現システムを変換するＭｏｎｔｏｇｏｍｅｒｙのものが知ら れているが、もっと単純で直接的な方式が同程度に高速であることを示 す。また、Ｍｏｎｔｏｇｏｍｅｒｙの方式の高速インプリメンテーショ ンとして知られている方式も、実はあまり早くないことも示す。
駅周辺で食事ができます．会場に持ち込む場合は，駅前の マクドナルドかパン屋で調達することになるでしょう．
説明をする太田さん
証明をする太田さん
前幹事の並木さん. お疲れさまでしたある種の大きな数（数百〜数千ビット）のｍｏｄに関する乗算や冪乗演算は、 公開鍵暗号系の基礎であるが、冪乗演算は普通にやると桁数（以下Ｎビットとす る）の三乗に比例する時間がかかるため、その演算の高速化は極めて重要である。発表者である太田は、前野年紀（東工大総合情報処理センター）と共同で、多 倍長整数乗算をレジスタブロッキングという手法で高速に行う方式を発見してい た。レジスタブロッキングは、行列の乗算の高速化では比較的よく知られた手法 である。計算中に二重ループがあるとき、それぞれＫ回の繰り返しのループと残 りの部分に分割して４重ループとし、ループの順序を入れ替えることにより、内 側をＫ＊Ｋ回の二重ループとし、それをインライン展開すると、いちどキャッシ ュからレジスタに読んだデータをＫ回再利用でき、書き込みの回数も１／Ｋにな る場合がある。この手法が多倍長乗算の場合にも適用でき、演算回数はＯ（Ｎ＊ ＊２）とかわらないが、メモリの読みだし／書き込みの回数はＯ（Ｎ＊＊２／Ｋ） となるため、ＲＩＳＣ ＣＰＵのように多数のレジスタがある場合、ＣＰＵの演 算性能をほとんどすべて引き出すことができる。
数千ビット程度では、Ｋａｒａｔｓｕｂａの方法やＦＦＴによる方法などのよ り計算量のオーダが少ない方式と比べても、この方式のほうが勝れていることも わかっている。
ここで、Ａ＊Ｂ（ｍｏｄ Ｍ）という計算を単純に行うことを考えると（「Ｘ」 で、ｆｌｏｏｒ演算（を超えない最大の整数）を表すとする：
Ａ＊Ｂ−「Ａ＊Ｂ／Ｍ」＊Ｍ
という計算をしなければいけないが、これには乗算２回と除算１回が必要である。 Ｍによる除算には、かなり時間がかかる。ここで、従来知られているＭｏｎｔｇｏｍｅｒｙの方法［１］というのは、Ｒ ＥＤＣ（）という同型変換とその逆変換を導入し、単純な方法のかわりに変換し た形での乗算結果にＲＥＤＣを一度施せばいいというものである。ＲＥＤＣは、 ２回の乗算と最後に結果を１程度補整する操作が必要だが、除算は２の冪乗によ るものであり、単純にシフト操作となる。
しかし、十分大きな２の冪Ｔ（Ｔ＞＝Ｍ＊＊２）を用いれば、「Ａ＊Ｂ＊「Ｔ ／Ｍ」」／Ｔは、「Ａ＊Ｂ／Ｍ」と同じか高々１しか異ならないし、「Ｔ／Ｍ］ は最初に一度だけ計算しておけばいいので、ＲＥＤＣなどというややこしい変換 は実は不用だということが、今回の発表の中核である。
Ｍｏｎｔｇｏｍｅｒｙの方式には、さらに結果のある個所が０になる等の性質 を使って演算回数をへらす工夫がしられているが、実はループアンローリングを 使ったほうがより速くなる。しかも、今回発表した方式も、Ｔ＞＝Ｋ＊Ｍ＊＊２ （Ｋ＞１）とすれば、定数ファクターも含めて同程度に効率的となるので、結局 Ｍｏｎｔｇｏｍｅｒｙの方式にはとくにメリットはない。
参考文献：
［１］喬木直史、「算術演算回路のアルゴリズム ４．初等関数計算回路のアル ゴリズム −専用回路の実現に向けて−」、情報処理、Ｖｏｌ．３７、Ｎｏ．４、 １９９６。
質疑応答:
いくつかでましたが、覚えているのは、
問：ニュートン法による除算は速いのでは？
答：もちろんニュートン法は使うであろうが、定数ファクターが大きい ので、遅い。公開鍵暗号の処理には、２倍の差でも大きい。 問：インプリメントして速度比較するのか？
答：Ｍｏｎｔｇｏｍｅｒｙなんて、できたらインプリメントしたくない。
問：十分大きな２の冪Ｔ（Ｔ＞＝Ｍ＊＊２）を用いれば、「Ａ＊Ｂ＊「 Ｔ／Ｍ」」／Ｔは、「Ａ＊Ｂ／Ｍ」と同じか高々１しか異ならない、を 証明して欲しい。
答：黒板で証明しました。