Efficient (HUGE) prime modulus

[Steven Bethard]

blaine wrote:
> Hey guys,
>   For my Network Security class we are designing a project that will,
> among other things, implement a Diffie Hellman secret key exchange.
> The rest of the class is doing Java, while myself and a classmate are
> using Python (as proof of concept).  I am having problems though with
> crunching huge numbers required for calculations.  As an alternative I
> can use Java - but I'd rather have a pure python implementation.  The
> problem is that Python takes a very long time (I haven't had it finish
> yet) - but Java does it in 3 seconds.  Suggestions?
> 
> 
> P and G are given to us. P represents a huge prime, G is the base, a
> is my secret (random) long integer.  I want to compute: (G^A)%P
> Python Code:
>     G =
> long(2333938645766150615511255943169694097469294538730577330470365230748185729160097289200390738424346682521059501689463393405180773510126708477896062227281603)
>     P =
> long(7897383601534681724700886135766287333879367007236994792380151951185032550914983506148400098806010880449684316518296830583436041101740143835597057941064647)
> 
>     a = self.rand_long(1) # 512 bit long integer
> 
>     A = (G ** a) % P # G^a mod P
> 
> ###### END #####
> The above code takes a very long time.

This executed almost instantaneously for me::

 >>> G = 
2333938645766150615511255943169694097469294538730577330470365230748185729160097289200390738424346682521059501689463393405180773510126708477896062227281603
 >>> P 
=7897383601534681724700886135766287333879367007236994792380151951185032550914983506148400098806010880449684316518296830583436041101740143835597057941064647
 >>> import random
 >>> a = random.getrandbits(512)
 >>> pow(G, a, P)
3277959392711594879221835927460692821823492945539627585936047598704303395627109292402670858323756252130899047733532207100944120599118796083912771339930412L

Did I run your algorithm wrong? Note the three argument form of pow::

 >>> help(pow)
Help on built-in function pow in module __builtin__:

pow(...)
     pow(x, y[, z]) -> number

     With two arguments, equivalent to x**y.  With three arguments,
     equivalent to (x**y) % z, but may be more efficient (e.g. for
     longs).

STeVe