How to use PHP and GMP to implement the Miller-Rabin primality test of large numbers

How to use PHP and GMP to implement the Miller-Rabin primality test of large numbers

Introduction:
Prime numbers play an important role in cryptography and computer science. The Miller-Rabin primality test is a probabilistic algorithm used to test whether a number is prime. It gives the correct answer with a high probability. This article will introduce how to use PHP language and GMP library (GNU Multiple Precision Arithmetic Library) to implement the Miller-Rabin primality testing algorithm for large numbers.

GMP library introduction:
The GMP library is an open source library for high-precision calculations. It provides support for large integers. We can use the GMP library to handle large number calculations, including large number addition, subtraction, multiplication, division and other operations.

Algorithm principle:
Miller-Rabin primality test algorithm is based on the extension of Fermat's little theorem. The theorem states: If the prime number p and the integer a are relatively prime and a^(p-1) ≡ 1 (mod p), then a is a base of p, and p has more than half of the bases.

According to the Miller-Rabin primality test algorithm, we can determine whether a number is prime with a certain probability by selecting different bases multiple times. The idea of ​​the algorithm is that for each tested number n, we select a random base b, and then calculate a^d ≡ 1 (mod n) and a^(2^r*d) ≡ -1 (mod n) Whether it is true, if it is true, then n may be a prime number; otherwise, we can be sure that n is a composite number.

Code example:

<?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;
}

This example uses the millerRabinTest() function to test whether a number is prime. The parameter $k represents the number of iterations of the test. In the test example, we tested some numbers separately and printed out the test results.

Summary:
Miller-Rabin primality testing algorithm is an efficient primality detection algorithm, especially suitable for large numbers. Using PHP language and GMP library, we can easily implement this algorithm. Through the Miller-Rabin primality test, we can effectively determine whether a number is prime, thus providing a powerful tool in cryptography, security and other fields.

The above is the detailed content of How to use PHP and GMP to implement the Miller-Rabin primality test of large numbers. For more information, please follow other related articles on the PHP Chinese website!