名工大 D38 同窓会

名工大 D38 同窓会のホームページは、卒業後50年目の同窓会を記念して作成しました。

 管理者     
前田・宮口・三山
掛け算のみによる素数確定方法と合成数の素因数分解法、 竹崎

掛け算のみによる素数確定方法と合成数の素因数分解法、 竹崎

竹崎さんのオリジナル原稿は、表はWordでうまく編集されています。WordPressのテキスト文章では、意図した表になっているか、ちょっと心配です。明日、PDFファイルに変換して見れるようにします。(管理人)

 

Abstruct

I have found that prime factorization and prime decision of integer can be done solely by multiplication (hereinafter called “Prime Factorization by multiplication”). I have found that all prime numbers originally existing at some numerical range between 2 and an integer 2R in a multiplication table made of the products of each of the integers

from 2 to R with each of the integers from 2 to an. In this multiplication table (from 2×2 to R×an there appear without any exception all composite numbers originally existing at the range between 4 and 2R, while integers not appearing at the range between 4 and 2R are all prime numbers originally existing at the range between 4 and 2R.

With respect to prime factorization, it goes without saying that any composite number appearing in the multiplication table is a product of known multiplier and multiplicand, which means that both of multiplier and multiplicand are factors of the composite number. These factors of the composite number are automatically factorized into a product of prime numbers by tracing back to its multiplier and multiplicand until each of the multiplier and multiplicand reaches respective prime numbers by use of the multiplication table.

 

はじめのはじめ

名工大D38同総会ホームページに2018年12月21日「古典と素数のひとり旅」と題したエッセイを掲載して戴きましたが、その中で素数についての我流の素数判定法が一応纏まりましたので、ここに掲載させて頂きます。前回にも述べましたが、頭の体操・ボケ防止のつもりで、昨年頃から始めたのが素数でしたので、整数論を勉強した者でもなく、他の数学を再学習した者でもない私が、算術の知識位で到達したのが我流の素数判定法です。ただこの我流の素数判定法が今日までに誰かによって考え出されているか否かを文末に挙げた素数関係の書籍多数を調べましたが、いずれにも見つけることがなかったので、ここに発表させて頂きたいと思います。

はじめに

 

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

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

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

 

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

≪ここでちょっとコヒーブレイク≫

巨大な素数を発見した者には、いろいろな研究所や機関から高額の懸賞金が付与されるとのことです。例えば、下記のとおりです。

Great Internet Mersenne Prime Search (GIMPS) では、彼らの無料ソフトウェアを入手し計算機上で実行してくれる参加者が、1億桁未満のメルセンヌ素数のいずれかを発見する毎に、3000米ドルの懸賞金を渡すと提示している。

電子フロンティア財団 (EFF) では大きな素数の新記録に対する懸賞金を何部門か提示している[3]。1億桁以上の素数を最初に発見した者に与えられる予定の電子フロンティア財団からの懸賞金150,000米ドルに対し、GIMPS では賞金を参加者と分配する方向で調整中である。

100万桁を越える素数が1999年に発見されたときの懸賞金は50,000米ドルであった[4]。1000万桁を超える素数が2008年に発見されたときの懸賞金は100,000米ドルであり、さらに電子フロンティア財団からCooperative Computing Award賞が授与された[3]。この業績は Time 誌が選ぶ「2008年 Top Invention」の29番目として紹介された[5]。1億桁を越える素数の発見と10億桁を超える素数の発見に対する懸賞金はまだ提示されたままである[3]。ちなみに50,000米ドルと100,000米ドルの懸賞金の受賞者は両方ともGIMPSの参加者である。(巨大な素数の一覧 – Wikipedia – ウィキペディア

また、RAS研究所(http://www.rsa.com/)は、ある種の巨大な自然数の因数分解が成功した場合は、最高20万ドルの懸賞金を出すとあります。(発行所オライリージャパン/オーム社2008年12月10日発行「プライムナンバーズ」248頁)

 

我流の素数判定法

 

「レラトステネスの篩」による素数判定法よりももっと簡単な方法はないかと考えて、発想の転換をして、素数確定を掛け算のみで行う方法(以下、「掛け算素数確定法」と仮称する)を思いつきました。「レラトステネスの篩」ではできなかった整数の素因数分解も、この「掛け算素数確定法」では、整数の素数判定と同時に整数の素因数分解も、その副産物として機械的に行うことができます。その上、素数リストなるものは一切不要です。一言でいえば、現行の素数判定法は判定したい数が素数であるか否かを判定する方法であるのに対して、「掛け算素数確定法」は自然数の数列の任意の範囲に存在する全ての自然数を対象として、その範囲内の全ての自然数の内、すべての合成数を一挙に確定し、その範囲内に合成数として出現しなかった数が全て素数である訳で、いわば間接的素数判定法です。自然数の集合は素数の集合と合成数の集合とから構成されているので、所望範囲内の自然数の内、漏れなく全ての合成数が確定できれば、自ずと残りの自然数は、全て素数となることになる。従って、「掛け算素数確定法」は掛け算だけで実行できます。このように任意の自然数N以下の自然数の中に存在する全ての素数を一度に確定することができる。同様に、所望の範囲内にある自然数N即ち、自然数N1≦自然数N≦自然数N2の範囲内にある自然数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=18、2×8=16、2×9=18、3の段では積だけを表示すると、6、9、12、15、18、21、24、27、以下、九九算の結果を表で表示する。

 

乗数

被乗数

2 3 4 5 6 7 8 9
2 4 6 8 10 12 14 16 18
3 6 9 12 15 18 21 24 27
4 8 12 16 20 24 28 32 36
5 10 15 20 25 30 35 40 45
6 12 18 24 30 36 42 48 54
7 14 21 28 35 42 49 56 63
8 16 24 32 40 48 56 64 72
9 18 27 36 45 54 63 72 81

(表中、対角線右上に存在する赤字で表示した全数字は、対角線左下に存在する全数字と全く同一であり、ここでは不要な数字である。自然数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(に最も近い自然数L(L)までの自然数との積を計算すればよいことになる。これを九九算による合成数と素数の求め方で言うと、に最も近い自然数L(L)は、N=9なので、33×1.4142≒4となり、乗数jは2~4となる。つまり、被乗数iは2~9で、乗数jは2~4までの積を求めればよいことになる。

エクセルの計算ソフトでは一度には計算できない巨大な自然数までの全素数と全合成数についても同様に行える。例えば、4~2×までの全ての合成数と全ての素数を求めたい場合は、乗数jは2~=までで、被乗数iは2~までの積を求めればよいことになる。

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

 

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

≪ここでちょっとコヒーブレイク≫

九九算と言えば、1×1から始まって9×9で終わるが、ところ変われば品代わるではないが、英米では12×12まである。インドでは20×20で終わるが、地方によっては99×99 まで習うところもあるようです。ところで、日本では平安時代から九九算があったが、今とは逆の順に「九九八十一、八九(ハツク)七十二…」の順に唱えたようです。江戸時代から今の順になったようです。

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

自然数iと自然数jとの積をPijと表示することにする。ここで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とすると、Pijで表示することが表示できる。

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

 

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

 

同様に、任意の自然数範囲(N1~N2まで)の全ての合成数Pijを含む表を作成すれば、この表に含まれていない自然数は素数P(N1≦P≦N2)と確定する。

 

2. 奇数のみの自然数を対象とした掛け算のみによる素数確定方法と合成数の素因数分解法

 

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

 

積Pij=i×j と表示する。   iもjも隣接する奇数の自然数(1を除く)とする。

 

エクセルで、被乗数i(3,5、7、9、・・・・奇数の)を列に配置し、乗数j(3,5、7、9、・・・・奇数の)を行に配置して、九九算のように掛け算した各積Pij=i×jを記載する。エクセルを使用すれば容易に積Pij=i×jの表が作成される。

任意の奇数の自然数3までの全ての合成数と全ての素数を確定するには、被乗数3~までの自然数と乗数3~Lに最も近い奇数の自然数L(L))までの奇数自然数との積を計算すればよいことになる。

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

 

つまり、この表中の9~3までの全ての奇数合成数Pijに含まれていない9~3までの自然数は全てが素数となる。

同様に、任意の奇数自然数Na~奇数自然数Nbまでの全ての合成数Pijを含む表を作成すれば、この表に含まれていない自然数(奇数)は素数P(Na≦P≦Nb)と確定する。

≪ここでちょっとコヒーブレイク≫

素数が発見されて以来約2600年間も実用面では素数は何の役にも立たず、数学の遊びに過ぎないと考えられていたようであるが、数学研究面では、遊びどころではなく、現代数学に至るまで数学発展の原動力を与え続けている。整数を研究する歴史の中で、ゼータ関数と呼ばれる関数が発見され素数分布の研究を始めとした解析的整数論における重要な研究対象であり、数論や力学系の研究を初め数学や物理学の様々な分野で用いられているゼータ関数と呼ばれる一連の関数のうち、最も歴史的に古いものである。リーマンのゼータ関数とも呼ばれる。

ところで、現代生活の実用面では、1977年に発明されたRSA暗号に巨大な素数が利用され、今日使用されている、例えば、通信販売の取引に不可欠な暗号となっている。一般にはインターネットで情報を暗号化してその情報を送り、受け取った側がその暗号化された情報をもとの情報に戻すという暗号化情報のやり取りにRSA暗号が使用されている。(雑誌「Newton」(㈱ニュートンオプレス社発行2017年8月号37頁))や(RSA暗号 – Wikipedia

ただし、「RSA暗号は、安全性が素因数分解問題と同値であると期待されている暗号方式であるが、本当に両者が同値であるかどうかについては分かっていない。」ともある。

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

一休みしたところで本論に戻ります。さて、表1で水色で表示した数は、2~50までの合成数の全てである。なお、対角線右上部に赤色で表示した数は、掛け算ab=baの関係から対角線左下部の数と重複しているので、不要である。

【表1】25×25までの九九算拡張法による素数確定例と合成数の素因数分解例

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

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

 

【1】2~50までの合成数と素数の算出

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

合成数     4   6   8 9 10   12   14 15 16   18   20
素数 2 3   5   7       11   13       17   19  
合成数 21 22   24 25 26 27 28   30   32 33 34 35 36   38 39
素数     23           29   31           37    
合成数 40   42   44 45 46   48 49 50                
素数   41   43       47                      

 

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

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

≪例1≫合成数391=被乗数(i)23×乗数(j)17

≪例2≫合成数306=被乗数(i)18×乗数(j)17=被乗数(i)3×乗数(j)6×乗数(j)17=2×32×17

≪例3≫合成数529=被乗数(i)23×乗数(j)32

≪例4≫合成数339=被乗数(i)21×乗数(j)19=被乗数(i)3×乗数(j)7×乗数(j)19=3×7×19

≪ここでちょっとコヒーブレイク≫

素数が発見されて以来約2600年経っても未だに素数の出現法則は発見されていない。つまり、任意の素数N=f(n) ここでn=1,2,3,4・・・・の自然数列のような関数は未発見です。数学者オイラーが考え出した素数生成式f(n) = − n + 41があるが、自然数nが41未満(n)までは全ての素数がこの式で生成されるが、41以上では生成されない場合(合成数である)がある。因みにn=41では、f(n) = − n + 41=となり、合成数となる。更にさまざまな数学者がいろいろな素数生成式を考案しているが、いずれも、nがある自然数以上になると素数が生成されなくなる。

このように今日までに未だ素数の完全な関数関係または法則性は発見されていないが、現在でも、その発見のために多くの数学者や一般人が挑戦しているからこそ、新しい数学が突然のように出現しつつ、数学は発展し、自然科学、社会科学など多くの分野に貢献しているのではないでしょうか。

なお、参考のために、「素数に法則はあるのか? – 偉人たちが挑戦した素数の数式化」(https://analytics-notty.tech/is-there-a-law-for-prime-numbers/)をご紹介します。

≪結論≫

  • 素数が登場する順番に法則はない。
  • 歴史上の偉人達が素数の数式化に挑戦してきたが、未だに成功していない。
  • メルセンヌ数は今後の素数の発見に役立つと期待されている。
  • 今後の素数分野の研究に期待!

 

 

4. 奇数のみの自然数を対象とした素数確定方法

【表2】奇数i×奇数jの積Pi*jの部分表(i=3,5,7,9,~199 j=3,5,7,9,~35)

ここで、9~597までに存在する全素数を確定するためには、奇数被乗数i=3,5,7,9,~199までで、奇数乗数jの最大数L=となるので、奇数乗数jの最大数Lは23までで十分となる。

 

 

 

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

 

表2から105~203までの奇数合成数(表中水色で表示した数)を小さい数(105)から最大合成数(203)まで順に並び替える。抜けている数が素数(下表に赤字で表示)。

奇数合成数の場合も、抜けている素数を抜き出すのは、エクセルの「並び替え」機能(昇順)を使用して合成数の数列を作成し、小さい数から大きい数に(昇順に)並んだ数列のn番目の数をとすると、――の場合には、が素数とが存在する。下表で確認すると、例えば、合成数111-105=6であるから、この二つの合成数の間に、107(=105+2)と109(=105+4)の2個の素数が存在する。

 

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

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

 

 

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

(1)    表2から例えば5103=被乗数(i)189*乗数(j)27=被乗数(i)21*乗数(j)9*乗数(j)27

=被乗数(i)3*乗数(j)7*乗数(j)9*被乗数(i)9*乗数(j)3=36*7となることが明らか

(2)    同様に、表2から5363=被乗数(i)173*乗数(j)31=173*31となることが明らか

 

あとがき

上記に述べました「掛け算素数確定法」は合成数を確定することにより間接的に素数を確定することができると同時に合成数の素因数分解も機械的にできることになります。

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

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

 

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

 

①「数学・まだこんなことがわからない」講談社2004年09月発行

②「素数の不思議」講談社1994年08月発行

③「数学・まだこんなことがわからない」講談社1990年11月発行

④「Newton 2017年8月号」東京:ニュートン プレス2017年08月発行

⑤「プライムナンバーズ」オライリー・ジャパンオーム社2008年10月発行

⑥「素数入門」講談社2002年10月発行

⑦「素数物語」東京:岩波書店2019年03月発行

⑧「素因数分解と素数判定」エスアイビー・アクセス星雲社(発売)2004年03月発行

⑨「暗号の整数論」講談社2009年03月発行

⑩「素数入門」講談社2002年10月発行

⑪ その他に、検索語「素数」、「素因数分解」、「素数判定」、「レラトステネスの篩」、

「ゼータ関数」、「RSA暗号」、「素数法則」、「リーマン予想」としてネット調査多数実施

 

以上

« »