Computing A mod d (for small odd d without division and multiplication)

[Torbjörn Granlund]

marco.bodrato at tutanota.com writes:

  d is odd, right? So it's a product of odd primes.

Indeed.

One could generalise, but we know how to compute A mod 2^k very
efficiently (k is the largest integer for which d/2^k is an integer),
then use CRT.

  For every odd prime p, the order of Z/pZ* is even, and the size of
  rems[] is the size of the order of 2^GMP_NUMB_BITS modulo d.  If
  GMP_NUMB_BITS is even (as usual), 2^GMP_NUMB_BITS is a square, and it
  can not be a generator.

Sure.

  I mean, mp_limbs_t rems [d-GMP_NUMB_BITS%2 >> 1-GMP_NUMB_BITS%2];
  should be large enough.

I am not sure how to interpret that expression.

  The divisors of 2^(GMP_NUMB_BITS)-1, right?

Yes all these, and some more.

  ? #divisors(2^(64*3)-1)
  49152

Huh?

-- 
Torbjörn
Please encrypt, key id 0xC8601622