Sep 6

[Python,Algorithms] Fast Modular exponentiation script

Algorithms, Python algorithm, code, exponentiation, Python

If we want to know the last ten digits of number aⁿ – we have to evaluate expression aⁿ mod 10¹⁰. Using brute force approach, we have to do O(n) ( If you don’t understand big „O” notation, visit: Big O notation – it’s VERY important) multiplications and modulo divisions. When n is greater than 10⁹, it will take a lot of time. Fortunately, we can use more „mathematical” approach, which has O(log n) complexity. Read More