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$.
$\begingroup$
$\endgroup$
7
-
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 RicherbyMar 30, 2014 at 11:59
-
3$\begingroup$ In case $x$ and $z$ are coprime, you can use Euler's theorem (wiki). $\endgroup$– hengxinMar 30, 2014 at 12:47
-
$\begingroup$ It is also a good idea to reduce $x$ modulo $z$. $\endgroup$– Yuval FilmusMar 30, 2014 at 12:55
-
1$\begingroup$ this is the std algorithm in RSA encryption/decryption try refs on that $\endgroup$– vznMar 30, 2014 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 FilmusMar 31, 2014 at 19:25
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
4
Here is the quickest way I can think. Assume first that $x$ and $z$ are coprime.
Factor $z = \prod_i p_i^{a_i}$ and calculate $\varphi(z) = \prod_i p_i^{a_i-1} (p_i-1)$.
Compute $x' = x \pmod{z}$ and $y' = y \pmod \varphi(z)$, so that $x^y \equiv x'^{y'} \pmod{z}$.
Compute $x'^{y'} \pmod{z}$ using repeated squaring.
Here is what to do in the more general case.
Factor $z = \prod_i p_i^{a_i}$ and calculate $\varphi(z) = \prod_i p_i^{a_i-1} (p_i-1)$.
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}$.
Compute $g^{y'} \pmod{z}$ using repeated squaring.
Factor $h = \prod_i p_i^{b_i}$.
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$.
Compute $\prod_i p_i^{c_i} \equiv h^y \pmod{z}$.
Compute $g^{y'} h^y \equiv x^y \pmod{z}$.
answered Mar 30, 2014 at 13:10
-
$\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$– vznMar 31, 2014 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$ Mar 31, 2014 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$– vznMar 31, 2014 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$ Mar 31, 2014 at 19:24
$\begingroup$
$\endgroup$
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.
