特許

J-GLOBAL ID：200903086676236004

剰余演算装置及び方法

発明者： 小池 正修 ,  川村 信一
出願人/特許権者： 株式会社東芝
代理人 (1件)： 鈴江 武彦 (外6名)
公報種別：公開公報
出願番号（国際出願番号）：特願2000-153379
公開番号（公開出願番号）：特開2001-337815
出願日： 2000年05月24日
公開日（公表日）： 2001年12月07日
要約：

【要約】【課題】 ぺリラーの方法と同程度の処理速度を維持しつつ、プログラムを簡略化する。【解決手段】 各基底の要素{a1,a2}および{b1,b2}が記憶されるROM20と、出力wの算出用の事前計算結果が記憶されるRAM10と、ROM20の内容に基づいて、各基底の要素{a1,a2}および{b1,b2}を法とする剰余乗算及び/又は加減算を実行する積和回路50と、積和回路50による演算結果が記憶されるRAM10とを備えている。ここで、基底の各要素として、a1=2r、a2=2r-1、b1=2r-3、b2=2r-1-1を用いる。

請求項（抜粋）：

どの2つも互いに素な4つの正の整数をa1,a2,b1,b2とし、整数A=a1a2、整数B=b1b2とし、剰余演算系の基底を{a1,a2}および{b1,b2}としたとき、前記整数A,Bのいずれよりも小さい正の整数Nと、N未満の正の整数x,yとを入力とし、前記整数Bを用いて、出力w=xyB-1mod Nを算出するための剰余演算装置であって、前記各基底の要素{a1,a2}および{b1,b2}が記憶される第1記憶手段と、前記出力wの算出用の事前計算結果が記憶される第2記憶手段と、前記第1記憶手段の内容及び/又は前記第2記憶手段の内容に基づいて、前記各基底の要素{a1,a2}および{b1,b2}を法とする剰余乗算及び/又は加減算を実行し、得られた演算結果を前記第2記憶手段に記憶させる演算手段とを備え、前記基底の各要素は、rを正の整数としたとき、a1=2r、a2=2r-1、b1=2r-3、b2=2r-1-1であることを特徴とする剰余演算装置。

IPC (5件)：

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

FI (5件)：

G06F 7/72 ,  G06F 17/10 Z ,  G09C 1/00 650 A ,  H03M 7/18 ,  H03M 13/01

Fターム (15件)：

5B056AA06 ,  5B056BB71 ,  5B056FF02 ,  5B056FF05 ,  5B056FF10 ,  5B056HH00 ,  5J065AC03 ,  5J065AF01 ,  5J065AG01 ,  5J065AH02 ,  5J065AH04 ,  5J065AH09 ,  5J104AA20 ,  5J104AA21 ,  5J104NA17