question on obtaining modulo values quickly

[Marco Bodrato]

Ciao,

Il 2022-03-09 21:32 Randall Rathbun ha scritto:
> Can anyone show by example, how the remainders or % is done quickly,
> using addition for the values of 9,5,7, 13, 17, and 97 as is used for
> the perfect square check routine?

How can you check the remainder of a long number modulo 11?
Consider it as a number written in base 100, add-up all the
"(double)digits"; the remainder of the resulting sum is the remainder of
the original number.

Why does this work? Because 100 = 1 (mod 11).


For the values you mention, GMP consider numbers in base 2^48 (2^24 on
32-bits platforms), i.e. computes the sum of all the chunks of 48 bits
(resp. 24, but you don't get the result modulo 97 in that case) from the
binary representation of the number.

If I understand correctly, you'd like to implement the %19 operation.
Since 2^18 = 1 (mod 19), Fermat says. You can add chunks of 18 bits (or
36, or...).

Ĝis,
m