# Efficient (HUGE) prime modulus

Steven Bethard steven.bethard at gmail.com
Mon Nov 19 18:16:09 CET 2007

```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

```