How to use PHP and GMP to test Fermat's theorem for large integers

How to use PHP and GMP to test Fermat's Little Theorem for large integers

Fermat's Little Theorem is one of the important theorems in number theory. It can be used to perform primality testing of large integers, that is, to determine whether a large integer is prime. In this article, we will introduce how to use PHP and the GMP extension library to perform testing of Fermat's Little Theorem for large integers.

First of all, we need to understand the principle of Fermat's theorem. Fermat's Little Theorem is expressed as follows:

If p is a prime number, a is any integer, and a is not divisible by p, then a^(p-1) ≡ 1 (mod p).

According to the Little Fermat Theorem, we can test the Little Fermat Theorem for large integers. The specific steps are as follows:

Step 1: Import the GMP extension library

Since PHP’s built-in functions cannot handle large integers, we need to import the GMP extension library to process large integers. In PHP, you can import the GMP extension library through the following code:

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

Step 2: Implement the Little Fermat Theorem test function

We can implement the Little Fermat Theorem for large integers by defining a function test. The function is defined as follows:

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可能是素数
}

In the above code, we use the gmp_random_range function to generate a random integer $a$ between 2 and $n-1$, and then use the gmp_powm function to calculate $a^ The result of {n-1} mod n$. If the result is not equal to 1, then $n$ is not a prime number and returns false; otherwise, continue with the next test. If all tests pass, then $n$ is probably prime, return true.

Step 3: Test function

We can write a test function to verify the correctness of the implemented Little Fermat Theorem test function. The test function is defined as follows:

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

In the above code, we call the fermatTest function to test Fermat's theorem 10 times, and then output the corresponding information based on the test results.

Step 4: Execute the test

Finally, we can call the test function to perform the little Fermat theorem test. For example, we can test a larger integer 100000000000000000003 with the following code:

testFermatTest(gmp_init("100000000000000000003"));

In the above code, we use the gmp_init function to convert the string "100000000000000000003" into a large integer, and then perform the Fermat theorem test.

Through the above steps, we can use PHP and GMP extension libraries to test the small Fermat theorem of large integers. This is a simple yet effective method for determining whether a large integer is prime.

Please note that in practical applications, Fermat's Theorem test is often combined with other testing methods to improve the accuracy and reliability of the test.

The above is the detailed content of How to use PHP and GMP to test Fermat's theorem for large integers. For more information, please follow other related articles on the PHP Chinese website!