GMP function to generate prime number bigger than X

Marco Bodrato bodrato at
Thu Jan 27 01:04:41 CET 2022


Il 2022-01-26 14:41 Hans Petter Selasky ha scritto:
> On 1/26/22 14:17, Torbjörn Granlund wrote:
>> Hans Petter Selasky <hps at> writes:

>>    Basically I wanted to avoid the Miller Rabin test, because any 
>> prime
>>    will do, not just the next one.

> Let me restate that. I need a prime, which also has the property, that
> two in the power of "N", does not become equal to one before "N"
> reaches "prime" minus one. Not all primes have the property. Not sure
> what this is called in formal language.

So, probably, "the next one" may not fit your needs, but for sure not 
"any prime will do".
"In formal language" probably you want 2 to generate the multiplicative 

This means that mpz_nextprime may not be the best you can choose. Anyway 
consider also to test the timings with the development version from the 
[ ]
Some speed-up where added to mpz_nextprime (By Seth Troisi) and to 
primality tests.


More information about the gmp-discuss mailing list