Cara menggunakan PHP dan GMP untuk melaksanakan ujian keutamaan Miller-Rabin bagi nombor besar

Cara melaksanakan ujian keutamaan Miller-Rabin bagi nombor besar menggunakan PHP dan GMP

Pengenalan:
Nombor perdana memainkan peranan penting dalam kriptografi dan sains komputer. Ujian keutamaan Miller-Rabin ialah algoritma kebarangkalian yang digunakan untuk menguji sama ada suatu nombor adalah perdana. Ia memberikan jawapan yang betul dengan kebarangkalian yang tinggi. Artikel ini akan memperkenalkan cara menggunakan bahasa PHP dan pustaka GMP (Perpustakaan Aritmetik Berbilang Ketepatan GNU) untuk melaksanakan algoritma ujian keutamaan Miller-Rabin untuk nombor yang besar.

Pengenalan perpustakaan GMP:
Pustaka GMP ialah perpustakaan sumber terbuka untuk pengiraan ketepatan tinggi, yang menyediakan sokongan untuk integer yang besar. Kita boleh menggunakan perpustakaan GMP untuk mengendalikan pengiraan nombor besar, termasuk penambahan, penolakan, pendaraban, pembahagian dan operasi nombor besar lain.

Prinsip algoritma:
Algoritma ujian primaliti Miller-Rabin adalah berdasarkan lanjutan Teorem Kecil Fermat. Teorem menyatakan bahawa jika nombor perdana p dan integer a adalah relatif perdana dan a^(p-1) ≡ 1 (mod p), maka a ialah asas p, dan p mempunyai lebih daripada separuh tapak.

Menurut algoritma ujian primaliti Miller-Rabin, kita boleh menentukan sama ada nombor adalah perdana dengan kebarangkalian tertentu dengan memilih asas yang berbeza beberapa kali. Idea algoritma ialah untuk setiap nombor n yang diuji, kami memilih asas rawak b, dan kemudian mengira a^d ≡ 1 (mod n) dan a^(2^r*d) ≡ -1 (mod n ) Sama ada ia benar, jika ia benar, maka n mungkin nombor perdana jika tidak, kita boleh pastikan bahawa n ialah nombor komposit.

Contoh kod:

<?php

// 导入GMP库
if (!extension_loaded('gmp')) {
    dl('gmp.so');
}

function millerRabinTest($n, $k = 20) {
    if ($n <= 1 || $n == 4) {
        return false;
    }
    if ($n <= 3) {
        return true;
    }

    // 将$n-1表示为(2^r) * d的形式
    $r = 0;
    $d = $n - 1;
    while (gmp_mod($d, 2) == 0) {
        $d >>= 1;
        $r++;
    }

    for ($i = 0; $i < $k; $i++) {
        $a = gmp_random_range(2, $n - 2);
        $x = gmp_powm($a, $d, $n);

        if ($x == 1 || $x == $n - 1) {
            continue;
        }

        $continueLoop = false;
        for ($j = 0; $j < $r - 1; $j++) {
            $x = gmp_powm($x, 2, $n);
            if ($x == 1) {
                return false;
            }
            if ($x == $n - 1) {
                $continueLoop = true;
                break;
            }
        }

        if (!$continueLoop) {
            return false;
        }
    }

    return true;
}

// 测试示例
$numbers = [
    gmp_init('2'),
    gmp_init('3'),
    gmp_init('4'),
    gmp_init('17'),
    gmp_init('7919'),
    gmp_init('999999999999999993')
];

foreach ($numbers as $number) {
    echo gmp_strval($number) . ' is ' . (millerRabinTest($number) ? 'prime' : 'composite') . PHP_EOL;
}

Contoh ini menggunakan fungsi millerRabinTest() untuk menguji sama ada nombor ialah perdana Parameter $k mewakili bilangan lelaran ujian. Dalam contoh ujian, kami menguji beberapa nombor secara berasingan dan mencetak keputusan ujian.

Ringkasan:
Algoritma ujian primaliti Miller-Rabin ialah algoritma pengesanan primaliti yang cekap, terutamanya sesuai untuk nombor yang besar. Menggunakan bahasa PHP dan perpustakaan GMP, kami boleh melaksanakan algoritma ini dengan mudah. Melalui ujian keutamaan Miller-Rabin, kami boleh menentukan dengan berkesan sama ada nombor itu adalah perdana, sekali gus menyediakan alat yang berkuasa dalam kriptografi, keselamatan dan bidang lain.

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