●学生部門の入賞の設計概要について

２）優勝（半導体産業新聞社賞・LSI of the Year for Student）team CREW-ITB

  さて、もうひとつのインドネシアteam CREW-ITBの設計の基本方針は、剰余演算をモンゴメリ剰余算を用いて実装しているところにあります。モンゴメリ剰余算を用いると、剰余演算を高速で実現できるメリットがあります。しかし、入力の平分などの整数を前準備として変換する余分な回路が必要になる課題があります。
  モンゴメリ剰余算では、乗算を行うＡ，ＢとmoduloをとるＭに対して、以下のようなＲを選択します。

  このとき、
Mont(A,B) =
なる演算がモンゴメリ剰余算であり、回路での実装がシンプルに実現できることが知られています。
とすると、 　　　　　　　　　　　　　　

であるので、計算量の少ないモンゴメリ剰余算が利用できることがわかります。このモンゴメリ剰余算を利用して、

を計算する方法をコード３に示します。モンゴメリ剰余算Mont()が高速に実行できるので、ＲＳＡ暗号計算が高速に実行することができます。

（コード３）

さらに、team CREW-ITBは計算要素であるモンゴメリ剰余算Mont(A,B)をコード４に示すＣＳＡを用いた方式で実装しました。結果的に、このチームも非常に大きなビット幅でも動作する回路を設計し、その高速性能で優勝に選ばれました。

（コード４）