mpz_nextprime

[Marco Bodrato]

Ciao,

Il Mer, 4 Settembre 2019 10:44 am, Niels Möller ha scritto:
> Seth Troisi <braintwo at gmail.com> writes:

>> I think the vast majority (98%+) of the function is spent in calls to
>> mpz_rabinmiller.

> 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.

Spending more time in sieving and reducing the number of calls surely is a
good idea.

> 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

One modular squaring and some products ...

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

We basically do not do anything special. So that small-base or large-base
will take the same time.

With the special case b=2 one may save a few operation seeding the process
with a 2-power smaller than the modulus, but this is a little saving.

Moreover one may avoid the windowing on the exponent (we currently
pre-compute b^3, b^5, b^7... so that we need fewer products) and use a
shift by a single bit every time a multiplication times the base is
needed.
Since we use a REDC-representation, implementing this is not completely
obvious, but anyway it shoul not be too difficult.
This means writing a special function for b=2, not for more general small
bases. Currently I do not have the time to, anyone?

Ĝis,
m