特許

J-GLOBAL ID：200903071954380866

逆元計算装置及びそのプログラム記録媒体

発明者： 青木 和麻呂 ,  植田 広樹
出願人/特許権者： 日本電信電話株式会社
代理人 (1件)： 草野 卓 (外1名)
公報種別：公開公報
出願番号（国際出願番号）：特願平11-010788
公開番号（公開出願番号）：特開2000-206881
出願日： 1999年01月19日
公開日（公表日）： 2000年07月28日
要約：

【要約】【課題】 ソフトウェア実装でマスク処理を削減し、高速処理を可能とする。【解決手段】 a、bを補助変数とし、x、y、a、bのビット長をm=2n (n≧1)とする。xを入力し、初期処理として、b:=[x/2]([x]はxを越えない最大整数)、a:=bの最下位ビット、b:=[(ax+b)/2]、y:=xの下位2ビットとし、i=1,2,...,n-1に対し、a:=-by,b:=[(b+ax)/(2^(2i ))],y:=y+a2^(2i )(p^qはpのq乗を表わす)を繰返し演算し、その後、yをxのmod2m での逆元として出力する。

請求項（抜粋）：

入力されたxを記憶手段に記憶する入力手段と、整数n、i(nは1以上)および2n ビットの整数x、y、a、bを記憶する記憶手段と、記憶手段に記憶されたxを用いて[x/2](ただし[x]はxを越えない最大の整数)を演算し、演算結果をbとして記憶手段に記憶するb初期化第1手段と、記憶手段に記憶されたbの最下位ビットをaとして記憶手段に記憶するa初期化手段と、記憶手段に記憶されたa、x、bを用いて[(ax+b)/2]を演算し、その演算結果により、記憶手段に記憶されたbを更新するb初期化第2手段と、記憶手段に記憶されたxの下位2ビットを取得してyとして記憶手段に記憶するy初期化手段と、記憶手段に記憶されたiを1にセットするi初期化手段と、記憶手段に記憶されたb、yを用いて-byを演算し、その演算結果により、記憶手段に記憶されたaを更新するa更新手段と、記憶手段に記憶されたa、b、x、iを用いて[(b+ax)/(2^(2i))]を演算し、その演算結果により、記憶手段に記憶されたbを更新するb更新手段と(但しp^qはpのq乗を表わす)、記憶手段に記憶されたa、y、iを用いてy+a×2^(2i )を演算し、その演算結果により、記憶手段に記憶されたyを更新するy更新手段と、記憶手段に記憶されたiをi+1に更新するi更新手段と、記憶手段に記憶されたi、nを読み出し、i=nになるまで上記a更新手段、上記b更新手段、上記y更新手段、上記i更新手段を順次動作させる制御手段と、記憶手段に記憶されたyを出力する出力手段と、を有することを特徴とする逆元演算装置。

IPC (3件)：

G09C 1/00 650 ,  G06F 7/72 ,  G06F 17/10

FI (3件)：

G09C 1/00 650 Z ,  G06F 7/72 ,  G06F 15/31 Z

Fターム (6件)：

5B056BB01 ,  5B056EE05 ,  5B056HH00 ,  5J104AA21 ,  5J104JA23 ,  5J104NA17

引用特許：

出願人引用 (1件)

• 逆元計算装置及び逆元計算方法
  公報種別：公開公報   出願番号：特願平9-014166   出願人：株式会社東芝