Rumah pembangunan bahagian belakang tutorial php Cara menggunakan PHP dan GMP untuk menguji teorem Fermat untuk integer besar

Cara menggunakan PHP dan GMP untuk menguji teorem Fermat untuk integer besar

Jul 29, 2023 am 11:13 AM
php gmp integer besar

Cara menggunakan PHP dan GMP untuk menguji Teorem Kecil Fermat untuk integer besar

Teorem Kecil Fermat ialah salah satu teorem penting dalam teori nombor. Ia boleh digunakan untuk melakukan ujian primaliti integer besar, iaitu, untuk menentukan sama ada integer besar adalah perdana. Dalam artikel ini, kami akan memperkenalkan cara menggunakan PHP dan perpustakaan sambungan GMP untuk melaksanakan ujian teorem Fermat kecil bagi integer besar.

Pertama sekali, kita perlu memahami prinsip Teorem Kecil Fermat. Teorem Kecil Fermat dinyatakan seperti berikut:

Jika p ialah nombor perdana, a ialah sebarang integer, dan a tidak boleh dibahagikan dengan p, maka a^(p-1) ≡ 1 (mod p).

Mengikut Teorem Little Fermat, kita boleh menjalankan ujian Teorem Little Fermat untuk integer yang besar. Langkah khusus adalah seperti berikut:

Langkah 1: Import pustaka sambungan GMP

Memandangkan fungsi terbina dalam PHP tidak dapat mengendalikan integer yang besar, kami perlu mengimport pustaka sambungan GMP untuk mengendalikan integer yang besar. Dalam PHP, anda boleh mengimport perpustakaan sambungan GMP melalui kod berikut:

if (extension_loaded('gmp')) {
    echo "GMP扩展库已加载。
";
} else {
    echo "GMP扩展库未加载。
";
    exit;
}
Salin selepas log masuk

Langkah 2: Laksanakan fungsi ujian teorem Fermat

Kita boleh melaksanakan ujian teorem Fermat untuk integer besar dengan mentakrifkan fungsi. Fungsi ditakrifkan seperti berikut:

function fermatTest($n, $k) {
    for ($i = 0; $i < $k; $i++) {
        $a = gmp_random_range(2, $n-1); // 随机选择一个整数a
        $result = gmp_powm($a, $n-1, $n); // 计算 a^(n-1) mod n
        if (gmp_cmp($result, 1) !== 0) { // 如果结果不等于1,则n不是素数
            return false;
        }
    }
    return true; // 如果所有测试都通过,则n可能是素数
}
Salin selepas log masuk

Dalam kod di atas, kami menggunakan fungsi gmp_random_range untuk menjana integer rawak $a$ antara 2 dan $n-1$, dan kemudian gunakan fungsi gmp_powm untuk mengira $a^{n -1 } Hasil mod n$. Jika keputusan tidak sama dengan 1, maka $n$ bukan nombor perdana dan mengembalikan palsu jika tidak, teruskan dengan ujian seterusnya. Jika semua ujian lulus, maka $n$ mungkin perdana, kembalikan benar.

Langkah 3: Fungsi ujian

Kita boleh menulis fungsi ujian untuk mengesahkan ketepatan fungsi ujian teorem Fermat yang dilaksanakan. Fungsi ujian ditakrifkan seperti berikut:

function testFermatTest($n) {
    if (fermatTest($n, 10)) { // 进行10次小费马定理测试
        echo "{$n} 可能是素数。
";
    } else {
        echo "{$n} 不是素数。
";
    }
}
Salin selepas log masuk

Dalam kod di atas, kami memanggil fungsi fermatTest untuk menguji teorem Fermat 10 kali, dan kemudian mengeluarkan maklumat yang sepadan berdasarkan keputusan ujian.

Langkah 4: Jalankan ujian

Akhir sekali, kita boleh memanggil fungsi ujian untuk melaksanakan ujian teorem Fermat. Sebagai contoh, kita boleh menguji integer yang lebih besar 100000000000000000003 dengan kod berikut:

testFermatTest(gmp_init("100000000000000000003"));
Salin selepas log masuk

Dalam kod di atas, kita menggunakan fungsi gmp_init untuk menukar rentetan "1000000000000000003" ke dalam integer kecil, kemudian melakukan ujian.

Melalui langkah di atas, kita boleh menggunakan perpustakaan sambungan PHP dan GMP untuk menguji teorem Fermat kecil bagi integer besar. Ini adalah kaedah yang mudah tetapi berkesan untuk menentukan sama ada integer besar adalah perdana.

Sila ambil perhatian bahawa dalam aplikasi praktikal, ujian Teorem Fermat sering digabungkan dengan kaedah ujian lain untuk meningkatkan ketepatan dan kebolehpercayaan ujian.

Atas ialah kandungan terperinci Cara menggunakan PHP dan GMP untuk menguji teorem Fermat untuk integer besar. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

AI Hentai Generator

Menjana ai hentai secara percuma.

Artikel Panas

R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)
2 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Repo: Cara menghidupkan semula rakan sepasukan
1 bulan yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Cara mendapatkan biji gergasi
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Konfigurasi Projek CakePHP Konfigurasi Projek CakePHP Sep 10, 2024 pm 05:25 PM

Dalam bab ini, kita akan memahami Pembolehubah Persekitaran, Konfigurasi Umum, Konfigurasi Pangkalan Data dan Konfigurasi E-mel dalam CakePHP.

Panduan Pemasangan dan Naik Taraf PHP 8.4 untuk Ubuntu dan Debian Panduan Pemasangan dan Naik Taraf PHP 8.4 untuk Ubuntu dan Debian Dec 24, 2024 pm 04:42 PM

PHP 8.4 membawa beberapa ciri baharu, peningkatan keselamatan dan peningkatan prestasi dengan jumlah penamatan dan penyingkiran ciri yang sihat. Panduan ini menerangkan cara memasang PHP 8.4 atau naik taraf kepada PHP 8.4 pada Ubuntu, Debian, atau terbitan mereka

Tarikh dan Masa CakePHP Tarikh dan Masa CakePHP Sep 10, 2024 pm 05:27 PM

Untuk bekerja dengan tarikh dan masa dalam cakephp4, kami akan menggunakan kelas FrozenTime yang tersedia.

Muat naik Fail CakePHP Muat naik Fail CakePHP Sep 10, 2024 pm 05:27 PM

Untuk mengusahakan muat naik fail, kami akan menggunakan pembantu borang. Di sini, adalah contoh untuk muat naik fail.

Penghalaan CakePHP Penghalaan CakePHP Sep 10, 2024 pm 05:25 PM

Dalam bab ini, kita akan mempelajari topik berikut yang berkaitan dengan penghalaan ?

Bincangkan CakePHP Bincangkan CakePHP Sep 10, 2024 pm 05:28 PM

CakePHP ialah rangka kerja sumber terbuka untuk PHP. Ia bertujuan untuk menjadikan pembangunan, penggunaan dan penyelenggaraan aplikasi lebih mudah. CakePHP adalah berdasarkan seni bina seperti MVC yang berkuasa dan mudah difahami. Model, Pandangan dan Pengawal gu

Cara Menyediakan Kod Visual Studio (Kod VS) untuk Pembangunan PHP Cara Menyediakan Kod Visual Studio (Kod VS) untuk Pembangunan PHP Dec 20, 2024 am 11:31 AM

Kod Visual Studio, juga dikenali sebagai Kod VS, ialah editor kod sumber percuma — atau persekitaran pembangunan bersepadu (IDE) — tersedia untuk semua sistem pengendalian utama. Dengan koleksi sambungan yang besar untuk banyak bahasa pengaturcaraan, Kod VS boleh menjadi c

Pengesah Mencipta CakePHP Pengesah Mencipta CakePHP Sep 10, 2024 pm 05:26 PM

Pengesah boleh dibuat dengan menambah dua baris berikut dalam pengawal.

See all articles