特許
J-GLOBAL ID：200903048961970812
素数判定方法および装置
発明者：
出願人/特許権者：
代理人 (1件)：
澤田 俊夫
公報種別：公開公報
出願番号（国際出願番号）：特願平8-349047
公開番号（公開出願番号）：特開平10-187037
出願日： 1996年12月26日
公開日（公表日）： 1998年07月14日
要約：
【要約】【課題】 P-1法などの安全対策を施した法数を生成する場合でも、処理の始めに増加値剰余テーブルを作成することによって、以後繰り返される多倍長の計算を回避する。【解決手段】 ふるい法によって棄却された素数候補を増加させるための多倍長の整数を被除数、素数テーブルの要素を除数としたときの剰余を予め計算し、この値を増加値剰余テーブルとして保持する(203)。そしてこの増加値剰余テーブルの値を用いて、ふるい法に必要な素数テーブルの要素を法としたときの乱整数の剰余を求める計算を行う(303)。素数テーブルの要素の大きさを1ワードより数ビット小さくし、この増加値剰余テーブルの要素の大きさも1ワードより数ビット小さくする。乱整数の剰余の計算は1ワードで実行できる。
請求項（抜粋）：
整数Aに対し、整数Aとは異なる整数BまたはBの倍数分だけ整数Aと異なる整数の集合Cに属する要素の素数性を判定する素数判定方法において、整数BまたはBの倍数を被除数とし、一つまたは複数の整数を除数または除数集合とした場合の剰余または剰余の集合を記憶手段に記憶するステップと、集合Cの要素を生成するステップと、生成された集合Cの要素に対し、対応する剰余を上記記憶手段から取り出すステップと、上記記憶手段から取り出された剰余を用いて、上記生成された集合Cの要素を被除数とし上記一つまたは複数の整数を除数とした場合の剰余を算出するステップとを有することを特徴とする素数判定方法。
IPC (4件)：
G09C 1/00 650
, G09C 1/00 620
, G06F 17/10
, G06F 7/544
G09C 1/00 650 Z
, G09C 1/00 620 B
, G06F 7/544 Z
, G06F 15/31 Z
