Would someone mind elaborating the explanation in the manual?

[Brian Hurt]

On Fri, 24 Oct 2003, 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--
> 
> Needless to say I don't understand this. Does someone have either a
> web site that has the formulas describing this process (also if
> possible a proof) or some example code that achieves this purpose?

int foo(mpz_t x) {
    /* Returns 1 if x is divisible by 23, 29, or 31 */
    unsigned long m = mpz_fdiv_ui(x, 23ul * 29ul * 31ul);

    if (((m % 23) == 0) || ((m % 29) == 0) || ((m % 31) == 0)) {
        return 1;
    } else {
        return 0;
    }
}

Assume we're interested in prime p.  We know that x mod (p * k) = m for
some k.  In other words, we know that x = t * (p * k) + m for some t.  If
m mod p = 0, i.e. m = u * p for some u, then x = t * (p * k) + (u * p) =
(t * k + u) * p, which means that x mod p = 0.

This is a speed up because compared to doing a long mod long, doing a 
mpz_t mod long is expensive.  The above code is almost 3x as fast as the 
naive implementation:

int foo(mpz_t x) {
    if ((mpz_fdiv_ui(x, 23ul) == 0ul) || (mpz_fdiv_ui(x, 29ul) == 0ul)
        || (mpz_fdiv_ui(x, 31ul) == 0ul)) 
    {
        return 1;
    } else {
        return 0;
    }
}

Brian