English subtitles

← Modular Exponentiation Quiz Solution - Applied Cryptography

Get Embed Code
1 Language


Showing Revision 2 created 05/25/2016 by Udacity Robot.

  1. So to do this we're taking advantage of the property that A to the 2B
  2. is equal to A to the B squared.
  3. So let's first define a procedure to do squaring,
  4. and then we'll define our modular exponentiation procedure.
  5. And the easiest way to do this is to do it recursively.
  6. So our base case is when B is zero.
  7. Anything raised to the zero power is defined as having the value of 1.
  8. If B is not zero, well then we want to check if it is divisible by 2.
  9. If it is divisible by 2 we can do this transformation.
  10. Then the result is the square of the modular exponentiation of A to the B divided by 2.
  11. If B is not divisible by 2, well then it's of the form 2N plus 1 for some N.
  12. So if we break off the 1, we will end up with something divisible by 2.
  13. So that means we can return the result of multiplying A
  14. times the result of modular exponentiation A raised to the B minus 1 power.
  15. Now this is just fast exponentiation.
  16. We haven't yet taken the modulo out.
  17. If we didn't care how big numbers got,
  18. we could do that all at the end.
  19. But we want to do that as we go.
  20. We're going to add the mod operator to do these modulo Q.
  21. And that will give us the result of raising A to the B power modulo Q
  22. using a number of multiplications that's close to the log of the value of B.