Modular Exponentiation for high numbers in C++

by

Exponentiation by squaring still “works” for modulo exponentiation. Your problem isn’t that 2 ^ 168277 is an exceptionally large number, it’s that one of your intermediate results is a fairly large number (bigger than 2^32), because 673109 is bigger than 2^16.

So I think the following will do. It’s possible I’ve missed a detail, but the basic idea works, and this is how “real” crypto code might do large mod-exponentiation (although not with 32 and 64 bit numbers, rather with bignums that never have to get bigger than 2 * log (modulus)):

  • Start with exponentiation by squaring, as you have.
  • Perform the actual squaring in a 64-bit unsigned integer.
  • Reduce modulo 673109 at each step to get back within the 32-bit range, as you do.

Obviously that’s a bit awkward if your C++ implementation doesn’t have a 64 bit integer, although you can always fake one.

There’s an example on slide 22 here: http://www.cs.princeton.edu/courses/archive/spr05/cos126/lectures/22.pdf, although it uses very small numbers (less than 2^16), so it may not illustrate anything you don’t already know.

Your other example, 4000111222 ^ 3 % 1608 would work in your current code if you just reduce 4000111222 modulo 1608 before you start. 1608 is small enough that you can safely multiply any two mod-1608 numbers in a 32 bit int.

More Related Contents:

  1. How do I detect unsigned integer overflow?
  2. Why do people say there is modulo bias when using a random number generator?
  3. Why is unsigned integer overflow defined behavior but signed integer overflow isn’t?
  4. Is signed integer overflow still undefined behavior in C++?
  5. Detecting signed overflow in C/C++
  6. Can’t use modulus on doubles?
  7. (-2147483648> 0) returns true in C++?
  8. Can’t Mod Zero?
  9. How to code a modulo (%) operator in C/C++/Obj-C that handles negative numbers
  10. Why does C++ output negative numbers when using modulo?
  11. Why does long long n = 2000*2000*2000*2000; overflow?
  12. Efficient unsigned-to-signed cast avoiding implementation-defined behavior
  13. Addition of two chars produces int
  14. Overflowing of Unsigned Int
  15. C++ integer overflow
  16. Allowing signed integer overflows in C/C++
  17. How to handle arbitrarily large integers
  18. Is there any alternative to using % (modulus) in C/C++?
  19. Program behaving strangely on online IDEs
  20. Checking for underflow/overflow in C++?
  21. I want to generate the nth term of the sequence 1,3,8,22,60 ,164 in Order(1) or order of (nlogn)
  22. Calculate a*a mod n without overflow
  23. How disastrous is integer overflow in C++?
  24. Using an iterator to Divide an Array into Parts with Unequal Size
  25. If a 32-bit integer overflows, can we use a 40-bit structure instead of a 64-bit long one?
  26. Is there some meaningful statistical data to justify keeping signed integer arithmetic overflow undefined?
  27. Fast division/mod by 10ˣ
  28. C++ operator % guarantees
  29. C++ Erase vector element by value rather than by position? [duplicate]
  30. Why is modifying a string through a retrieved pointer to its data not allowed?

Leave a Comment