Efficient (HUGE) prime modulus
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