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
--
http://mail.python.org/mailman/listinfo/python-list
