1

How exactly does the pow built-in function in python work? Specifically, how does it compute (a^b)%c. What is the algorithm?

>>>pow(134562,12345,15)
12

whereas the naive,

>>>(134562**12345)%15

isn't able to yield anything even after a significant amount of time. What optimisation is performed that leads to the massive speed up?

Guy
  • 604
  • 5
  • 21
  • Probably one of the techniques listed on [this page](http://en.wikipedia.org/wiki/Modular_exponentiation) – Kevin Feb 26 '14 at 16:00
  • @Kevin thanks for the link. Is there anyway I can view the source code for python's implementation? I mean yeah it's open source so there is, but where can I find it? – Guy Feb 26 '14 at 16:02
  • 1
    @Sabyasachi Somewhere on http://hg.python.org/cpython/ (make sure to pick the relevant branch). –  Feb 26 '14 at 16:03

0 Answers0