特許

J-GLOBAL ID：200903055360529945

逆元計算装置及び逆元計算方法

発明者： 川村 信一
出願人/特許権者： 株式会社東芝
代理人 (1件)： 鈴江 武彦 (外6名)
公報種別：公開公報
出願番号（国際出願番号）：特願平9-014166
公開番号（公開出願番号）：特開平10-207689
出願日： 1997年01月28日
公開日（公表日）： 1998年08月07日
要約：

【要約】【課題】 逆元計算を除算を用いることなく規則正しく効率良く行なう逆元計算装置を提供すること。【解決手段】 第1の正整数N(Nはqのs乗;q、sはそれぞれ正の整数)を法として、第1の正整数Nと互いに素である第2の正整数Aの逆元Xを求める逆元計算装置であって、q進数で表現した整数Aの最下位桁のqを法とする逆元と、q進数で表現した中間結果の最下位桁のqの補数との(初回のみ1との)、qを法とする乗算結果を求める第1の演算手段と、第1の演算手段で求められた値と整数Aとの積と、中間結果(中間結果の初期値は0)とを加算し、この加算結果を最下位桁を捨てて右に1桁シフトし、このシフト結果を新たな中間結果とする第2の演算手段と、第1の演算手段と第2の演算手段を交互に繰り返し実行させた結果、第1の演算手段で逐次求められるs個の値を逆元Xの最下位桁から最上位桁へと順に対応付けて保持する保持手段とを備えたことを特徴とする。

請求項（抜粋）：

第1の正整数N=qs を法として(q、sはそれぞれ正の整数)、第1の正整数Nと互いに素である第2の正整数Aの逆元Xを求める逆元計算装置であって、q進数で表現した整数Aの最下位桁のqを法とする逆元と、q進数で表現した中間結果の最下位桁のqの補数との(初回のみ1との)、qを法とする乗算結果を求める第1の演算手段と、第1の演算手段で求められた値と整数Aとの積と、中間結果(中間結果の初期値は0)とを加算し、この加算結果を最下位桁を捨てて右に1桁シフトし、このシフト結果を新たな中間結果とする第2の演算手段と、第1の演算手段と第2の演算手段を交互に繰り返し実行させた結果、第1の演算手段で逐次求められるs個の値を、逆元Xの最下位桁から最上位桁へと順に対応付けて保持する保持手段とを備えたことを特徴とする逆元計算装置。

IPC (4件)：

G06F 7/00 ,  G06F 17/10 ,  G09C 1/00 650 ,  H03M 13/00

FI (4件)：

G06F 7/00 D ,  G09C 1/00 650 A ,  H03M 13/00 ,  G06F 15/31 Z