2

I have a question, how does 

pow(num, power, mod)

work so much faster than 

(num**power)%mod

On large numbers the second is unusable, so i'm wondering how pow() works. How does it work to be so much faster, what is the underpinning of how it works with mod to calculate an answer so much faster than

(num**power)%mod.

(num * * power)%mod is unusable with larger numbers

so i'm wondering what trick pow() uses to calculate the answer so quickly? Does it mod first, then power? Hopefully somebody can help me understand how this works.

import time

shared_Prime = 1031267
base_prime = 111029

secret_num = 103123


start = time.time()
A = (secret_num**base_prime) % shared_Prime
end = time.time()
print(end - start)
0.1082313060760498

start = time.time()
B = pow(secret_num, base_prime, shared_Prime)
end = time.time()
print(end - start)
8.916854858398438e-05

A==B
True
AMC
  • 2,642
  • 7
  • 13
  • 35
oppressionslayer
  • 6,942
  • 2
  • 7
  • 24
  • 4
    You don't have to take the mod only at the end, you can apply it at every step of the computation thus always working with small numbers. – Julien Nov 13 '19 at 23:14
  • @Julien if you fleshed that out a bit, that could be an answer. – mypetlion Nov 13 '19 at 23:16
  • 1
    yes, i would definitely give you a checkmark for an answer, i think i know where your going with this. I'm actually trying to work through this now, but kinda stuck, what number do you use at each step? – oppressionslayer Nov 13 '19 at 23:20
  • 1
    Also see https://en.wikipedia.org/wiki/Modular_exponentiation – tevemadar Nov 13 '19 at 23:30
  • 1
    You should be able to get an understanding of this by doing some examples by hand and working out the algorithm complexity. – President James K. Polk Nov 14 '19 at 00:15
  • math on small numbers is `O(1)` but on big ones is not ... even simple addition is `O(n)` and multiplication is between `O(3*n^1.58)` and `O(n^2)` or even less for more advanced stuff on really big numbers. so if you take modulo each multiplication step (`modmul`) then you limit the numbers to your modulo staying small ... making the `modpow` much much faster – Spektre Nov 14 '19 at 08:40

1 Answers1

6

You can experience this as a human being. Suppose you want to answer the following question:

What is the last digit in a decimal representation of 3100?

To answer this, you can calculate 3100 while tracking only the last digit:

3^5 = 243 = 3 mod 10
3^25 = (3^5)^5 = 3 mod 10
3^50 = (3^25)^2 = 9 mod 10
3^100 = (3^50)^2 = 1 mod 10

So the last digit is 1. Now imagine calculating all digits of 3100, just to throw them all away, except for the last one... Too tedious to be practical.

The considerations above hold also for calculation in python.

anatolyg
  • 26,506
  • 9
  • 60
  • 134