Is there anyway to make this code to run faster

Question

Is there any way to make this code run faster?

g = 53710316114328094
a = 995443176435632644
n = 926093738455418579
print(g**a%n)

It is running for too long I want to make it faster
I also tried:

import math
g = 53710316114328094
a = 995443176435632644
n = 926093738455418579

print(math.pow(g**a)%n)

and

g = 53710316114328094
a = 995443176435632644
n = 926093738455418579

def power(a,b):
    ans = 1
    for i in range(b):
        ans *= a
    return ans
print(power(g,a)%n)

All of these code is running for very long

This is to be expected and there isn't a magic solution. See https://stackoverflow.com/questions/66111479/how-to-calculate-very-long-numbers-in-python for some options. — kgiannakakis, Oct 28 '21 at 07:44
@luigigi the math.pow(g**a) is a typo, and yes, g**a is a very big number but i just want the code to be faster — Mortis_666, Oct 28 '21 at 07:52
You could take a look at: https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method. There exists fast algorithms to compute modular exponentiation. — areobe, Oct 28 '21 at 07:55
Python *already* supports power-modulo. ``pow(g, a, n)`` takes about 10 - 20 µs. — MisterMiyagi, Oct 28 '21 at 08:20

Alexey S. Larionov · Accepted Answer · 2021-10-28T08:13:47.273

First of all you need to know about Binary exponentiation algorithm. The idea is that instead of computing e.g. 5^46 like 5*5*5*5... 46 times, you can do

5^46 == 5^2 * 5^4 * 5^8 * 5^32

The key here, is that you can compute 5^2 fast from 5 (just square it), then 5^4 fast from 5^2 (just square it), then 5^8 from 5^4 (just square it) and so on. To determine which 5^K numbers you should multiply and which not, you can represent the power as a binary number, and multiply to the final result only those components, that correspond to 1 in this binary representation. E.g.

decimal 46 == binary 101110

Thus 5^1 is skipped (corresponds to right most 0), 5^2 is multiplied (corresponds to right most 1), 5^4 is multiplied(second from the right 1), 5^8 is multiplied (third from the right 1), 5^16 is skipped (the left most 0) and 5^32 is multiplied (the left most 1).

Next, you need to compute a very huge power, it's impractically big. But there is a shortcut, since you use modulo operation.

You see, there's a rule that

(a*b % n) == ( (a % n)*(b % n) ) % n

So these should be equivalent

5^46 % n == ( ( ( (5^2 % n) * (5^4 % n) % n) * (5^8 % n) % n) * (5^32 % n) % n)

Notice that each number we multiply won't ever exceed n, so the overall multiplication chain will not take forever, as n is big, but not even remotely as gigantic as g**a

In the code, all of that looks like that. It computes instantly

def pow_modulo_n(base, power, n):
    result = 1
    multiplier = base
        
    while power > 0:
        power, binary_digit = divmod(power, 2)
        if binary_digit == 1:
            result = (result * multiplier) % n
        
        multiplier = (multiplier**2) % n        
    return result % n

g = 53710316114328094
a = 995443176435632644
n = 926093738455418579

print(pow_modulo_n(g, a, n))

This prints

434839845697636246

Might be worth mentioning that modular exponentiation is also provided as a python built-in, with `(g^a) % n = pow(g, a, n)` — Seon, Oct 28 '21 at 08:20
Heads up that this is about 4 times slower than the builtin ``pow``. — MisterMiyagi, Oct 28 '21 at 08:22

Is there anyway to make this code to run faster

1 Answers1