(57)【特許請求の範囲】
【請求項１】
Ｘ2 ＝Ｘ1 ＋α（α＞０：正の整数）なる関係をもつ相異なる整数Ｘ1 とＸ2 が、ある整数Ｐを約数に持つかを判定する装置において、
Ａ＝Ｘ1 mod Ｐを計算する剰余演算手段と、
その演算結果Ａが０であればＸ1 はＰを約数に持つ、その演算結果Ａが０でなければＸ1 はＰを約数に持たないと判定する手段と、
上記演算結果Ａにαを加算する加算手段と、
その加算結果ＢがＰ以上か否かを判定する判定手段と、
その判定結果がＰ以上であればＢよりＰを減算し、減算結果をＢとし、そのＢがＰより小さくなるまでＰを減算する減算手段と、
上記Ｂの値が０であればＸ2 はＰを約数に持つ、上記Ｂの値が０でなければＸ2はＰを約数に持たないと判定する手段と、
を具備する約数判定装置
【請求項２】
正の整数Ｘ1 ，Ｘ2 ，…，Ｘk （Ｘ1 ＜Ｘ2 ＜…＜Ｘk ），Ｘ2 −Ｘ1 ＝α1 ，Ｘ3 −Ｘ2 ＝α2 ，…，Ｘk −Ｘk-1 ＝αk-1 なる有限個の整数から、整数Ｘ1 ，Ｘ2 ，…，Ｘk が、ある整数Ｐを約数に持つかを判定する装置において、
Ｂ1 ＝Ｘ1 mod Ｐを計算する剰余演算手段と、
計算結果Ｂ1 が０であればＸ1 はＰを約数に持つ、計算結果Ｂ1が０でなければＸ1 はＰを約数に持たないと判定する処理と、
Ｂi にαi を加算してＢi+1 を得る加算手段と、
Ｂi+1 がＰより小さいか否かを判定する第１判定手段と、
Ｂi+1 がＰ以上であればＢi+1 からＰを、減算してＢi+1 とし、Ｂi+1 がＰより小さくなるまで減算する減算手段と、
Ｂi+1 の値が０であればＸi+1はＰを約数に持つ、Ｂi+1 の値が０でなければＸi+1はＰを約数に持たないと判定する第２判定手段と、
をｉ＝１，２，…，ｋ−１の順に、各ｉについて上記加算手段と、第１判定手段と、上記減算手段と、第２判定手段とを行わせる制御手段と、
を具備することを特徴とする約数判定装置。
【請求項３】
整数Ｘ1 と整数Ｘ2 ＝Ｘ1 ＋α（αは正の整数）と整数Ｐとを入力する処理と、
Ａ＝Ｘ1 mod Ｐを計算する処理と、
計算結果Ａが０であればＸ1 はＰを約数に持つ、計算結果Ａが０でなければＸ1 はＰを約数に持たないと判定する処理と、
計算結果Ａにαを加算する処理と、
Ｂ＝Ａ＋αがＰ以上か判定する大小判定処理と、
その大小判定処理がＢがＰ以上と判定するとＢがＰを減算してその結果をＢとして上記大小判定処理に戻る処理と、
上記大小判定処理がＢがＰより小と判定すると、そのＢが０であればＸ2 はＰを約数に持つ、そのＢが０でなければＸ2 はＰを約数に持たないと判定する処理と、
をコンピュータに実行させるプログラムを記録した記録媒体。
【請求項４】
正の整数Ｘ1 ，Ｘ2 ，…，Ｘk （Ｘ1 ＜Ｘ2 ＜…＜Ｘk ，Ｘ2 −Ｘ1 ＝α1 ，Ｘ3 −Ｘ2 ＝α2 ，…，Ｘk −Ｘk-1 ＝αk-1 ）、Ｐを入力する処理と、
Ｂ1 ＝Ｘ1 mod Ｐを計算する処理と、
計算結果Ｂ1 が０であればＸ1 はＰを約数に持つ、計算結果Ｂ1が０でなければＸ1 はＰを約数に持たないと判定する処理と、
ｉ＝１を設定する処理と、
Ｂi にαi を加算してＢi+1 を得る加算処理と、
Ｂi+1 がＰより小さいか否か判定する判定処理と、
Ｂi+1 がＰ以上であればＢi+1 からＰを減算し、その結果をＢi+1 として上記判定処理に戻る減算処理と、
Ｂi+1 が０であればＸi+1 はＰを約数に持つ、Ｂi+1 が０でなければＸi+1 はＰを約数に持たないと判定する処理と、
ｉがｋ−１になったかを判定する処理と、
ｉがｋ−１より小さければｉを＋１してｉとして上記加算処理に戻る処理と
をコンピュータに実行させるプログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は複数の正の整数が、ある整数Ｐを約数に持つかを判定する装置及びそのプログラム記録媒体に関する。
【０００２】
【従来の技術】
１）ある整数Ｘがある整数Ｐを約数にもつか判定するには、Ｘmod Ｐを計算し、０となるかを判定すれば良い。ここで、Ｘ2 ＝Ｘ1 ＋αなる関係をもつ相異なる整数Ｘ1 とＸ2 が、ある整数Ｐを約数に持つかを判定する場合、
従来、Ｘ1 mod Ｐを計算し、
さらに、Ｘ2 mod Ｐを計算し、
それぞれが０となるかを判定していた。
【０００３】
２）複数の相異なる整数Ｘ1 ，Ｘ2 ，…，Ｘk が整数Ｐを約数にもつか判定する場合、
それぞれＸ1 ，Ｘ2 ，…，Ｘk に対して合計ｋ回の剰余演算を行い、
その演算結果が０であるかどうかにより判定していた。
【０００４】
【発明が解決しようとする課題】
上記に示したような従来の技術では解決できない課題を以下に示す。
課題１：従来技術１の場合、Ｘ1 mod Ｐを計算するために必要な計算量Ａ1 と同等以上の計算を、Ｘ2 mod Ｐに対して繰り返す事となり、Ａ1 よりも小さな演算量でＸ2 mod Ｐを求める事は不可能であった。
【０００５】
課題２：従来技術２の場合ｋ回の剰余演算が必要であって、これをｋ回より少ない回数の剰余演算で整数ＰがＸ1 ，Ｘ2 ，…，Ｘk の約数であるかどうかの判定を下す事は不可能であった。
一般に、加減算に比べて、剰余演算は非常に時間がかかる。このため、ある整数Ｘまたは複数の整数Ｘ1 ，Ｘ2 ，…，Ｘk が整数Ｐを約数に持つことを判定するためのアルゴリズムや回路構造が複雑になりソフトおよびハードウェアにおける実現のための資源が多分に必要であった。
【０００６】
【課題を解決するための手段】
請求項１の発明によれば、剰余演算手段によりＡ＝Ｘ1 mod Ｐが計算され、その計算結果Ａの値からＸ1 がＰを約数に持つかの判定がなされ、Ａにα（Ｘ2 ＝Ｘ1 ＋α）が加算され、その加算結果ＢがＰより大きいか否かが判定され、Ｐより大きければ、ＢよりＰを減算して、その結果をＢとし、そのＢがＰ以下になるまで減算がなされ、Ｐ以下の場合のＢの値からＸ2 がＰを約数に持つかの判定がなされる。
【０００７】
このように剰余演算は１回で済む。
請求項２の発明によればＸ1 ＜Ｘ2 ＜，…＜Ｘk ，Ｘ2 −Ｘ1 ＝α1 ，Ｘ3 −Ｘ2 ＝α2 ，…Ｘk −Ｘk-1 ＝αk-1 であって、Ｂ1 ＝Ｘ1 mod Ｐが計算され、その計算結果Ｂ1 からＸ1 がＰを約数に持つかが判定され、Ｂi+1 ＝Ｂi ＋αi の加算演算がなされ、Ｂi+1 がＰより小さいか否かの判定（第１判定）がなされ、Ｂi+1 がＰ以上であればＢi+1 からＰを減算してＢi+1 とし、Ｂi+1 がＰより小さくなるまで減算を行い、Ｂi+1 がＰより小さければそのＢi+1 の値が０であるか否かによりＸi+1 がＰを約数にもつか否かの判定（第２判定）がなされ、ｉ＝１，２，…，ｋ−１の順に、各ｉについて上記加算演算と、第１判定と、上記減算と、第２判定がなされる。
【０００８】
この場合も剰余演算は１回で済む。
【０００９】
【発明の実施の形態】
図１に請求項１の発明の実施例を示す。この実施例では正の整数Ｘ1 とＸ2 とＰがそれぞれ入力レジスタ１１，１２，１３に入力され、これら入力数値Ｘ1 ，Ｘ2 ，Ｐは制御部１４の制御のもとに、以下の各部が動作する。α決定部１５で、Ｘ1 とＸ2 の何れが大で、大きい方Ｘ2 から小さい方Ｘ1 を差し引いた値αが決定される。また剰余演算部１６でＡ＝Ｘ1 mod Ｐが演算され、加算部１７でＢ＝Ａ＋αが計算され、判定部１８でＢ＜Ｐか否かが判定され、減算部１９でＢ＝Ｂ−Ｐが計算され、判定部２１でＡ＝０か、Ｂ＝０かの各判定によりそれぞれＸ1 ，Ｘ2 がＰを約数にもつかの判定がなされる。各処理において必要に応じて記憶部２２に一時記憶する。
【００１０】
なお、入力としてはＸ1 とα（Ｘ2 ＝Ｘ1 ＋α）とＰとが入力される場合があり、この場合はα決定部１５は省略される。
次に図２を参照して図１の装置の動作を説明する。
Ｓｔｅｐ１：Ｘ1 ，Ｘ2 ，Ｐが取込まれる。
Ｓｔｅｐ２：α決定部１５でＸ1 とＸ2 の大小が判定され、その差αが決定される。この例ではＸ1 ＜Ｘ2 と判定されたとする。
【００１１】
Ｓｔｅｐ３：剰余演算部１６でＸ1 mod Ｐを計算し、
その値を、Ａとして記憶部２２に保存し、
Ｓｔｅｐ４：判定部２１でＡ＝０か否かを判定し、
Ａ＝０であれば、ＰはＸ1 の約数であると判定し（Ｓｔｅｐ５）、
Ａ≠０であれば、ＰはＸ1 の約数でないと判定する（Ｓｔｅｐ６）。
【００１２】
Ｓｔｅｐ７：加算部１７でＢ＝Ａ＋αを計算し、
Ｓｔｅｐ８：判定部１８でＡ＋αとＰを比較し、
Ｓｔｅｐ９：Ｂ＝Ａ＋α≧Ｐであれば、Ａ＋α＜Ｐとなるまで減算部１９でＢからＰを減じ、減じた結果をＢとし、
Ｓｔｅｐ１０：判定部２１でＢ＝０か否かを判定し、
Ｓｔｅｐ１１：Ｂ＝０であれば、ＰはＸ2 の約数であると判定し、
Ｓｔｅｐ１２：Ｂ≠０であればも、ＰはＸ2 の約数でないと判定する。
【００１３】
これにより、剰余演算は、最初の１回だけ実行すれば良い。
一般に、加減算に比べて、剰余演算は非常に時間がかかるため、Ｘ2 に対する約数判定処理はＸ1 に比べて非常に小さい時間で判定可能である。
次に請求項２の発明の実施例を説明しよう。図３にはその機能構成例を示し、図１と対応する部分に同一符号を付けてある。この実施例では正の整数Ｘ1 ，Ｘ2 ，…，Ｘk と、Ｐが入力され、これらＸi （ｉ＝１，２，…，ｋ）がそれぞれＰを約数としてもつかを判定する例であり、従ってα決定部１５では入力整数Ｘ1 ，…Ｘk を大小順に並べ、この例ではＸ1 ＜Ｘ2 ＜…Ｘk-1 ＜Ｘk であったとし、Ｘ2 −Ｘ1 ＝α1 ，Ｘ3 −Ｘ2 ＝α2 ，…，Ｘk −Ｘk-1 ＝αk-1 を求める。加算部１７ではＢi+1 ＝Ｂi ＋αi を計算し、判定部１８ではＢi+1 ＜Ｐかを判定し、減算部１９ではＢi+1 ＝Ｂi+1 −Ｐを計算し、判定部２１ではＢi ＝０かを判定する。この例では更にｉカウンタ２３が設けられ、ｉ＝１から＋１され、また判定部２４でｉ＝ｋ−１かの判定が行われる。
【００１４】
この装置の処理を図４を参照して説明する。
Ｓｔｅｐ１：Ｘ1 ，Ｘ2 ，…，Ｘk 、Ｐを取込み、
Ｓｔｅｐ２：α決定部１５でＸ1 ，…，Ｘk を大小順に並べ、かつその各隣接するものとの差、α1 ，α2 ，…，αk-1 を求める。
Ｓｔｅｐ３：剰余計算部１６でＢ1 ＝Ｘ1 mod Ｐを計算し、
その値を、Ｂ1 として記憶部２２に保存し、
Ｓｔｅｐ４：Ｂ1 ＝０かの判定を判定部２１で行い、
Ｓｔｅｐ５：Ｂ1 ＝０であれば、ＰはＸ1 の約数であると判定し、
Ｓｔｅｐ６：Ｂ1 ≠０であれば、ＰはＸ1 の約数でないと判定する。
【００１５】
Ｓｔｅｐ７：ｉカウンタ２３を１に初期化し、
Ｓｔｅｐ８：加算部１７でＢi+1 ＝Ｂi ＋αi を計算し、
Ｓｔｅｐ９：Ｂi+1 とＰを比較し、
Ｓｔｅｐ10：Ｂi+1 ≧ＰであればＢi+1 ＜ＰとなるまでＢi+1 からＰを減じ、減じた結果をＢi+1 とし、
Ｓｔｅｐ11：Ｂi+1 ＝０であるか否かを判定部２１で判定し、
Ｓｔｅｐ12：Ｂi+1 ＝０であれば、ＰはＸ2 の約数であると判定し、
Ｓｔｅｐ13：Ｂi+1 ≠０であれば、ＰはＸ2 の約数でないと判定する。
【００１６】
Ｓｔｅｐ14：ｉ＝ｋ−１か否かを判定部２４で判定し、
Ｓｔｅｐ15：ｉ＝ｋ−１でなければカウンタ２３を１加算し、ｉ＝ｉ＋１としてＳｔｅｐ８に戻る。ｉ＝ｋ−１であれば終了する。
上記方法は、判定したい整数の数が増えると効果が顕著となる。従来方法では、ｋ回の剰余演算が必要であるが、この実施例では１回の剰余演算のみで、後は加減算のみで済む。
適用例
例えば暗号技術、電子署名技術などの分野では素数を生成することがよく行われ、その素数の生成には乱数を素数生成して、その中から素数を選び出す。
【００１７】
この適用例では、任意乱数Ｘは素数候補でないかを判定する、以後、Ｘ＋α，Ｘ＋２×α，Ｘ＋３×α，…，Ｘ＋ｊ×αの順で素数判定を行う。ここで、α＝２の場合を挙げているが、αは必ずしも２でなくてもよい。また、αは必ずしも一定ではなく、素数候補Ｘに応じた適当な値としてもよい。
この素数生成装置の全体の機能構成を図５に示す。この装置は記憶装置１００、剰余演算装置２００、演算装置３００、Ｒａｂｉｎ法判定装置４００、加算装置５００、比較装置６００、乱数生成装置７００から成る。演算装置３００は図６に示すように加算装置３１０で入力値Ａi に２を加算してＡi とし、比較装置３２０でＡi ＜Ｐi かを判定し、減算装置３３０でＡi ＝Ａi −Ｐi を計算してその結果Ａi を出力する。
【００１８】
この素数生成装置は図７に示す手順により素数生成を行う。
＜準備＞（Ｓ１）（図８）
▲１▼あらかじめ、小さい方からｎ個の素数を求めておいて、記憶装置１００内に格納しておく（これを、Ｐ1 ，Ｐ2 ，…，Ｐn とする）。
▲２▼α＝２とする。
＜一次ふるい（１）＞（Ｓ２）（図９）
▲１▼素数の候補として、任意の奇数Ｘを１つ選択し、
▲２▼剰余演算装置２００でＡ1 ＝Ｘmod Ｐ1 ，Ａ2 ＝Ｘmod Ｐ2 ，…，Ａn ＝Ｘmod Ｐn を計算し、
▲３▼Ａ1 ，Ａ2 ，…，Ａn を記憶装置１００に格納し、
▲４▼Ａ1 ，Ａ2 ，…，Ａn の全てが０でないかを比較装置６００で判定し（Ｓ３）、
Ａ1 からＡn 全てが「０でない」場合、＜二次ふるい＞に進み（Ｓ４）、
Ａ1 からＡn のうち１つでも０の場合、＜一次ふるい（２）＞に進む（Ｓ５）。
＜一次ふるい（２）＞（Ｓ４）（図１０）
▲１▼加算装置５００で新たな候補Ｘ（＝Ｘ＋２）を計算し、
▲２▼加算装置３００でＡ1 ＋２を計算し、比較装置３２０でＡ1 ＋２とＰ1 を比較し
▲３▼Ａ1 ＋２＜Ｐ1 であれば、Ａ1 ＝Ａ1 ＋２とし、
▲４▼Ａ1 ＋２≧Ｐ1 であれば、減算装置３３０でＡ1 ＋２からＰ1 を減じ、減じた結果をＡ1 とし、
Ａ2 ＋２とＰ2 を比較し、
Ａ2 ＋２＜Ｐ2 であれば、Ａ2 ＝Ａ2 ＋２とし、
Ａ2 ＋２≧Ｐ2 であれば、Ａ2 ＋２からＰ2 を減じ、減じた結果をＡ2 とし、
以下同様にＡn までの値を計算し、
Ａ1 ，Ａ2 ，…，Ａn を記憶装置１００に格納し、
▲５▼Ａ1 ，Ａ2 ，…，Ａn が全て０かを調べ（Ｓ６）、
Ａ1 からＡn 全てが「０でない」場合、＜二次ふるい＞に進み（Ｓ５）、
Ａ1 からＡn のうち１つでも０の場合、＜一次ふるい（２）＞の始めにもどる（Ｓ４）。
＜二次ふるい＞（Ｓ５）（図１１）
▲１▼判定装置４００とＲａｂｉｎ法によりＸが素数であるか否かを判定し（Ｓ７）、
▲２▼素数であると判定された場合、Ｘを出力して処理を終了し（Ｓ８）、
▲３▼素数でないと判定された場合、＜一次ふるい（２）＞の始めにもどる（Ｓ４）。
【００１９】
Ｒａｂｉｎ法による判定は時間がかかるため、できるだけ一次ふるいで候補を絞ることが素数生成時間を短縮するためには有効である。
この発明装置を用いることにより、効率的に素数候補を絞ることが可能である。
この発明装置はその各機能をコンピュータにプログラムを解読実行させて作用させることもできる。
【００２０】
【発明の効果】
整数Ｘ1 およびＸ2 （＝Ｘ1 ＋α）がｉ個の整数Ｐ1 ，Ｐ2 ，…，Ｐi の約数であるかを判定する装置において、従来法においては、Ｘ1 mod Ｐ1 ，Ｘ1 mod Ｐ2 ，…，Ｘ1 mod Ｐi を計算し、さらに、Ｘ2 mod Ｐ1 ，Ｘ2 mod Ｐ2 ，…，Ｘ2 mod Ｐi を計算し、それぞれが０か否かで約数であるかを判定していた。
【００２１】
これに対し、この発明装置においては、Ｘ1 がＰを約数にもつかを判定するために、Ｘ1 mod Ｐを計算し、その値を、Ａとして保存し、Ａ＝０であれば、ＰはＸ1 の約数であると判定し、Ａ≠０であれば、ＰはＸ1 の約数でないと判定し、Ｘ2 がＰを約数にもつかを判定するために、Ａ＋αとＰを比較し、Ａ＋α＜Ｐであれば、Ｂ＝Ａ＋αとし、Ａ＋α≧Ｐであれば、Ａ＋α＜ＰとなるまでＡ＋αからＰを減じ、減じた結果をＢとし、Ｂ＝０であれば、ＰはＸ2 の約数であると判定し、Ｂ≠０であれば、ＰはＸ2 の約数でないと判定する。
【００２２】
これにより、剰余演算は、１回だけ実行すれば良い。一般に、加減算に比べて、剰余演算は非常に時間がかかるため、２回目は１回目に比べて非常に小さい時間で判定可能である。また、この発明は、判定したい整数の数が増えると効果が顕著となる。例えば、Ｘ，Ｘ＋α，Ｘ＋２×α，Ｘ＋３×α，…，Ｘ＋ｊ×αのｊ＋１個の整数が、Ｐを約数にもつかどうかを判定する場合、従来では、ｊ＋１回の剰余演算が必要であるが、この発明では剰余演算は１回でよい。
【図面の簡単な説明】
【図１】請求項１の発明の実施例の機能構成を示すブロック図。
【図２】図１の装置の処理手順を示す流れ図。
【図３】請求項２の発明の実施例の機能構成を示すブロック図。
【図４】図３の装置の処理手順を示す流れ図。
【図５】素数生成装置の全体の機能構成を示すブロック構成図。
【図６】図５中の演算装置３００の具体例を示すブロック構成図。
【図７】素数生成の全体を示すフローチャート。
【図８】図７中のＳ１の処理を示すフローチャート。
【図９】図７中の一次ふるい（１）Ｓ２の処理を示すフローチャート。
【図１０】図７中の一次ふるい（２）Ｓ４の処理を示すフローチャート。
【図１１】図７中の二次ふるいＳ５の処理を示すフローチャート。
【図１】
0003782262.tif 000002
【図２】
0003782262.tif 000003
【図３】
0003782262.tif 000004
【図４】
0003782262.tif 000005
【図５】
0003782262.tif 000006
【図６】
0003782262.tif 000007
【図７】
0003782262.tif 000008
【図８】
0003782262.tif 000009
【図９】
0003782262.tif 000010
【図１０】
0003782262.tif 000011
【図１１】
0003782262.tif 000012