特許
J-GLOBAL ID：201103041487342779
モンゴメリ乗算装置及び方法
発明者：
,
出願人/特許権者：
代理人 (7件)：
鈴江 武彦
, 村松 貞男
, 坪井 淳
, 橋本 良郎
, 河野 哲
, 中村 誠
, 河井 将次
公報種別：特許公報
出願番号（国際出願番号）：特願2000-137182
公開番号（公開出願番号）：特開2001-318785
特許番号：特許第3554525号
出願日： 2000年05月10日
公開日（公表日）： 2001年11月16日
請求項（抜粋）：
【請求項1】正の整数Nと、N未満の正の整数x,yとを入力とし、剰余演算系の基底を{a1,a2,...,ai,...,an}および{b1,b2,...,bi,...,bn}(1≦i≦n、nは正の整数)としたとき、前記基底の要素の乗積として定義された整数B(=b1b2...bn)を用いて、出力w=xyB-1mod Nを算出するためのモンゴメリ乗算装置であって、前記各基底の要素{a1,a2,...,an}および{b1,b2,...,bn}と前記出力wの算出用の事前計算結果とが記憶される第1記憶手段と、前記基底の拡張用の入力ξiを受けたとき、前記入力ξiの上位qビットを抽出すると共に、この今回の抽出値と前回の最上位ビットを除く加算結果とを加算し、得られた加算結果のうち、最上位ビットの値kiを出力する近似演算手段と、前記第1記憶手段の内容および前記近似演算手段の出力kiに基づいて、前記各基底の要素{a1,a2,...,an}および{b1,b2,...,bn}を法mとする剰余算(但し、法m=2r-μは基底の一要素、rはm≦2rを満たす整数、μは2r未満の非負整数)を実行する剰余演算手段と、前記剰余演算手段による剰余算の結果が記憶される第2記憶手段とを備え、前記剰余演算手段は、前記第1記憶手段又は前記第2記憶手段からの入力x,yの積xyと前回の剰余算の結果dと前記近似演算手段の出力kiに基づき入力される前記事前計算結果cとの和(xy+d+c)からなる入力z(但し、zは正の整数)を受けると共に、前記入力zの法mによる剰余算h=z mod mを実行する剰余算部と、前記剰余算部による実行結果h’と前記法mの上限値2rとを比較し、前記実行結果h’が2r以上のときには当該実行結果h’を前記入力zとして前記剰余算部に戻し、前記実行結果h’が2r未満のときには当該実行結果h’を前記剰余算の結果hとして前記第2記憶手段に出力するループ制御部と、を備えたことを特徴とするモンゴメリ乗算装置。
IPC (2件)：
FI (2件)：
G06F 7/72
, G09C 1/00 650 A
