How to use PHP and GMP to implement Fermat primality testing of large numbers

How to use PHP and GMP to implement the Fermat primality test of large numbers

Introduction:
Fermat primality test is a simple method for detecting whether a number is prime. This method is based on Fermat's little theorem, which states that if p is a prime number and a is a positive integer less than p, then a^(p-1) ≡ 1 (mod p). This theorem allows us to test whether a number is prime using a randomly chosen a. In this article, we will use PHP and GMP libraries to implement Fermat primality testing of large numbers.

Installation and Setup:
First, make sure that PHP and GMP libraries are installed on your system. If you haven't installed them yet, you can install them by running the following command in the command line:

sudo apt-get install php
sudo apt-get install php-gmp

Next, create a file called "fermat_prime.php" and open it with a text editor.

Implement the Fermat primality test function:
Add the following code to implement the Fermat primality test function:

<?php

function is_prime($n, $k)
{
    if ($n <= 1 || $n == 4) {
        return false;
    }
    if ($n <= 3) {
        return true;
    }
 
    while ($k > 0) {
        // 随机选择一个 [2, $n-2] 之间的整数
        $a = gmp_random_range(2, $n-2);
 
        // 使用 GMP 函数进行幂运算
        $res = gmp_powm($a, $n-1, $n);
 
        // 如果不满足费马小定理，则 n 不是素数
        if (gmp_cmp($res, 1) != 0) {
            return false;
        }
        $k--;
    }
 
    return true;
}

Analysis code:

• Functionis_primeAccepts two parameters, $n is the number to be tested, $k is the number of tests
• The function first checks whether $n is between 1 and 4, and if so, returns false. This is because neither 1 nor 4 are prime numbers.
• Next, the function uses a while loop to perform $k tests. In each loop, the function randomly selects a positive integer between 2 and $n-2 and uses the GMP function gmp_powm for exponentiation.
• Finally, the function compares whether the calculated power is equal to 1. If not, it returns false, indicating that the number is not a prime number.
• If the verification of Fermat's Little Theorem is passed in $k tests, the function returns true, indicating that the number may be a prime number.

Test code:
Add the following code at the end of the code file to test the effect of the is_prime function:

// 测试1: 检测一个较小的素数
$n = gmp_init("17");
$k = 5;
$result = is_prime($n, $k);
echo $result ? "$n is probable prime
" : "$n is not prime
";
 
// 测试2: 检测一个较大的合数
$n = gmp_init("123456789123456789");
$k = 5;
$result = is_prime($n, $k);
echo $result ? "$n is probable prime
" : "$n is not prime
";

Save and close the file.

Run the code:
Run the following command on the command line to execute the code file:

php fermat_prime.php

Next, you should be able to see the results of the program output on the command line:

17 is probable prime
123456789123456789 is not prime

Conclusion:
This article introduces how to use PHP and GMP libraries to implement Fermat primality testing of large numbers. With this simple test, we can tell whether a larger number is prime. Using this method, we can better understand Fermat's Little Theorem and be able to implement basic primality testing functions.

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