Efficient (HUGE) prime modulus

[Justin Kwok]

For the interested, the algorithm that is most likely being used is
http://en.wikipedia.org/wiki/Exponentiation_by_squaring

If you scroll down, there is a ruby implementation. Combine this with
a little bit of http://en.wikipedia.org/wiki/Modular_arithmetic and I
wrote a small python function that does what the built-in is probably
doing.

G =
long(2333938645766150615511255943169694097469294538730577330470365230748185729160097289200390738424346682521059501689463393405180773510126708477896062227281603)
P =
long(7897383601534681724700886135766287333879367007236994792380151951185032550914983506148400098806010880449684316518296830583436041101740143835597057941064647)

import random
a = random.getrandbits(512)
#A = (G ** a) % P # G^a mod P
print pow(G, a, P)
def testpower(x, n, P):
    result = 1
    while n:
        if n % 2:
            result = (result * x) % P
            n = n - 1
        x = (x * x) % P
        n = n / 2
    return result
print testpower(G, a, P)


-Justin