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

[Niels Möller]

marco.bodrato at tutanota.com writes:

> Let's take some examples:
>  - 47, the order of 2^64 mod 47 is 23, and also the order of 2 is 23;
>    this means that 23 divides 2^(23*2)-1;

You mean that _47_ divides 2^(23*2)-1, right? It appears to also divide
2^23 - 1.

>    should we really perform a 23-passes computation with 23 multiplications and modulus,
>    or should we better reduce the number modulo 2^46-1 with some bit trickery,
>    and perform a single last step mod 47?

If I try to rephrase what you are saying: Whenever the order of 2 mod d
is "small" (so that the needed "rem" array is small), then d divides 2^k
- 1 for a small k, and reducing mod that larger modulo could then be
done with shifts and adds rather than multiplies.

Some off-the-top-of-my-head observations:

There should be a similar trick for d dividing 2^k + 1.

There may be a divide-and-conquer analogue (with no asymptotic gain, as
far as I see, but possibly more efficient if cycle/limb is smaller for
plain add that for the mod logic: Before reducing mod 2^k-1, we could
reduce mod 2^{2k}-1, and before that mod 2^{4k} - 1, etc. (But then
again clever mod algorithms may have *smaller* cycle/limb than plain add,
due to operations being more independent).

> Could you read them only partially?
> Unfortunately, I do not have many options I can play with on this server.

It's weird. This mail came through all the way. Previous mails have
appeared in my imap inbox (so I could see them in K-9 mail on my phone),
but then my old-fashioned MUA setup (in emacs Gnus) moves all new mail
from the mail server and sorts into local folders, and at that step,
your recent mails have disappeared. One potential way this could happen
is if you reuse message ids (since my MUA discards duplicates, based on
message ID), but after looking in the archive file
https://gmplib.org/list-archives/gmp-devel/2026-March.txt.gz I see no
duplicates. So I'm puzzled.

Regards,
/Niels

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.