Idea for modulo with fixed n in GMP
diep at xs4all.nl
Sun Apr 20 16:27:26 CEST 2008
Currently a lot of crunchers are using GMP implementations to search
for big primes.
A few of them therefore will have a big need for a faster modulo, if
they aren't explicitly
searching for special cases of primes that allows a very fast modulo.
For the many
statistical researches that eat so much system time it is therefore
interesting to have
a faster modulo. Additional to that, we can expect PRP search to
really start taking off soon.
In some cases it is possible to prove them prime if P-1 can get
factorized quite a tad.
So for that single case where the crunchers aren't using Woltman
code, but GMP,
let's give them tools to do it quicker!
On Apr 20, 2008, at 2:43 PM, Torbjorn Granlund wrote:
> Vincent Diepeveen <diep at xs4all.nl> writes:
> I will have a look at the implementation. Note that at > 100k bits,
> especially million bit range it is more than factor 2 faster than
> division method to take modulo.
> I got break even between the new divide-and-conquer code and the "mu"
> Barrett code at about 10000 bits, when the total dividend approaches
> So for exponent squaring might be idea to take serious look at it.
> I am not sure Barrett's algorithm will ever become relevant for
> operands in the range one uses for RSA.
> With very good short multiplication code, it might be feasible to use
> Barrett for such small operands, but I haven't been successful in that
More information about the gmp-discuss