Cara menggunakan PHP dan GMP untuk melaksanakan ujian keutamaan Lucas-Lehmer bagi nombor besar
Pengenalan:
Ujian primaliti Lucas-Lehmer ialah algoritma untuk mengesan keperibadian nombor Mersenne dan digunakan secara meluas dalam bidang teori nombor dan kriptografi. Nombor Mersenne ialah integer dalam bentuk 2^n - 1, dengan n ialah integer positif. Artikel ini akan memperkenalkan cara menggunakan perpustakaan PHP dan GMP untuk melaksanakan ujian keutamaan Lucas-Lehmer bagi nombor besar untuk menentukan sama ada nombor Mersenne adalah perdana.
function lucasLehmerTest($n) { $s = gmp_init(4); $m = gmp_sub(gmp_pow(2, $n), 1); for ($i = 0; $i < $n - 2; $i++) { $s = gmp_mod(gmp_sub(gmp_mul($s, $s), 2), $m); } return gmp_cmp($s, 0) == 0; }
Fungsi di atas menerima parameter n, yang mewakili kuasa nombor Mersenne. Fungsi ini menggunakan gelung secara dalaman untuk mengira setiap item bagi jujukan Lucas-Lehmer, dan kemudian menentukan sama ada item terakhir ialah 0. Jika ia kembali benar, ia bermakna nombor Mersenne adalah perdana; jika ia kembali palsu, ia bermakna nombor Mersenne bukan perdana.
$n = 29; // 选取一个合适的幂次,这里以29为例 $isPrime = lucasLehmerTest($n); if ($isPrime) { echo "2^{$n} - 1 是素数"; } else { echo "2^{$n} - 1 不是素数"; }
Dalam contoh di atas, kami memilih kuasa 29 untuk ujian, dan kemudian menilai sama ada nombor Mersenne adalah perdana berdasarkan nilai pulangan.
Kesimpulan:
Artikel ini memperkenalkan cara menggunakan perpustakaan PHP dan GMP untuk melaksanakan ujian keutamaan Lucas-Lehmer bagi nombor besar. Dengan menggunakan fungsi yang disediakan oleh perpustakaan GMP untuk melaksanakan operasi nombor besar, kami boleh menentukan dengan berkesan sama ada nombor Mersenne adalah perdana. Selain itu, artikel ini menyediakan cadangan untuk pengoptimuman prestasi algoritma untuk mempercepatkan pengiraan. Saya harap artikel ini dapat membantu pembaca yang berminat dengan ujian ini.Atas ialah kandungan terperinci Cara menggunakan PHP dan GMP untuk melaksanakan ujian keutamaan Lucas-Lehmer bagi nombor besar. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!