特許
J-GLOBAL ID：200903040543910250
べき積演算装置
発明者：
,
出願人/特許権者：
代理人 (1件)：
小鍜治 明 (外2名)
公報種別：公開公報
出願番号（国際出願番号）：特願平3-312079
公開番号（公開出願番号）：特開平5-150722
出願日： 1991年11月27日
公開日（公表日）： 1993年06月18日
要約：
【要約】【目的】n個の正整数の組(Xi,Yi)(i=1,2,...,n)と正整数pに対して、pを法とする正整数の組(Xi,Yi)(i=1,2,...n) に対する次の演算Z=(X1Y1×X2Y2...×XnYn) modp を、比較的大きなnに対しても、計算量やメモリ容量が、nに対して指数関数的に増加することがない効率的なべき積演算装置を提供することを目的とする。【構成】入力分割部10と、グループ数決定部11と要素数決定部12とべき積計算部20とメモリー部21と乗算計算部30からなるべき積演算装置であり、11と12でn個の正整数の組(Xi,Yi)を、m(≧1)個のグループにnj(1≦nj≦n,n=n1+n2+...+nm)個ずつ分割し、それぞれに対して、20でべき積計算を行い、その各結果を30で乗算して所望する結果を得る。
請求項（抜粋）：
n個の正整数の組(Xi,Yi)(i=1,2,...,n) と正整数pを入力すると、前記正整数pを法とし前記正整数Yi(i=1,2,...,n)をそれぞれのべきとする前記正整数Xi(i=1,2,...,n) に対するべき積演算の結果Z=(X1Y1×X2Y2×...×XnYn) modpを出力するべき積演算装置であって、入力された前記n個の正整数の組(Xi,Yi)を、m(m≧1) 個のグループGj(j=1,2,...,m) に、それぞれnj(j=1,2,...,m)(但し1≦nj≦n,n=n1+n2+...+nm)個の正整数の組(Xi,Yi)(i∈Gj) ずつ分割する入力分割部と、前記入力分割部において、グループの個数mを決定するグループ数決定部と、前記各グループGj に分割される正整数の組の個数njを決定する要素数決定部と、前記各グループGjに分割された前記nj個の正整数の組(Xi,Yi)(i∈Gj)に対して、それぞれ前記正整数pを法とし、前記正整数Yi(i∈Gj)をそれぞれのべきとする前記正整数Xi(i∈Gj)に対するべき積演算の結果Zj=Πi (XiYi) modp (i∈Gj,j=1,2,...,m)を2値計算法(binary method)と呼ばれる計算法を用いて求めるべき積計算部と、 そのべき積計算部に付随するメモリー部と、前記正整数pを法とする前記各べき積演算の結果Zj(j=1,2,...,m) に対する乗算結果Z=(Z1×...×Zm) modpを求める乗算計算部を備えたべき積演算装置。
IPC (4件)：
G09C 1/00
, H04L 9/00
, H04L 9/10
, H04L 9/12
