メルセンヌ数、フェルマー数

出典: 西川利男　シンポジウム　2000
論文:素数とJの整数多倍長計算ーメルセンヌ数、フェルマー数からRSA暗号を巡ってー
PDF
Script
jsympo.ijs

メルセンヌ数

メルセンヌ(Marin Mersenne 1588-1648 France) 神学者で数学、物理、音響理論の研究者

学会もアカデミーも紀要も無い時代に数学者間の手紙ネットワークの中心に位置し、 多くの手紙が貴重な数学遺産となった。

メルセンヌの予想
\( n=2,3,5,7,13,17,19,31,61,127,257 \)に対して\( 2^{n}-1\)は素数で有り、257未満の その他のnに対してはそうでは無い
数式 　
\[ M_{n}=2^{n}-1 \]
SCRIPT 
mers =: 3 : '(2x^y) - 1x'
mperf =: 3 : '-: (y + 1x)*y'
J Grammer
1x 多倍長計算は数字の後ろにxをつける。（何処までもやる）
-: \( \dfrac{1}{2} \)
q:素因数分解の動詞
Example 
    mers 2 3 5 7 13 17 19  
3 7 31 127 8191 131071 524287


   mers 31
2147483647
   q: mers 31
2147483647
1876 エドワール・ルカが \( 2^{127}-1 \)が素数であると証明した 
   mers 127
170141183460469231731687303715884105727
  q: mers 127
170141183460469231731687303715884105727
1903 アメリカ数学会でフランク・ネルソン・コールは 次の数を黒板に書いて黙って立ち去った（出典:WikiPedia） \[193707721 \times 761838257287 \] 
   mers 67
147573952589676412927
  q: mers 67
193707721 761838257287
note: 　
257はPCのメモリーに余裕が必要 　
最新の発見は2017 　
オンライン整数列大辞典

メルセンヌ数と完全数

数式
\[ (2^{n-1})(2^{n}-1)=(M_{n}+1)M_{n}/2 \]
既にユークリッド・原論にある
Script 
 NB. test Perfect number
s =: ~.@q:                NB. 素数だけの取出し
t =: >:@(+/@(] =/ ~.)@q:) NB. 素因数分解のべきの数＋１
tau =: */@t               NB. 約数の個数
sigma =: */@:((<:@(s^t)) % <:@s)
tperf =: 2&* = sigma
Example 
   mers 3
7
   mperf 7
28
   tperf 28
1
\[ (2^{3-1})(2^{3}-1) = \dfrac{7(7+1)}{2} \]

フェルマー数

フェルマーの予想（1640）
2を基数にすると、全てが素数になる
数式
\[ F_{n}=2^{{2}^{n}}+1 \]
Script 
NB. make Fermat number: Fn <--> fm n
fm =: 3 : '1x + 2x^2x^y'

NB. make p value: e.g. p =. n pk k
pk =: 4 : '1x + y*(2x^>: x)'

NB. multi-precision integer divide
NB. returns (quotient, residue)
idiv =: 4 : 0
r =. y| x
((x - r)%y) , r
)
Example 
   fm 1 2 3 4 5
5 17 257 65537 4294967297
 q:  fm 1 2 3 4 5
    5       0
   17       0
  257       0
65537       0
  641 6700417
オイラー（1732）\( F_{5} \) は素数ではない 
  ] p=. 5 pk i.15
1 65 129 193 257 321 385 449 513 577 641 705 769 833 897

  ] F5=. fm 5
4294967297

   p,.F5 idiv  "0 p
  1 4294967297   0
 65   66076419  62
129   33294320  17
193   22253716 109
257   16711935   2
321   13379960 137
385   11155759  82
449    9565628 325
513    8372255 482
577    7443617 288
641    6700417   0
705    6092152 137
769    5585133  20
833    5156023 138
897    4788146 335