Improvement to mpz_nextprime

[Paul Zimmermann]

> The only remaining question is how to obtain the starting residues =20
> for the sieve (e.g. in a call to mpz_nextprime(10^1000), one would =20
> have to compute 10^1000 mod 2, 3, 5, 7, 11, etc.) If subquadratic =20
> division is implemented, then the best strategy is, I believe:
> 
> -Compute m =3D 2*3*5*7*11*... up until the number is about half the =20
> size of 10^1000;
> -Compute r =3D 10^1000 mod m;
> -Break up m in two similarly sized halves m_1 and m_2;
> -Compute r_1 =3D r mod m_1 and r_2 =3D r mod m_2;
> -Proceed recursively until the modulos are prime.

The good reference for that is Dan Bernstein's page.

Paul