(57)【要約】      （修正有）【課題】因数分解及び素数判定にかかる時間を自在に短縮する方法を提供する。【解決手段】〔ステップ１〕３以上のある奇数Ａが、最大素因数Ｂと最小素因数Ｃの２つの数の積からなる合成数であることを判定する。Ｂ＝Ａ／（２ｎ−１）（２≦ｎ≦（√Ａ＋１）／２までの自然数）の計算をｎ＝２から順番に行った際に余りが０になった時のＢが最大素因数であり、その時点のＡ／Ｂの値が最小素因数Ｃである。〔ステップ２〕３以上のある奇数Ａが、素数であることを判定する。Ｂ＝Ａ／（２ｎ−１）（２≦ｎ≦（√Ａ＋１）／２までの自然数）の計算をｎ＝２から順番に行った際に全ての余りが０にならなければ、Ａは合成数でないことが判定されて、その結果素数であることが判明する。【選択図】図１
2019113811.tif 000002
【特許請求の範囲】
【請求項１】
大きな数の因数分解及び素数判定のアルゴリズムを記述する。
〔ステップ１〕３以上のある奇数Ａが最大素因数Ｂと最小素因数Ｃの２つの数の積からなる合成数であることを判定するには、
Ｂ＝Ａ／（２ｎ−１）  （２≦ｎ≦（√Ａ  ＋１）／２までの自然数）
の計算をｎ＝２から順番に行った際に余りが０になった時のＢが最大素因数でありその時点のＡ／Ｂの値が最小素因数Ｃである。何故ならば二つの素数からなる合成数である奇数Ａは以下の数式で表現できる。
Ａ＝（２ｎ１−１）×（２ｎ２−１）
従って（（２ｎ１−１）×（２ｎ２−１））／（２ｎ−１）の計算をｎ＝２から順番に行ってｎがｎ２の値になった時点で割り切れて（２ｎ１−１）の値、つまりこの場合の最大素因数Ｂが算出されることになる。またある奇数Ａが数Ｂと最小素因数Ｃの３つ以上の素数の積からなる合成数である場合は数Ｂは最大素因数ではなく最大因数となる。
〔ステップ２〕３以上のある奇数Ａが素数であることを判定するには、
Ｂ＝Ａ／（２ｎ−１）  （２≦ｎ≦（√Ａ  ＋１）／２までの自然数）
の計算をｎ＝２から順番に行った際に全ての余りが０にならなければＡは合成数でないことが判定されて、その結果素数であることが判明する。
【発明の詳細な説明】
【技術分野】
【０００１】本発明は従来非常に難しいとされていた大きな数の因数分解や素数判定を簡単に行うことのできるアルゴリズム及びプログラムに関するものである。
【背景技術】
【０００２】従来の大きな数の因数分解や素数判定の多くは既知の素数データを基にして対象数を篩にかけて判定するという手法であった。また大きな数の因数分解のアルゴリズムについては未だに未解決問題となったままである。
【特許文献１】特開２００９−１２９３３５
【発明の開示】
【発明が解決しようとする課題】
【０００３】  従来の方法には次のような欠点があった。
既知の素数データを基にして対象数を篩にかける従来の因数分解や素数判定法では繰り返し計算によって新たに見つかった素数をその都度新しいデータとして蓄積しながら次の因数分解や素数判定に役立てなければいけないという煩雑さがあったために対象数が大きくなればなるほど処理スピードが遅くなってしまうといった欠点があった。また大きな数の因数分解の手法についてのアルゴリズムは未だに確立されていない。
本発明はこれらの欠点を除くためになされたものである。
【課題を解決するための手段】
【０００４】ある大きな数が偶数という自然数であった場合、その大きな数は必ず２という約数を持つ合成数なので素数ではないことが明らかである。つまり素数の中で唯一偶数である素数の２を除いたその他の全ての素数は自然数の中の奇数に属する。これを集合で表すと、
〔素数の２を除く全ての素数〕∈〔奇数〕
となり３以上の奇数を数式で表すと２ｎ−１（ｎ≧２の自然数）となる。従って、
〔２以外の素数〕∈（２ｎ−１）、（ｎ≧２の自然数）
となる。次に素数同士の積は
（２ｎ１−１）×（２ｎ２−１）
でありこれを展開すると
４ｎ１ｎ２−２ｎ１−２ｎ２＋１
となる。この式の中の４ｎ１ｎ２、２ｎ１、２ｎ２共に係数が偶数なので偶数となる。従ってこの式を偶数と奇数で表すと、
〔偶数〕−〔偶数〕−〔偶数〕＋〔奇数の１〕
となり偶数に１をプラスするので必ず奇数となる。従って次の式が成り立つ。
（２ｎ１−１）×（２ｎ２−１）∈〔奇数〕
この奇数部分を（２ｎ−１）に置き換えると、
（２ｎ１−１）×（２ｎ２−１）∈（２ｎ−１）（ｎ≧２の自然数）
これを等式で表すと、
（２ｎ１−１）×（２ｎ２−１）＝（２ｎ３−１）
となる。そして素数同士の積が３つ以上であっても同様の展開を行うことによって結果が奇数となることが分かる。つまり素数及び素数同士の積は以下の式で表すことができる。
〔素数及び素数同士の積〕∈（２ｎ−１）（ｎ≧２の自然数）
本アルゴリズム及びプログラムはこの集合関係を利用して作成したものであり、既知の素数データを用いることなく奇数列という一種類の数列によって大きな数の因数分解及び素数判定を簡単に行うことができるようになっているため処理範囲を区切って複数のコンピュータで分散処理することが可能であり、その結果因数分解及び素数判定にかかる時間を自在に短縮できるようになっている。
以下に大きな数の因数分解及び素数判定のアルゴリズムを記述する。
〔ステップ１〕３以上のある奇数Ａが最大素因数Ｂと最小素因数Ｃの２つの数の積からなる合成数であることを判定するには、
Ｂ＝Ａ／（２ｎ−１）  （２≦ｎ≦（√Ａ  ＋１）／２までの自然数）
の計算をｎ＝２から順番に行った際に余りが０になった時のＢが最大素因数でありその時点のＡ／Ｂの値が最小素因数Ｃである。何故ならば二つの素数からなる合成数である奇数Ａは以下の数式で表現できる。
Ａ＝（２ｎ１−１）×（２ｎ２−１）
従って（（２ｎ１−１）×（２ｎ２−１））／（２ｎ−１）の計算をｎ＝２から順番に行ってｎがｎ２の値になった時点で割り切れて（２ｎ１−１）の値、つまりこの場合の最大素因数Ｂが算出されることになる。またある奇数Ａが数Ｂと最小素因数Ｃの３つ以上の素数の積からなる合成数である場合は数Ｂは最大素因数ではなく最大因数となる。
〔ステップ２〕３以上のある奇数Ａが素数であることを判定するには、
Ｂ＝Ａ／（２ｎ−１）  （２≦ｎ≦（√Ａ  ＋１）／２までの自然数）
の計算をｎ＝２から順番に行った際に全ての余りが０にならなければＡは合成数でないことが判定されて、その結果素数であることが判明する。
【発明の効果】
【０００５】  本発明には次のような効果がある。
既知の素数データを用いることなく奇数列という一種類の数列によって大きな数の因数分解及び素数判定を簡単に行うことができるようになっているため処理範囲を区切って複数のコンピュータで分散処理することが可能であり、その結果因数分解及び素数判定にかかる時間を自在に短縮できるようになっている。
【発明を実施するための最良の形態】
【０００６】本発明は非常にシンプルなアルゴリズム及びプログラム構成になっているのでビジネス用のパソコンでも十分稼働させることができるが非常に大きな数の因数分解を行う場合は科学技術計算用スーパーコンピュータクラスの大規模コンピュータを使用するのが最良の形態である。
【実施例】
【０００７】  以下本発明の実施例について説明する。添付図１のＢＡＳＩＣプログラムを用いてＷｉｎｄｏｗｓパソコン上の（仮称）十進ＢＡＳＩＣで計算処理を行いアルゴリズムが正しいことを検証した。
【産業上の利用可能性】
【０００８】安全な通信を確保するためのＲＳＡ暗号の公開暗号鍵には２個の大きな素数の積の値が使われているため大きな数の因数分解を簡単に行えるようになるとこのＲＳＡ暗号の公開暗号鍵の信頼性が低下して安全な通信が破られるといった危険性が生じてくるので、今後量子暗号などの代替暗号の開発を急ぐ必要がある。
【図面の簡単な説明】
【０００９】
【図１】本発明のアルゴリズムを基にして記述したＢＡＳＩＣプログラム
【符号の説明】
【００１０】１  数Ａを（２ｎ−１）で割った余り
２  繰り返し計算の始め
３  ｎを２から（√Ａ  ＋１）／２まで繰り返して計算を行う
４  乗算
【図１】
2019113811.tif 000003