TOP > 技術シーズ検索 > 剰余系の計算方法及び装置並びにプログラム

剰余系の計算方法及び装置並びにプログラム

シーズコード S110005108
掲載日 2011年1月4日
研究者
  • 高木 直史
  • カイハラ、マルセロ エミリオ
技術名称 剰余系の計算方法及び装置並びにプログラム
技術概要 剰余系を新たに定義する領域に変換し、乗数を上位部分と下位部分とに分割した場合に、剰余演算の部分で上位部分、下位部分ともに計算の桁数を減らして並列計算ができるようにし、計算の高速化を可能にする。図に示すように、剰余系における変数U,Vを新たに定義する領域では、各々X=U・RmodM、Y=V・RmodMに変換する。乗算剰余演算装置は、r進の整数Mを法とする剰余系において(ただし、Mとrとは互いに素)、法M、r進でn桁の変数Y及び変数Xが入力されたときに変数Yを上位(n-m)桁のY及び下位m桁のYに分割する分割手段と、変数Yを分割した上位(n-m)桁のY、変数X及び法MでX・YmodMを計算して出力する第1乗算剰余算器と、変数Yを分割した下位m桁のY、変数X及び法MでX・Y・r-mmodMを計算して出力する第2乗算剰余算器と、第1乗算剰余算器の出力及び第2乗算剰余算器の出力を加算し、その加算結果を出力する加算器とを備える。更に加算器の加算結果を入力し、法Mによる剰余算を行って出力する剰余算器を備える。
画像

※ 画像をクリックすると拡大します。

thum_2005-242956.gif
研究分野
  • 演算方式
  • 符号理論
  • データ保護
展開可能なシーズ 剰余系における乗算剰余算の繰り返し計算をサイクル時間を増すことなく高速化するための計算方法を提供する。
剰余系の演算を新たに定義した領域において計算しようとすると、変換や逆変換が必要となるものの、乗算剰余算において乗数Yを上位部分Yと下位部分Yとに分けて計算できるので、例えば公開鍵暗号等の計算のように、剰余系において乗算剰余算を繰返し行わなければならない計算を高速化することができる。
用途利用分野 公開鍵暗号システム、データセキュリティ
出願特許   特許 国際特許分類(IPC)
( 1 ) 学校法人名古屋大学, . ▲高▼木 直史, カイハラ、マルセロ エミリオ, . 剰余系の計算方法及び装置並びにプログラム. 特開2007-057811. 2007-03-08
  • G09C   1/00     

PAGE TOP