0
$\begingroup$

What is the cheapest and fastest way to find the remainder of the modular arithmetic $\pmod {n}$ when we have the reminder for $\pmod {n-1}$ or $\pmod {n+1}$ ?

As an example, if:

$ 3^{60} \equiv 128433\pmod {2^{20}} $

then

$ 3^{60} \equiv ?\pmod {2^{20}+1} $

1 Answers 1

1

Unfortunately, for sufficiently large numbers $x$, the remainder of $x$ modulo $m$ has absolutely nothing to do with the remainder of $x$ modulo $n$ when $m$ and $n$ are relatively prime.

It may be possible to use some method to use the remainder modulo $2^{20}$ to accelerate the calculation of the remainder modulo $2^{96}$ (which would be the exact value) and then reduce that result modulo $2^{20} + 1$. For this particular calculation, I find it very unlikely that any such approach would be more efficient than computing it directly.

  • 1
    The nature of -- in particular, I have the Chinese Remainder Theorem in mind, which says not only can $x$ have any possible pair of remainders modulo $m$ and $n$, but remainders happen *uniformly* in the sense that in any set of $mn$ consecutive integers, you will see each pair of possible residues exactly once.2012-12-22