mpz_nextprime

[Niels Möller]

Seth Troisi <braintwo at gmail.com> writes:

> Yes I've tried that too. It was the same exact speed, so I started to
> profile the function, which hasn't been easy.
> I think the vast majority (98%+) of the function is spent in calls to
> mpz_rabinmiller.

Good to have some profile numbers! Then microoptimizations elsewhere
will not make any significant difference.

To get better speed, we'd need to either increase the size of the prime
table used for sieving considerably, say by a factor of 2, 5 or 10.

Or speed up detection of composites in mpz_millerrabin, unclear how.

I think I've seen comments in the literature saying that 2^e mod m is
"obviously" more efficient than general modular exponentiation. But as
far as I can tell, b^e mod m with small b needs essentially one modular
squaring per bit in the exponent, including the special case b = 2. But
if there's something clever I'm missing, it could be used to speed up
mpz_millerrabin.

And I'm not sure how well we currently do small-base modexp in gmp.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.