patternMinor
Quick calculation for $(x^y) \bmod z$
Viewed 0 times
calculationbmodforquick
Problem
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$.
Integers $x,y \lt 10^{10000}$ and $z \lt 10^6$.
Solution
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.
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.
Context
StackExchange Computer Science Q#23252, answer score: 5
Revisions (0)
No revisions yet.