Efficient (HUGE) prime modulus

Tim Roberts timr at probo.com
Tue Nov 20 08:13:27 CET 2007

blaine <frikker at gmail.com> wrote:
>  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

And it won't.  Ever.  Well, actually, it will finish when it crashes.

>    G =
>    P =
>    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.

We all know the proper answer (use 3-arg math.pow).  However, Paul Rubin's
suggested to figure out how large (G ** a) prompted me to go do just that.
That expression is not computable on any computer on Earth today.  It is a
number requiring 7 x 10**156 bits.  Consider that a terabyte hard disk
today only includes 9 x 10**12 bits.  Also consider that, by rough
estimate, there are approximately 10**80 atoms in the known universe
Tim Roberts, timr at probo.com
Providenza & Boekelheide, Inc.

More information about the Python-list mailing list