Square & Multiply Algorithm - Computerphile

How do you compute a massive number raised to the power of another huge number, modulo something else? Dr Mike Pound explains the super-quick square & multiply algorithm.


This video was filmed and edited by Sean Riley.

[pleasedontwatchthese]

For the people who have worked with assembly programming they will be really use to these. In the past CPUs did not have multiply and you often had a table of the fastest way to multiply a numbers. Which you guessed it was shifts (which is like a square) and addition

[GeorgeBratley]

I think the last bit of the video is facinating - that you could perform an attack to work out a key based on the CPU time to calculate a square vs a square & multipy. A great example of the theoretical mathematics being ideal vs. the real world implementation being fundamentally vulnerable.

[thuokagiri]

Dr Pounds breadth and depth of knowledge in computer science never cease to amaze me!!
"Man from the future"

[davidgillies]

Note that for RSA and similar, the modular multiplication operation itself can be quite expensive, so modern implementations typically convert the numbers involved to an intermediate representation, called a Montgomery form, after Peter Montgomery. The binary exponentiation method can use Montgomery forms throughout, so only at the end is the result converted back to a conventional representation. Montgomery multiplication is also resistant to the side channel attacks mentioned at the end of the video.

[todayonthebench]

Interesting algorithm.
At first I thought it were just going to be a simple, "first we build our list of binary equivalents and then just multiply them all together in the end."
As an example, calculate 3^1, 3^2, 3^4, 3^8, 3^16, etc. And then choose the values our exponent actually contains.
Then the slight of hands of mathematicians came in at 9:40 and made things far far simpler and much easier to execute in practice.

[Alex_Deam]

9:34 It's actually not the minimum number of operations. For example, to make 31 by this method takes 8 operations (SMSMSMSM), whereas the minimum is only 7 operations (N^2, N*(N^2), (N^3)^2, (N^6)^2, (N^12)^2, (N^6)*(N^24), N*(N^30)). However, in general finding the minimum number for a given exponent is NP-complete, so in practice square and multiply is presumably what you'd do. Otherwise, great video!

[SRISWA]

This is also known as "Fast Binary Exponentiation", which calculates pow(a, b, mod) in logarithmic time.

[ezg]

I read binary numbers left to right by starting at 1, doubling for each bit, and adding 1 if the bit was a 1. Very cool to see this pattern coming up in exponents

[LeDabe]

Also called russian peasant multiplication. It works for any power operation tbh, not only scalar multiplication. The power operator on matrix can for instance be used to compute large fibonacci numbers very quickly using the matrix 2x2 [1, 1, 1, 0]

[longlostwraith]

I always liked calculating that recursively. For example, 2^6 is (2^3)*(2^3), 2^3 is (2^2)*(2^1) and 2^2 is (2^1)*(2^1).

It's extremely simple to code it too. Here's the algorithm that performs the calculation:
1) If exponent is zero, return 1
2) Divide exponent by two, and save both the quotient and the remainder
3) Call algorithm recursively with (exponent = quotient) and save the result
4) If remainder is zero, return result*result
5) If remainder is one, return result*result*base

[hazemessawi]

I love how entertaining the video is given that I already know what the answer is and have used this quite a lot

[japedr]

This is also called "exponentiation by squaring" and it's super useful in many cases.
One quick example is in computing the nth Fibonacci number using the 2x2 matrix formula, where one raises a matrix to the nth power. But using this method, the number of multiplications is greatly reduced. There is also a closed form expression using a power of the golden ratio but that requires a lot of numerical precision for large n.

[jkye_]

I am currently purchasing master degree in cybersecurity and this guy summerize a 2h of lectures in literally 17min ;)

[karanjotsinghbagga]

i cant believe how brilliant this explanation actually was!!Kudoss

[tsjbb]

This was fascinating, so simple and intuitive once explained but so powerful

[conradludgate]

I did the 3^45 mod 7 in my head fairly simply. 3 and 7 are coprime, so you know that 3 will cycle through all 7 numbers. Then we can do 3^42 * 3^3 mod 7, which is just 1*3^3 or 27 mod 7 which is 6. Still a very useful algorithm though

[meispi]

I remember using this algorithm for a competitive programming question on one of the codechef's monthly contests, didn't know it had a name.

[NotAnAviator]

This video was a lovely reminder of my time spent with number theorists in college, cryptography is so damn fascinating

[eggsquishit]

You can do multiplication this way, too (by doubling & adding). Very useful on CPUs that can only do addition.

[franziscoschmidt]

Saw an implementation of this in a programming tutorial video but they just rushed over the details. Computerphile does a wonderful job at filling this gap (as always I might add!)