【２】リュカ数列と素数判定法

２n −１の形の数が素数であるためにはｎが素数であることが必要条件です．一方，２^n＋１の形が素数であるためにはｎ＝２^mの形であることが必要です．しかし，このことは十分条件ではなく，指数ｎがどんな数のとき２^n−１，２^n＋１が素数になるかはいまだに解決されていません．

　添字に２^nをもつリュカ数列｛Ｌ2^n｝，すなわち，３，７，４７，２２０７，４８７０８４７，・・・では，漸化式Ｌ2^(n+1)＝（Ｌ2^n）^2−２が成り立ちますが，この漸化式とフェルマーの小定理（１６４０年）

　　「もしｐが素数であれば，任意の整数ａに関してａ^p−ａはｐの倍数である．」を応用した素数判定法がリュカテストです．

　リュカはフィボナッチ数列，リュカ数列を用いてメルセンヌ数（２^n−１）が素数であるかどうかを判定し，（２^127−１）が素数であることを示しています（１８７６年）．この数は１２番目のメルセンヌ素数で，１９５２年の１３番目（２^521−１）からはコンピュータによる発見ですから，コンピュータを使わずに見つけられた最大のメルセンヌ素数になっていて，わかっている最大の素数として最長不倒記録を保ち続けました．

　１９９４年，アメリカのスーパーコンピュータ，クレイによって発見された２５８７１６桁の巨大な素数（２^859433−１）は当時知られている最大の素数（３３番目のメルセンヌ素数）ですが，リュカテストはメルセンヌ数が素数であるか否か判定する非常に能率的なアルゴリズムとなっていて，リュカテストの効率のよさのおかげで最近の素数の世界記録はすべてメルセンヌ素数が独占しています．

　なお，フェルマー数（２^(2^n)＋１）に対してはリュカテストと同じくらい能率的なペパンの素数判定法があり，コンピュータを使って６番目のフェルマー素数の探索が続けられているのですが，はたして本当に存在するのでしょうか？

　リュカやペパンの素数判定法によってある数が合成数とわかってもそれを素因数分解するのはとても大変な作業になります．現在，巨大な整数の素因数分解に楕円曲線法とか平方ふるい法とか能率のよい素因数分解法が考え出されています．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝