Idea for modulo with fixed n in GMP

[Vincent Diepeveen]

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!

Vincent

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
> infinity.
>
>   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
> area.
>
> -- 
> Torbjörn
>