■リュカの素数判定法(その1)

初項1,第2項3のフィボナッチ数列

1,3,4,7,11,18,・・・

はフランスの数学者リュカにちなんでリュカ数列と呼ばれています(1877年).リュカ数列の一般項Ln は,

Ln ={(1+√5)/2}n +{(1−√5)/2}n

  ={φn +(−1/φ)n }

(L0 =2:φ=(1+√5)/2)

で表され,Ln =Fn-1 +Fn+1 の関係があります.リュカ数列はフィボナッチ数列と同じ漸化式をもち,連続する2つの項の比は黄金比に近づきます.

添字に2^n をもつリュカ数列{L2^n},すなわち,3,7,47,2207,4870847,・・・では,漸化式L2^(n+1)=(L2^n)2 −2が成り立ちますが,この漸化式とフェルマーの小定理(もしpが素数であれば,任意の整数aに関してap −aはpの倍数である.1640年)を応用した素数判定法がリュカテストです.

===================================

【1】メルセンヌ数とリュカテスト

メルセンヌ数とは,pを素数とするとき

  Mp=2^p−1

Mp自身が素数のとき,メルセンヌ素数と呼ばれます.

 2^11−1=2047=23・89

のように,すべての素数pがメルセンヌ素数を与えるわけではないので,素数性を判定する方法が必要になります.

平方数から2を差し引くという生成則に従う数列

  Sn=(Sn-1)^2−2,S2=4

S2=4,S3=14,S4=194,S5=37634,・・・

は,メルセンス数の素数性判定のために用いられる数列です.

リュカテストでは,素因数を見つけることなく,直接メルセンヌ素数であるかどうかを判定します.pが奇数の素数のとき,Mpが素数であるための必要十分条件:SpがMpで割り切れる,かつ,そのときだけMpは素数である.

リュカはフィボナッチ数列,リュカ数列を用いてメルセンヌ数(2n −1)が素数であるかどうかを判定し,(2127 −1)が素数であることを示しています(1876年).この数は12番目のメルセンヌ素数で,1952年の13番目(2521 −1)からはコンピュータによる発見ですから,コンピュータを使わずに手計算で見つけられた最大のメルセンヌ素数になっています.

リュカテストはメルセンヌ数が素数であるか否か判定する非常に能率的なアルゴリズムとなっていて,リュカテストの効率のよさのおかげで最近の素数の世界記録はすべてメルセンヌ素数が独占しています.

===================================