モンゴメリ除算装置及びモンゴメリ逆元計算装置並びにモンゴメリ除算方法及びモンゴメリ逆元計算方法

発明者：
出願人/特許権者：
代理人 (1件)：鈴江武彦 (外6名)
公報種別：公開公報
出願番号（国際出願番号）：特願平10-014250
公開番号（公開出願番号）：特開平10-269060
出願日： 1998年01月27日
公開日（公表日）： 1998年10月09日
要約：

【要約】【課題】本発明は、モンゴメリ演算域での除算結果を高速に求めることのできるモンゴメリ除算装置を提供すること。【解決手段】正の整数N、正の整数A(0≦A<N、AとNは互いに素)、正の整数Bについて、Nを2進表現したときのビット長をLとして、n≧Lなる整数nに対して、Y=B・A^(-1)・2^n mod Nなるモンゴメリ演算域での除算結果Yを求めるモンゴメリ除算装置であって、整数Aと法Nを入力として逆元X=A^(-1)・2^(2n) mod Nを求めるモンゴメリ逆元計算部と、求められた逆元Xと法NとBを入力として除算結果Y=B・X・2^(-n) mod Nを求めるモンゴメリ乗算部とを備えたことを特徴とする。

請求項（抜粋）：

正の整数N、正の整数A(0≦A<N、AとNは互いに素)、正の整数Bについて、Nを2進表現したときのビット長をLとして、n≧Lなる整数nに対して、Y=B・A<SP>-1</SP>・2<SP>n </SP> mod Nなるモンゴメリ演算域での除算結果Yを求めるモンゴメリ除算装置であって、整数Aと法Nを入力として逆元X=A<SP>-1</SP>・2<SP>2n</SP> mod Nを求めるモンゴメリ逆元計算手段と、求められた逆元Xと法NとBを入力として除算結果Y=B・X・2<SP>-n</SP> modNを求めるモンゴメリ乗算手段とを備えたことを特徴とするモンゴメリ除算装置。

IPC (3件)：

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

FI (3件)：

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

前のページに戻る