What is the gmp_nextprime algorithm?

Question

I am relearning a lot of PHP currently and I have come across gmp.

I know that gmp can be added to PHP, but what if you cant?

The usual prime listing method involves:

$max = 10;
for( $prime = 2; $prime <= $max; $prime++ ) {
    for( $count = 2; $count < $prime; $count++ ) {
        if( $prime % $count == 0 ) {
            break;
        }
    }
    if( $count == $prime )
        echo "Prime: ", $prime, "<br>";
    }
}

It is very slow when reaching over thousands.

For gmp it only takes a couple of milliseconds.

What is its algorithm?

How does it find the next prime number?

Answer 1

Here is the link. http://php.net/manual/en/function.gmp-nextprime.php

This function uses a probabilistic algorithm to identify primes and chances to get a composite number are extremely small.

This quote comes from the link. The link specifies that the function uses probabilistic algorithm. The algorithm may end up getting composite number. But, the chances are extremely small.

There is also a good article about probabilistic algorithm.

https://www.sciencedirect.com/science/article/pii/0022314X80900840