5
$\begingroup$

What are the possible ways to calculate $(x^y) \bmod z$ quickly for very large integers? Integers $x,y \lt 10^{10000}$ and $z \lt 10^6$.

$\endgroup$
  • 2
    $\begingroup$ If you're working modulo a million or less, $x$ is not of order of $10^{10000}$. And you know about repeated squaring, right? $\endgroup$ – David Richerby Mar 30 '14 at 11:59
  • 3
    $\begingroup$ In case $x$ and $z$ are coprime, you can use Euler's theorem (wiki). $\endgroup$ – hengxin Mar 30 '14 at 12:47
  • $\begingroup$ It is also a good idea to reduce $x$ modulo $z$. $\endgroup$ – Yuval Filmus Mar 30 '14 at 12:55
  • 1
    $\begingroup$ this is the std algorithm in RSA encryption/decryption try refs on that $\endgroup$ – vzn Mar 30 '14 at 17:10
  • 1
    $\begingroup$ @vzn In RSA $z$ is crucially a product of two primes, which makes it difficult to compute $\varphi(z)$. Also, $z$ is substantially larger in RSA. $\endgroup$ – Yuval Filmus Mar 31 '14 at 19:25
4
$\begingroup$

Here is the quickest way I can think. Assume first that $x$ and $z$ are coprime.

  1. Factor $z = \prod_i p_i^{a_i}$ and calculate $\varphi(z) = \prod_i p_i^{a_i-1} (p_i-1)$.

  2. Compute $x' = x \pmod{z}$ and $y' = y \pmod \varphi(z)$, so that $x^y \equiv x'^{y'} \pmod{z}$.

  3. Compute $x'^{y'} \pmod{z}$ using repeated squaring.

Here is what to do in the more general case.

  1. Factor $z = \prod_i p_i^{a_i}$ and calculate $\varphi(z) = \prod_i p_i^{a_i-1} (p_i-1)$.

  2. Compute $x' = x \pmod{z}$, $y' = y \pmod \varphi(z)$, $g = gcd(x',z)$, $h = x'/g$, so that $x^y \equiv g^{y'} h^y \pmod{z}$.

  3. Compute $g^{y'} \pmod{z}$ using repeated squaring.

  4. Factor $h = \prod_i p_i^{b_i}$.

  5. Compute $c_i = \min(a_i,yb_i)$. This is easy since we only need to explicitly compute $yb_i$ when $y \leq a_i$.

  6. Compute $\prod_i p_i^{c_i} \equiv h^y \pmod{z}$.

  7. Compute $g^{y'} h^y \equiv x^y \pmod{z}$.

$\endgroup$
  • $\begingroup$ it would help to tie all this in to standard algorithms, the literature/refs (is it similar to something published? unpublished variant? etc), and also, how does it compare to the widely known method of repeated squaring as cited by DR? $\endgroup$ – vzn Mar 31 '14 at 18:01
  • $\begingroup$ @vzn When $(x,z)=1$, this is just a trivial optimization of repeated squaring. In the general case, we need to work a bit harder, but at the heart is the same repeated squaring approach. It is probable that this algorithm or something very similar can be found in the literature, it would be nice if you could provide such a reference. $\endgroup$ – Yuval Filmus Mar 31 '14 at 18:49
  • $\begingroup$ not an expert on this & not widely familiar with the literature on it but could you be using the chinese remainder thm as cited by vonbrand in all this? that seems to be the case in factoring $z$ $\endgroup$ – vzn Mar 31 '14 at 19:04
  • $\begingroup$ My algorithm uses the Chinese remainder theorem in the general case $(x,z) > 1$. It might or might not be more efficient to apply repeated squaring through the CRT (for $z$ fitting in a machine word, it is probably not worthwhile). We have to factor $z$ so that we can compute $\varphi(z)$, but since $z$ is small this is not an issue here. $\endgroup$ – Yuval Filmus Mar 31 '14 at 19:24
5
$\begingroup$

Computation with large integers is one of the topics of Knuth's "Seminumerical Algorithms" (volume 2 of "The Art of Computer Programming"). Results in elementary number theory, like the properties of modular arithmetic, the Chinese Remainder Theorem, Fermat's little theorem/Euler's theorem are critical here.

As commented, this operation is central in cryptography, like RSA. Doing this operation efficiently for fixed $y$ and $z$ are critical.

There are several efficient libraries for doing multiprecision computation, perhaps the most known is GMP, which in turn is used in several languages that offer "big integers." Most computer algebra systems offer computation with large integers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.