Mp = 2p – 1

(p は素数)の形の数をメルセンヌ (Mersenne) 数という。

p が2、3、5、7、13、17、19、31、61、89、107、127、521、607、1279、2203、2281、3217、4253、4423、9689、9941、11213、19937、21701、23209、44497、86243、110503、132049、216091、756839、859433 のとき

Mp

は素数であることがわかっている。ちなみに M859433は10進数で約26万桁の数であり、1994年1月にLucasテストによって発見された巨大素数である。

Lucasテストとは、ルーカス (Lucas) が1876年に発見したもので、メルセンヌ数が素数かどうかを簡単に判定できる。

   

L0 = 4、 Li+i =(Li2 – 2) mod (2p – 1)

で、

Lp-1

が 0 なら

Mp

は素数、0 以外なら非素数という。

Lucas テストのおかげで、コンピュータの力による素数の発見競争は、これからも続けられ、記録は塗り替えられていくであろう。

<関数名>
  lucas —- メルセンヌ(Mersenne)数が素数であるかどうかを判定する

<形式>
  int lucas(int p);

<引数>
  p メルセンヌ数における素数

<関数値>
  素数なら1、非素数(つまり、合成数)なら0、内部エラーが起きたときは -1。

用例
  lucas(3217);

<関数本体>
  lucas.c

Comments are closed.

Post Navigation