Cara menggunakan PHP dan GMP untuk melaksanakan ujian keutamaan Lucas-Lehmer bagi integer besar

Cara menggunakan PHP dan GMP untuk melaksanakan ujian keutamaan Lucas-Lehmer bagi integer besar

Pengenalan:
Dalam teori nombor, ujian keutamaan Lucas-Lehmer ialah kaedah yang digunakan untuk menguji sama ada nombor Mernessen (nombor Mernessen) ialah perdana. Ia digunakan secara meluas Digunakan untuk penghakiman integer besar. Dalam artikel ini, kami akan menggunakan bahasa PHP dan sambungan GMP (Perpustakaan Aritmetik Berbilang Ketepatan GNU, Perpustakaan Matematik Berbilang Ketepatan GNU) untuk melaksanakan ujian keutamaan Lucas-Lehmer dan menyediakan contoh kod yang sepadan.

Apakah Ujian Seksualiti Lucas-Lehmer?
Ujian primaliti Lucas-Lehmer ialah algoritma yang cekap digunakan untuk menentukan sama ada nombor Mounissen dalam bentuk M = 2^n − 1 ialah nombor perdana. Antaranya, n ialah integer positif lebih besar daripada 1. Kaedah ujian ini adalah berdasarkan sifat-sifat jujukan Lucas-Lehmer Ia menentukan keperibadian nombor Monessen dengan mengira secara berulang unsur jujukan seterusnya, dan akhirnya menilai sama ada unsur terakhir jujukan adalah sifar.

Langkah untuk melakukan ujian primaliti Lucas-Lehmer menggunakan PHP dan GMP:
Langkah 1: Pasang sambungan GMP
Apabila melakukan operasi integer yang besar, fungsi terbina dalam PHP tidak dapat mengendalikan nilai yang lebih besar. Jadi, kita perlu menggunakan sambungan GMP untuk menyelesaikan masalah ini. Apabila memasang PHP, anda boleh memilih untuk memasang versi dengan sambungan GMP didayakan atau mendayakan sambungan GMP dalam persekitaran PHP sedia ada.

Langkah 2: Tulis fungsi ujian primaliti Lucas-Lehmer
Berikut ialah contoh fungsi yang digunakan untuk melaksanakan ujian primaliti Lucas-Lehmer:

function lucasLehmerTest($n)
{
    $s = '4';
    $m = gmp_pow('2', $n) - '1';
    
    for ($i = 1; $i < $n - 1; $i++) {
        $s = gmp_mod(gmp_pow($s, 2) - 2, $m);
    }
    
    if ($s == '0') {
        return true;
    }
    
    return false;
}

Analisis:

• $n: bahagian eksponen nombor Mernessen .
• $s: nilai awal jujukan Lucas-Lehmer.
• $m: Nombor Monessen.

Dalam fungsi, kita menggunakan fungsi gmp_pow untuk mengira 2 kepada kuasa $n$, dan kemudian tolak 1 untuk mendapatkan $m$. Kemudian, kami melakukan lelaran gelung $n-1$ untuk mengira setiap elemen jujukan Lucas-Lehmer. Akhir sekali, tentukan sama ada elemen terakhir jujukan adalah sifar, dengan itu menentukan primaliti nombor Monessen.

Langkah 3: Panggil fungsi ujian primaliti Lucas-Lehmer untuk ujian
Berikut ialah contoh memanggil fungsi ujian primaliti Lucas-Lehmer:

$exponents = [2, 3, 5, 7, 13, 17];
foreach ($exponents as $exponent) {
    $result = lucasLehmerTest($exponent);
    
    if ($result) {
        echo "2^$exponent - 1 is a prime number.
";
    } else {
        echo "2^$exponent - 1 is not a prime number.
";
    }
}

Analisis:
Kami mentakrifkan tatasusunan $eksponen, yang mengandungi beberapa nilai eksponen. Kemudian gunakan gelung foreach untuk memanggil fungsi ujian keutamaan Lucas-Lehmer dalam urutan dan mengeluarkan maklumat penghakiman yang sepadan berdasarkan keputusan ujian.

Ringkasan:
Dengan menggunakan sambungan PHP dan GMP, kami boleh melaksanakan ujian primaliti Lucas-Lehmer dengan mudah dan menentukan sama ada integer besar adalah prima. Untuk ujian primaliti berskala besar, algoritma Lucas-Lehmer sangat cekap dan boleh menentukan primaliti nombor Mönisen dengan cepat. Artikel ini menyediakan contoh kod yang sepadan, dengan harapan dapat membantu pembaca menjalankan ujian primaliti integer besar dalam amalan.

Rujukan:

• "Ujian keutamaan Lucas–Lehmer Wikipedia, The Free Encyclopedia URL: https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test
• "GMP Manual . URL: https://www.php.net/manual/en/book.gmp.php

Di atas ialah artikel tentang cara menggunakan PHP dan GMP untuk melaksanakan ujian keutamaan Lucas-Lehmer bagi integer besar, juga sebagai contoh kod yang sepadan.

Atas ialah kandungan terperinci Cara menggunakan PHP dan GMP untuk melaksanakan ujian keutamaan Lucas-Lehmer bagi integer besar. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!