Implementing Large Integer Fermat's Little Theorem Primality Test with PHP and GMP

Introduction to Fermat's Little Theorem

Fermat's Little Theorem is a fundamental result in number theory, commonly used for primality testing. It states that if p is a prime number and a is any integer not divisible by p, then a^{p-1} \equiv 1 \pmod{p}. This theorem can be applied to verify if a large number is prime.

Using GMP Extension for Large Integer Handling

Since PHP's native functions have limitations when handling very large integers, the GMP extension provides efficient arbitrary precision arithmetic. First, ensure that the GMP extension is loaded as shown below:

if (extension_loaded('gmp')) {
    echo "GMP extension is loaded.";
} else {
    echo "GMP extension is not loaded.";
    exit;
}

Implementing the Fermat Primality Test Function

Define a function that uses GMP's arithmetic to perform multiple randomized tests, determining the primality of a large integer:

function fermatTest($n, $k) {
    for ($i = 0; $i < $k; $i++) {
        $a = gmp_random_range(2, $n - 1);  // Random integer a
        $result = gmp_powm($a, $n - 1, $n);  // Compute a^(n-1) mod n
        if (gmp_cmp($result, 1) !== 0) {  // If result is not 1, n is composite
            return false;
        }
    }
    return true;  // Passes all tests, n is probably prime
}

Testing the Function

To verify the correctness of the Fermat test, define a helper function that calls it multiple times:

function testFermatTest($n) {
    if (fermatTest($n, 10)) {  // Perform 10 Fermat tests
        echo "{$n} is probably prime.";
    } else {
        echo "{$n} is not prime.";
    }
}

Example of Running the Test

Here is an example of testing a very large integer using the implemented functions:

<span class="fun">testFermatTest(gmp_init("100000000000000000003"));</span>

The code converts the string into a GMP large integer with gmp_init and runs the primality check.

Conclusion

By leveraging PHP's GMP extension, we can implement an effective Fermat primality test for large integers. This approach is straightforward and useful for preliminary prime checking. For increased accuracy, Fermat testing is often combined with other primality tests.