•
|
n が強擬似素数判定法および Lucas 判定法で合成数であることが示されると false を返し、そうでないときは true を返します。 isprime が true を返したとき、n は「ほぼ確実に」素数です。 参考文献としては Knuth ``The art of computer programming'' Vol 2、第 2 版の 4.5.4 節 , Algorithm P、また H. Riesel, ``Prime numbers and computer methods for factorization'' を参照して下さい。反例は知られていません。また、そのような反例が何百桁長であるにちがいないと予想されています。
|