時間的に効率の良い素数判定と素因数分解のアイデアについて

第1話

はじめに

筆者はアマチュア数学愛好家ですが、ふと素数判定と素因数分解に使えそうなアイデアを思いついたので書いてみます。

【要旨】

16以上の数に対して充分な数の階乗表を用意する事が出来れば効率的に素数判定が出来る。

また判定する数が素数でないならば1とその数以外の約数(素数とは限らない)を一つ求めることが出来る。

なお階乗表を用意できた場合に比べて時間はかかるが、連続する整数の掛け合わせを必要になるたびに計算する事でも同様に結果算出は出来る。

【基本的な考え方】

与えられた整数Nの約数が特定の範囲にあるかを調べて、その範囲を狭めることによりNの素数判定と素因数分解を行う。

対象範囲は前の対象範囲の約半分になるので、例えば素数表を用いて順次調べる方法よりも時間的効率が良いと思われる。

【実例】

15までの階乗表を使用して、実際に試してみる。

※15までの階乗表

1の階乗：1

2の階乗：2

3の階乗：6

4の階乗：24

5の階乗：120

6の階乗：720

7の階乗：5,040

8の階乗：40,320

9の階乗：362,880

10の階乗：3,628,800

11の階乗：39,916,800

12の階乗：479,001,600

13の階乗：6,227,020,800

14の階乗：87,178,291,200

15の階乗：1,307,674,368,000

１．調べる数をNとする。ただし、この数が25未満ならば既知の数として判定終了。

　　※Nの平方根の整数部をnとした時に、nの階乗がNよりも小さいと以下に

　　　記述するアルゴリズムが使えない。

２．Nの平方根を求める。この数が整数ならばNは平方数かつ素数ではない。

　　判定終了。

　　例：121(11の平方数)

　　　　平方根は11

　　　　121は11*11で、素数ではない。終了。

３．Nの平方根の整数部分(小数点以下を切り捨てた値)をｎとする。

　　ｎの階乗をNで割った余りが0で無ければ、ユークリッドの互除法を使い、

　　ｎの階乗とNの最大公約数を求める。

　　・ｎの階乗をNで割った余りが0ならば、範囲を狭めて探索する（４．に移動)

　　・最大公約数が0でなく1で無ければ、Nはこの最大公約数の倍数

　　・最大公約数が1ならばNは素数

　　　※nの階乗と平方数でないNの最大公約数が1ならば、Nが約数を持つとしても

　　　　1を除き1からnまでの間には存在しない。　　　　

　　　　またNの平方根の整数部分なので、nよりも大きい複数の整数を掛けたもの

　　　　はNよりも大きくなる。

　　　　従ってnの階乗とNの最大公約数が1ならば、Nは1と自分自身以外の約数を

　　　　持たない素数。

　　例１：231(=3*7*11)

　　　　平方根は15.198…

　　　　整数部分は15

　　　　15の階乗(1,307,674,368,000)と231の最大公約数を求める。

　　　　1,307,674,368,000　÷　231　余り　0

　　　　nの階乗がNで割り切れるならば、Nはそれぞれ異なるnより小さい複数の

　　　　整数の積で表せる。

　　　　４．に移動

　　例２：143(=13*11)

　　　　平方根は11.958…

　　　　整数部分は11

　　　　11の階乗(39,916,800)と143の最大公約数を求める。

　　　　39,916,800　÷　143　余り　66

　　　　143　÷　66　余り　11

　　　　66　÷　11　余り　0

　　　　最大公約数は11、従って143は11の倍数。終了。

　　例３：139(素数)

　　　　平方根は11.789…

　　　　整数部分は11

　　　　11の階乗(39,916,800)と139の最大公約数を求める。

　　　　39,916,800　÷　139　余り　31

　　　　139 ÷　31　余り　15

　　　　31　÷　15　余り　1

　　　　15　÷　1　余り　0

　　　　最大公約数は１、従って139は素数。終了。

４．始点Sを2、終点Eをnとする数列を考える。

　　(どの数に1を掛けても値は変わらないため1は除外)

　　この数列を検査数列と呼称する。

　　検査数列のすべての数を掛け合わせた数はnの階乗に等しい。

　　そしてnの階乗はNで割り切れる(3．を参照)。

　　またNは素数では無い(3．を参照)。

　　これは、この数列の2つ以上の要素の組み合わせで掛け合わせると

　　Nになる組が存在する事を意味する。

　　５．に移動。

５．検査数列を(S+E)/2を境に大小二つの数列に分ける。

　　(S+E)/2が整数の場合は、(S+E)/2は小さい数列に入れる。

　　小さい数列のすべての数を掛け合わせた数をL、大きい数列の

　　すべての数を掛け合わせたを数Gとする。

　　(階乗表があるならば2つの階乗から除算で算出できる)

　　その結果は以下の3通りのいずれかになる。

　　(②と③はどちらも満たす可能性がある)

　　①GもLもNで割り切れない。

　　②LはNで割り切れる。

　　③GはNで割り切れる。

　　LもGもNで割り切れないならば、どちらかの数とNの1ではない

　　最大公約数を求めることが出来る。

　　(ユークリッドの互除法使用)

　　従って①の場合、Nはここで求めた最大公約数の倍数になる。終了。

　　例１：231(=3*7*11)の続き

　　　　　S=2、E=15、(S+E)/2=8.5

　　　　　小さい数列は2, 3, 4, 5, 6, 7, 8

　　　　　L=40,320

　　　　　40,320　÷　231　余り　126

　　　　　231 ÷　126　余り　105

　　　　　126 ÷　105　余り　21

　　　　　105 ÷　21　余り　0

　　　 最大公約数は21、従って231は21の倍数。終了。

　　②の場合、小さい数列の最小値をS、同じく最大値をEとする検査数列として

　　５．に移動。

　　③の場合、大きい数列の最小値をS、同じく最大値をEとする検査数列として

　　５．に移動。

　　※大小どちらかの数列の数の掛け合わせたものがNで割り切れるという事は、

　　　その数列の2つ以上の要素の組み合わせで掛け合わせるとNになる組が

　　　存在する事を意味する。

　　　(つまり最大公約数からNの1とN以外の約数を求められない)

　　　なので、この場合は範囲を狭めて新しい検査数列として調べなおす。

【実装にあたって】

明確な問題点としては、巨大な数の階乗表を作る事の時間的困難さとそれを(メモリーやストレージに)記憶する事の物理的困難さがある。

しかし一度、階乗表を作れば、その後の判定は容易になると思われる。

また、上記の例では範囲を2つに分けて判定したが、100億分割など分割を大幅に増やしたり、すべての数の階乗表ではなく、例えば2の累乗の数の階乗表のみを用意するなど、ある程度の実装のための改善は可能かもしれない。

【追記】2024年4月1日13時16分

思いついた時は、分散して計算できるし(例えば10001から11001と言うように)階乗は悪くないかと思いましたが、素数のみの掛け合わせを使った方が良いように思えてきました。

他にも思い付いたアイデアがありますので近いうちにWebアプリを作ってみたいと思います。