Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

So I have been reading and learning a lot about cryptography lately and in particular asymmetric ciphers such as RSA.

One thing that I am curious about but never seems to be mentioned is how the cipher algorithm manages to compute such enormous numbers in reasonable amounts of time.

This example shows what I mean. Such enormous numbers, and powers of enormous numbers no less. What kind of algorithm can handle computing 35052111338673026690212423937053328511880760811579981620642802346685810623109850235943049080973386241113784040794704193978215378499765413083646438784740952306932534945195080183861574225226218879827232453912820596886440377536082465681750074417459151485407445862511023472235560823053497791518928820272257787786 to the power of 89489425009274444368228545921773093919669586065884257445497854456487674839629818390934941973262879616797970608917283679875499331574161113854088813275488110588247193077582527278437906504015680623423550067240042466665654232383502922215493623289472138866445818789127946123407807725702626644091036502372545139713 in a useful amount of time?

share|improve this question

migrated from Oct 6 at 17:25

This question came from our site for information security professionals.

What research have you done? This is covered in textbooks and courses on cryptography. We expect you to do a significant amount of research before asking, and to show it in the question. See "Have you thoroughly searched for an answer before asking your question? Sharing your research helps everyone. Tell us what you found and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and above all, it helps you get a more specific and relevant answer!" – D.W. Oct 5 at 18:50
See also – D.W. Oct 5 at 18:52
Here's a related problem: compute the "ones" decimal digit of eleven raised to the ten billionth power. If you compute eleven to the first, second, third and fourth powers it should become rapidly pretty clear that you do not need to perform ten billion multiplications to answer that question. Now do you see why the computations in RSA are feasible? – Eric Lippert Oct 5 at 22:53
I'm voting to close this question as off-topic because it should be migrated to Cryptography SE. – RoraΖ Oct 6 at 11:38
@RoraΖ Gosh, sorry, I didn't realise such a stack existed! – Luke Oct 6 at 11:45

2 Answers 2

up vote 32 down vote accepted

Surprisingly, very basic algorithms which the children learn at the basic schools are used. For instance:

You can find a similar algorithm for sum, sub and division. Try to ask google for: "division on paper"

The "power of" is little tricky. In cryptography you don't really need the "real power of". Instead you need:

(a ^ b) mod c

It is easy to compute a^(power of 2) mod c

a * a mod c= a^2 mod c
(a^2)^2 mod c= a^4 mod c
(a^4)^2 mod c= a^8 mod c
(a^512)^2 mod c= a^1024  mod c

And if you need a^5

(a^5) = a^2 * a^2 * a

thanks to "mod c" you keep the numbers no higher than c.

For example:

c = 10

2^2 = 4
2^4 mod 10 = (4^2) mod 10 = 16 mod 10 = 6
2^8 mod 10 = ((4^2)^2) mod 10 = (6^2) mod 10 = 36 mod 10 = 6
2^16 mod 10 = (6^2) mod 10 =....


There are many tricks how to make the calculation faster. For example, Montgomery multiplication algorithm is often used for that. But even without those tricks the implementation would be fast enough. I would estimate RSA instead of 0.2s would take 5s or so.

share|improve this answer
0.2s vs 5s!? You are vastly underestimating how fast computers do math. The difference is closer to 0.1ms vs 1ms – BlueRaja - Danny Pflughoeft Oct 5 at 16:26
yah, I forgot on 486 cpu :-) – smrt28 Oct 5 at 16:43
Note: If you don't do the repeated square and multiply trick you'll likely never witness the finish of your RSA signing operation... – SEJPM Oct 5 at 21:02
486 was similarly bloomin' fast. – Lightness Races in Orbit Oct 5 at 23:55
Just note the comment about Montgomery was written by someone else. Not sure how this is possible, but it seems some people with really high reputation can modify posts of someone else. Would be nice if they remark that explicitly. – smrt28 Oct 8 at 7:34

There are two reasons by which such "huge" numbers can be computed in reasonable time.

The first one is that we do not raise one integer x to some big exponent d. What we do is that we compute x raised to power d modulo an integer n. The modulo means that we are not interested in the final integer xd but only in the remainder of the Euclidian division of xd by n. The good part here is that all involved numbers will reside between 0 and n-1; thus, they will fit in a few thousands of bits, instead of becoming (much) larger than the entire Universe.

The second reason is that the exponentiation is done through the square-and-multiply algorithm. As an example, to compute x100 (modulo n), we do not do 99 multiplications by x; instead, we compute:

  • x2
  • (x2)2 = x4
  • (x4)2 = x8
  • (x8)2 = x16
  • (x16)2 = x32
  • (x32)2 = x64
  • x64x32x4 = x64+32+4 = x100

Thus a grand total of 6 squarings and 2 multiplications, i.e. way fewer than the 99 multiplications of the naive algorithm. In all generality, if the exponent fist on k bits (the exponent value lies between 2k-1 and 2k), then the square-and-multiply algorithm will need k-1 squarings and at most k-1 multiplications (possibly much less than that with "window" optimizations).

If you want full details on such things, have a look at the Handbook of Applied Cryptography, especially chapter 14.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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