Would someone mind elaborating the explanation in the manual?

[Sisyphus]

David McKen wrote:
> In the efficiency section of the GMP manual I came across the
> following couple lines
> 
> --Begin quote--
> However when testing divisibility by several small integers, it's
> best to take a remainder modulo their product, to save
> multi-precision operations. For instance to test whether a number is
> divisible by any of 23, 29 or 31 take a remainder modulo 23*29*31 =
> 20677 and then test that.
> --End quote--
> 

It's telling you to calculate R = bignum % 20677, and to then check R 
for divisibility by 23, 29, and 31.

That will work because if x divides bignum, x also divides
bignum % (x * a) for all non-zero integers a.
And if x does not divide bignum, x does not divide
bignum % (x * a) for any non-zero integer a.

It will be quicker because it is faster to check R for divisibility by 
23, 29, and 31 than it is to check bignum for divisibility by those same 
3 numbers. There's a cost in calculating R in the first place, but that 
cost is more than offset by the savings.

At least, that's how I'm reading it. As to whether there's a saving 
would, I think, depend upon the size of bignum, and upon the number of 
small integers for which divisibility needs to be tested. (If it were 
me, I'd want to do some timings to check .... I'm a little dubious that 
you'll find a saving for only 2 small test divisors).

I've also seen literature (not specifically relating to GMP) suggesting 
that you could simply calculate the gcd of bignum and 20677 - or you 
could extend that to calculating the gcd of R and 20677. You have to be 
a little careful there if the "small" numbers are not primes - and I 
don't know how that method stacks up (speed-wise) against the above 
recommendation.

Hth.

Cheers,
Rob

-- 
Any emails containing attachments will be deleted from my ISP's mail 
server before I even get to see them. If you wish to email me an 
attachment, please provide advance warning so that I can make the 
necessary arrangements.