Math Study（日本語） | Takezaki's Math Study

はじめに

ある説明には、「与えられた自然数が素数かどうか判定するには、その与えられた自然数の平方根以下の素数で割り切れるかどうかを調べれば判定できることになります。これが素数判定の基本です。それには、素数リストが必要で・・・数値が大きくなればなるほど素数リストを作るのは大変な作業となります。150桁の数になってくると、コンピュピュータでもそう簡単に素数判定はできません。」とあります。因みに、雑誌「Newton」（㈱ニュートンオプレス社発行2017年8月号37頁）には、600桁の整数を割り算をして余りが出るか否かを確認するには、たとえスーパーコンピュータを使ったとしても10²⁷³年程度かかるとみられているとある。

このように既知の素数を用いて、それより大きい、判定したい自然数を割り算で行う素数判定法は膨大な時間を要すると言われるので、現在の素数算出方法は、古代ギリシャの学者エラトステネス（紀元前276年頃～紀元前194年頃）によって発見された「エラトステネスの篩」と称されている、比較的に小さな整数の連続する数列（例えば1～100）の中から素数だけを抜き出す素数算出方法をコンピュータによって、巨大な整数の連続する数列に適用しているに過ぎません。つまり、2000年以上経った現在でも「エラトステネスの篩」に勝る方法は見付っていません。

ここで、「エラトステネスの篩」による素数判定法について例を挙げて簡単に紹介します。

自然数を（表に）並べ、1は素数でないので初めに1を除外し、次に2を残して次々に2の倍数を消去する。
2の次に残った数で一番小さい3を残して次々に3の倍数を消去する。
3の次に残った数で一番小さい5を残して次々に5の倍数を消去する。4は2の倍数なので既に消去されている。このようにして、既に消去されている数を飛ばして残っている最小の数nを残して次々にその数nの倍数を消去する。この作業を繰り返して、表の最後の自然数Nまで行う。
こうして表に残った数が2～Nまでの全て素数である。

以下は「エラトステネスの篩」による素数判定法であり、Nが100までの数の中に存在する素数を判定した例である。赤色で表示した2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97が素数である。

本論

掛け算のみによる素数判定方法と合成数の素因数分解法の提案と説明

「エラトステネスの篩」による素数判定法よりももっと簡単な方法はないかと考えて、発想の転換をして、素数判定を掛け算のみで行う方法（以下、「掛け算素数判定法」と仮称する）を思いつきました。

証　明

「掛け算素数判定法」によって、素数判定と合成数の素因数分解ができることの証明は以下のとおりです。合成数は、二つの自然数の積であるので、二つの自然数を一定の順序で掛け合わせることで、全ての合成数を作り出すことができることになる。任意の合成数C_ij=I×Jであると表示する。ここで、I=2,3,4,5,6,7,・・・・nであり、J=2,3,4,5,6,7,・・・・mとする。合成数C_2j=2×J (J=2,3,4,5,6,7,・・・・m), 合成数C_3j=3×J (J=2,3,4,5,6,7,・・・・m), 合成数C_4j=4×J (J=2,3,4,5,6,7,・・・・m), ・・・・・・・合成数C_nj=n×J (J=2,3,4,5,6,7,・・・・m)を算出する。同様にして、合成数C_nm=n×mまで算出すれば、4から合成数C_nmまでの全ての合成数のみが出現することになる。しかし、任意の合成数C_ij=I×J=J× I=C_jiであるので、上記で算出した合成数はいずれの合成数も少なくとも、2個以上算出されているので、不要な算出を避ける工夫をすればよいことになる。

なお、「合成数は、二つの自然数の積である」ことは、証明するまでもなく明らかなことであるが、敢えて証明をすると、合成数は全て素因数分解できる自然数であるので、次のように表記できる。任意の合成数 $\begin{eqnarray} C=p_1^a p_2^b p_3^c \cdots p_n^z \end{eqnarray}$ 、ここで p₁, p₂, p₃,・・・p_nはいずれも互いに異なる素数を表し、a,b,c,・・・zは0以外の自然数でありかつ、互いに異なる自然数であっても同じ自然数であってもよい。つまり、a=b=c=zであってもa≠b≠c≠zであってもよい。簡単のために、a=b=c=z=1とすると、合成数 $\begin{eqnarray} C=p_1^a p_2^b p_3^c \cdots p_n^z \end{eqnarray}$ を二つの自然数の積にするのは、n個の素数p₁, p₂, p₃,・・・p_nの組合せであるから、組合せ_nC₂=n×(n-1)÷2個の組合せだけあることになる。例えば、合成数$\begin{eqnarray} C=p_1^a p_2^b p_3^c \cdots p_n^z \end{eqnarray}$=自然数$\begin{eqnarray} p_1^a × \end{eqnarray}$自然数$\begin{eqnarray} (p_2^b p_3^c \cdots p_n^z) \end{eqnarray}$となる。具体例で示すと、合成数6=2×3、10=2×5、8=2×2×2=2×4、16=2×2×2×2=2×8=4×4、20=2×2×5=2×10=4×5、99=3×3×11=3×33=9×11のように、全ての合成数は2個以上の素数の積であるので、全ての合成数は2個の自然数の積で表すことができる。以上のとおり、「合成数は、二つの自然数の積である」ことが証明されたことになる。

「掛け算素数判定法」の説明

「エラトステネスの篩」ではできなかった整数の素因数分解も、この「掛け算素数判定法」では、整数の素数判定と同時に整数の素因数分解も、その副産物として機械的に行うことができます。その上、素数リストなるものは一切不要です。一言でいえば、現行の素数判定法は判定したい数が素数であるか否かを判定する方法であるのに対して、「掛け算素数判定法」は自然数の数列の任意の範囲に存在する全ての自然数を対象として、その範囲内の全ての自然数の内、すべての合成数を一挙に確定し、その範囲内に合成数として出現しなかった数が全て素数である訳で、いわば間接的素数判定法です。自然数の集合は素数の集合と合成数の集合とから構成されているので、所望範囲内の自然数の内、漏れなく全ての合成数が確定できれば、自ずと残りの自然数は、全て素数となることになる。従って、「掛け算素数判定法」は掛け算だけで実行できます。このように任意の自然数N以下の自然数の中に存在する全ての素数を一度に判定することができる。同様に、所望の範囲内にある自然数N即ち、自然数N₁≦自然数N≦自然数N₂の範囲内にある自然数Nが素数なのか合成数なのかを確定できます。この掛け算素数判定法は、九九算を所定の自然数まで相互に掛け合わせて合成数表を作成し、その表に存在しない自然数は全て素数となる。この表により、この表に存在する全ては合成数であり、しかも既に乗数と被乗数とが既知なので、機械的に合成数の素因数分解ができる。

なお、この「掛け算素数判定法」では、素数判定を行うには、奇数の自然数だけを掛け算の対象とすれば、掛け算の回数が半分になり計算負荷が少なくなる。勿論、その表に存在する奇数合成数も上記と同様に素因数分解が機械的にできる。

ここで、一つ見落としてはならないことは、上記のようにして作成した合成数が漏れなく全て網羅されている範囲は、連続する自然数（2,3,4,5,6,7・・・・N）を対象とした場合は2N以下となり、また、奇数の自然数（3,5,7,9,11・・・・N）を対象とした場合は3N以下となるということです。

このことを直感的に理解して戴くために、小学2年生から習う九九算で説明します。九九算で出てくる合成数は、最小の合成数4～最大の合成数81までですが、自然数4～自然数81までの全ての合成数が出ている訳ではない。例えば、合成数80、22など多くの合成数が出てこない。全ての合成数が出ている範囲は9×2=18までです。ここで、九九算を例にして、その理由を説明すると、2の段では2×2=4、2×3=6、2×4=8、2×5=10、2×6=12、2×7=8、2×8=16、2×9=18、3の段では積だけを表示すると、6、9、12、15、18、21、24、27、以下、九九算の結果を表で表示する。

（表中、対角線右上に存在する赤字で表示した全数字は、対角線左下に存在する全数字と全く同一であり、ここでは不要な数字である。自然数iとjの積は、i×j=j×iの関係にあるから。）

上表で明らかなように、九九算では8×8=64個の合成数が出現するが、4から81までの全ての合成数が出現する訳ではない。合成数が自然数列のなかで連続して出現するのは、4～18までの範囲（2×2～2R）である。即ち、上表で青字で表示した4、6、8、9、10、12、14、15、16、18までである。そこで、4～18までの範囲に出現していない自然数は、5、7、11、13、17であり、これら自然数は合成数でないので、全て素数である。

もう一つ見逃してはならないことは、上表で青字で表示した4、6、8、9、10、12、14、15、16、18までの合成数を九九算で出すには、被乗数iは2～9までであるが、乗数jは2～4までで必要かつ十分であると言うことである。

これを一般化して言うと、任意の自然数2Nまでの全ての合成数と全ての素数を判定するには、被乗数iとして2～Nまでの自然数と乗数jとして2～L（ $\begin{eqnarray} \sqrt{2N} \end{eqnarray}$ に最も近い自然数L） ($\begin{eqnarray} L\leq\sqrt{2N} \end{eqnarray}$) までの自然数との積を計算すればよいことになる。これを九九算による合成数と素数の求め方で言うと、 $\begin{eqnarray} \sqrt{2N} \end{eqnarray}$に最も近い自然数自然数L$ \begin{eqnarray} (L\leq\sqrt{2N}) \end{eqnarray}$は、N=9なので、 $\begin{eqnarray} \sqrt{2N}=\sqrt{2×9}=3\sqrt{2} \fallingdotseq 3×1.4142 \fallingdotseq 4 \end{eqnarray}$となり、乗数jは2～4となる。つまり、被乗数iは2～9で、乗数jは2～4までの積を求めればよいことになる。

エクセルの計算ソフトでは一度には計算できない巨大な自然数までの全素数と全合成数についても同様に行える。例えば、4～2 × $\begin{eqnarray} \ 10^{ 100 } \end{eqnarray}$ までの全ての合成数と全ての素数を求めたい場合は、乗数jは2〜$\begin{eqnarray} \sqrt{2 × 10^{ 100 }}=10^{ 50 } \sqrt{2} \end{eqnarray}$ までで、被乗数iは2～$\ 10^{ 100 }$ までの積を求めればよいことになる。

しかも、最も強調したいのは、この掛け算素数判定法が従前の割り算等による素数判定法に比べて決定的に有利な点は、たった一度だけ巨大な自然数まで被乗数iと乗数jとの積を計算してしまい、その結果（電子データまたは印刷データ）を公開すれば、従前の割り算等による素数判定法のように、各自が何度も何度も同じような計算（割り算）をしなくて済むことになる。

以下に、九九算よりはもう少し大きい自然数までの掛け算素数判定法の実例を挙げながら、上記直感的理解を少し纏めてみたいと思います。ただし、エクセルを使用するため巨大な数を扱っていません。

1. 連続する自然数を対象とした場合の「掛け算素数判定方法」

自然数iと自然数jとの積をP_ijと表示することにする。ここでiは連続する自然数（1を除く）2,3,4,5,6,7,・・・・Nとし、jも連続する自然数（1を除く）2,3,4,5,6,7,・・・・Nとする。因みに、九九算は、iを連続する自然数（1を除く）2,3,4,5,6,7,8,9とし、jを連続する自然数（1を除く）2,3,4,5,6,7,8,9とすると、P_ijで表示することが表示できる。

エクセルで、被乗数iを列に2,3,4,5,6,7,・・・・Nと配置し、乗数jを行に2,3,4,5,6,7,・・・・Nと配置して、九九算のように掛け算した各積P_ij=i×jを記載する。エクセルを使用すれば容易に積P_ij=i×jの表が作成される。この表中の全ての積P_ijには4～2Nまでの全ての合成数がふくまれている。自然数は、素数の集合と合成数の集合とから構成されているので、2から任意の自然数2Nまでの全合成数（表中に表示された全ての積P_ij）が算出されれば、表中に出現していない他の全ての自然数は素数であることが確定する。

つまり、この表中の4～2Nまでの全ての合成数P_ijに含まれていない4から2Nまでの自然数は全てが素数となる。

同様に、任意の自然数範囲（$\ N_{ 1 }$ ～ $\ N_{ 2 }$まで）の全ての合成数P_ijを含む表を作成すれば、この表に含まれていない自然数は素数P（$\ N_{ 1 }$ ≦P≦$\ N_{ 2 }$）と確定する。

2. 奇数のみの自然数を対象とした場合の「掛け算素数判定方法」

素数は奇数であるので、奇数のみの自然数を対象とした「掛け算素数判定法」によれば、計算回数を、上記連続する自然数を対象とした素数判定方法の二分の一にすることができる。

積P_ij=i×j と表示する。 iもjも隣接する奇数の自然数（1を除く）とする。

エクセルで、被乗数i（3、5、7、9、・・・・奇数の$\ N_{ 1 }$）を列に配置し、乗数j（3、5、7、9、・・・・奇数の$\ N_{ 2 }$）を行に配置して、九九算のように掛け算した各積P_ij=i×jを記載する。エクセルを使用すれば容易に積P_ij=i×jの表が作成される。任意の奇数の自然数3$\ N_{ 1 }$までの全ての合成数と全ての素数を判定するには、被乗数3～$\ N_{ 1 }$までの自然数と乗数3～L ($\begin{eqnarray} \sqrt{ 3N_{1} } \end{eqnarray}$ に最も近い奇数の自然数L(L≤ $\begin{eqnarray} \sqrt{ 3N_{1} } \end{eqnarray}$)) までの奇数自然数との積を計算すればよいことになる

この表中の全ての積P_ijには9～3 $\ N_{ 1 }$までの全ての奇数の合成数がふくまれている。奇数の自然数は、素数の集合と奇数の合成数の集合とから構成されているので、9から任意の奇数の自然数3 $\ N_{ 1 }$までの全奇数合成数が確定すれば、その全奇数合成数に出てこない奇数は、9から任意の奇数の自然数3$\ N_{ 1 }$以下の全素数であることが確定する。

つまり、この表中の9～3 $\ N_{ 1 }$までの全ての奇数合成数P_ijに含まれていない9～3 $\ N_{ 1 }$までの自然数は全てが素数となる。

同様に、任意の奇数自然数N_a～奇数自然数$\ N_{ b }$までの全ての合成数P_ijを含む表を作成すれば、この表に含まれていない自然数（奇数）は素数P（$\ N_{ a }$≦P≦ $\ N_{ b }$）と確定する。

3. 連続する自然数を対象とした「掛け算素数判定方法」の一例

下記表1で水色で表示した数は、2～50までの合成数の全てである。なお、対角線右上部に赤色で表示した数は、掛け算ab=baの関係から対角線左下部の数と重複しているので、不要である。

【表１】２５×２５までの九九算拡張法による素数判定例と合成数の素因数分解例

既に述べたように、任意の自然数2Nまでの全ての合成数と全ての素数を確定するには、被乗数2～Nまでの自然数と乗数2～L（ $\begin{eqnarray} \sqrt{ 2N } \end{eqnarray}$ ）に最も近い自然数L (L≤ $\begin{eqnarray} \sqrt{ 2N } \end{eqnarray}$) までの自然数との積を計算すればよいから、2～50までに存在する素数と合成数の素因数分解とを求めるためには、N=25を上式に代入すれば、乗数L=7(L≤ $\begin{eqnarray} \sqrt{ 2N } \end{eqnarray}$ = $\begin{eqnarray} \sqrt{ 2×25 } \end{eqnarray}$ =5 $\begin{eqnarray} \sqrt{ 2N } \end{eqnarray}$ $\begin{eqnarray} \fallingdotseq 5×1.4142≒7 \end{eqnarray}$) と被乗数2～25までの全積P_ij（i=2、3、4、5・・・25、　j=2、3、4、5、6、7）で求められることになる。因みに、表1中で乗数8～25までの右側の表は不要だということになる。

従って、表中青字の数字だけが2～50までに存在する素数と合成数の素因数分解とを求めるために必要な全積P_ijである。

【１】 2～50までの合成数と素数の算出

上記表1で青色表示の合成数を小さい数（4）から最大合成数（50）まで順に並び替える。抜けている数が素数。なお、青色表示の全ての合成数の並び替えには、エクセルの「並び替え」機能（昇順）を使用すれば一瞬でできる。下表のように50までの合成数の数列の場合は、どの数が抜けているかは、目視でも簡単に判るが、巨大な数までの合成数列になると大変な作業になる。小さい数から大きい数に（昇順に）並んだ数列のn番目の数を$\ a_{ n }$とすると、$\ a_{ n+1 }$ − $\ a_{ n }$=2の場合に、$\ a_{ n }$+1が素数となる。下表でも明らかなように、例えば、合成数24-22=2であり、24と22とに挟まれた23（22+1=23）が素数である。同様に44-42=2であり、44と42とに挟まれた43（42+1=43）が素数である。以下全て同様である。

【 2 】表1の合成数を素因数分解する方法

表１の合成数は被乗数i×乗数jの数の積であるから同表を順次たどれば素数同士の積、つまり素因数分解が機械的にできる。

≪例1≫合成数391=被乗数(i)23×乗数(j)17
≪例2≫合成数306=被乗数(i)18×乗数(j)17=被乗数(i)3×乗数(j)6×乗数(j)17=2×$\ 3^{ 2 }$×17
≪例3≫合成数529=被乗数(i)23×乗数(j)23
≪例4≫合成数339=被乗数(i)21×乗数(j)19=被乗数(i)3×乗数(j)7×乗数(j)19=3×7×19

4. 奇数のみの自然数を対象とした「掛け算素数判定方法」の一例

【表２】奇数i×奇数jの積P_i×_jの部分表（i=3,5,7,9,～199 j=3,5,7,9,～35）

ここで、9～597までに存在する全素数を判定するためには、奇数被乗数i=3,5,7,9,～199までで、奇数乗数jの最大数L ≤ $\begin{eqnarray} \sqrt{ 3N } \end{eqnarray}$ $\begin{eqnarray} = \end{eqnarray}$ $\begin{eqnarray} \sqrt{ 3×199 } \end{eqnarray}$ $\begin{eqnarray} ≤24.3 \end{eqnarray}$ となるので、奇数乗数jの最大数Lは23までで十分となる。

【表２】奇数i×奇数jの積Pijの表

【例１】 105～203までの奇数合成数と素数の算出

上記表2から105～203までの奇数合成数（表中水色で表示した数）を小さい数（105）から最大合成数（203）まで順に並び替える。抜けている数が素数（下表に赤字で表示）。奇数合成数の場合も、抜けている素数を抜き出すのは、エクセルの「並び替え」機能（昇順）を使用して合成数の数列を作成し、小さい数から大きい数に（昇順に）並んだ数列のn番目の数を$\ a_{ n }$とすると、$\ a_{ n+1 }$− $\ a_{ n }$=4の場合は$\ a_{ n }$+2が素数1個あり、または$\ a_{ n+1 }$− $\ a_{ n }$=6の場合には、$\ a_{ n+1 }$と$\ a_{ n }$ との間に2個の素数$\ a_{ n }$+2および$\ a_{ n }$+4が素数とが存在する。下表で確認すると、例えば、合成数111− 105=6であるから、この二つの合成数の間に、107（=105+2）と109（=105+4）の2個の素数が存在する。

【例２】 501～561までの奇数合成数と素数の算出

表2から501～561までの奇数合成数（表中黄緑色で表示した数）を小さい数（501）から最大合成数（561）まで順に並び替える。抜けている数が素数（下表に赤字で表示）。

【奇数合成数の素因数分解の例】

表２から例えば5103=被乗数(i)189×乗数(j)27=被乗数(i)21×乗数(j)9×乗数(j)27=被乗数(i)3×乗数(j)7×乗数(j)9×被乗数(i)9×乗数(j)3=$\ 3^{ 6 }$×７となることが明らか。
同様に、表２から5363=被乗数(i)173×乗数(j)31=173×31となることが明らか。

あとがき

上記に述べました「掛け算素数判定法」は合成数を確定することにより間接的に素数を確定することができると同時に合成数の素因数分解も機械的にできることになります。これに対して、コンピュータの発展により現行の素数判定方法としては、原始的なギリシャ時代に考案された「エラトステネスの篩」による素数判定法によっています。しかしこの方法では合成数の素因数分解ができません。素因数分解は依然として目的の数Nを $\begin{eqnarray} \sqrt{ N } \end{eqnarray}$ 以下の素数で次々と直接割り算をして余りがゼロであれば、合成数であり、素因数分解ができることになり、余りがあれば、その数Nは素数となる基本的素数判定法（試し割り法(trial division)）と同じ手法です。判定せんとする自然数一個毎に、素数リストを使用して小さい素数から順次大きい素数で次々と割り算を繰り返し続けることが不可欠です。素数リストと言っても、素数リストに記載されている最後の既発見素数がなくなれば、それより大きい未知の素数は自分で見つけ出して行かなければならないことになります。これは更に大変な作業となる。

これに対して「掛け算素数判定法」が上記現行の二つの素数判定方法に比べて、より簡単な方法であると素人ながら考えています。そう言うことになれば、自然数同士の掛け算をした積P_ij=i×jの表を電子データとしておけば、随時使用することができるので、いろいろに活用できるのではないかと考えられます。また、そのデータを公表しておけば、利用者が同じことを繰り返す必要がなく有意と考えます。100桁、1000桁の数を対象とするには、当然大型コンピュータを使用することになると思います。

「掛け算素数判定法」が新しい判定方法か否かの調査のために参考にした書籍等

「数学・まだこんなことがわからない」講談社2004年09月発行
「素数の不思議」講談社1994年08月発行
「数学・まだこんなことがわからない」講談社1990年11月発行
「Newton　２０１７年８月号」東京：ニュートン　プレス2017年08月発行
「プライムナンバーズ」オライリー・ジャパンオーム社2008年10月発行
「素数入門」講談社2002年10月発行
「素数物語」東京：岩波書店2019年03月発行
「素因数分解と素数判定」エスアイビー・アクセス星雲社(発売)2004年03月発行
「暗号の整数論」講談社2009年03月発行
「素数入門」講談社2002年10月発行
その他に、検索語「素数」、「素因数分解」、「素数判定」、「エラトステネスの篩」、「ゼータ関数」、「RSA暗号」、「素数法則」、「リーマン予想」としてネット調査多数実施

以上

掛け算のみによる素数判定方法と合成数の素因数分解法