mpz_nextprime
Marco Bodrato
bodrato at mail.dm.unipi.it
Wed Sep 4 15:07:23 UTC 2019
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
More information about the gmp-devel
mailing list