How can WolframAlpha exponentiate numbers so quickly?

Question

I was wondering how RSA algorithm deals with such big numbers and tried one example in WolframAlpha. How can they deal with such crazy numbers?

EDIT: Just to make it more bizarre, one more example

Answer 1

There's a simple algorithm called exponentiation by squaring that can be used to compute a^b mod c very efficiently. It's based on the observation that

a^2k mod c = (a^k)² mod c

a^{2k + 1} mod c = a · (a^k)² mod c

Given this, you can compute a^b mod c with this recursive approach:

function raiseModPower(a, b, c):
    if b == 0 return 1
    let d = raiseModPower(a, floor(b/2), c)
    if b mod 2 = 1:
        return d * d * a mod c
    else
        return d * d mod c

This does only O(log b) multiplications, each of which can't have any more digits in them than O(log c), so it's really fast. This is how RSA implementations raise things to powers as well. You can rewrite this to be iterative if you'd like, though I think the recursive presentation is really clean.

Once you have this algorithm, you can use standard techniques for multiplying arbitrary-precision numbers to do the computation. Since only O(log b) iterations of the multiplication are required (as opposed to, say, b iterations), it's crazy fast. You never actually end up computing a^b and then modding it by c, which also keeps the number of digits low and makes it even faster.

Hope this helps!