473,230 Members | 1,521 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,230 software developers and data experts.

Efficient (HUGE) prime modulus

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(233393864576615061551125594316969409746929453 87305773304703652307481857291600972892003907384243 46682521059501689463393405180773510126708477896062 227281603)
P =
long(789738360153468172470088613576628733387936700 72369947923801519511850325509149835061484000988060 10880449684316518296830583436041101740143835597057 941064647)

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. If I make little a only 16
bits instead of 512, it takes about 12 seconds on my machine to
compute. Is this incorrect usage of **? I used math.pow and built-in
pow. The math.pow complained about converting a long to a float. The
built in pow() took a very long time as well.

The following Java code gives me a result in 2 seconds or so.

import java.math.*;

class cruncher {
// Simple class for crunching a secret key!
public static void main(String[] args) {
BigInteger p, g, a, B, out;
out = null;
a = new BigInteger(args[1]);

// To make sure the compiler doesn't complain:
if (a == null) {
System.out.println("You must specify little a");
System.exit(1);
}
g = new
BigInteger("23339386457661506155112559431696940974 69294538730577330470365230748185729160097289200390 73842434668252105950168946339340518077351012670847 7896062227281603");
p = new
BigInteger("78973836015346817247008861357662873338 79367007236994792380151951185032550914983506148400 09880601088044968431651829683058343604110174014383 5597057941064647");

// We now have a, g, and p. Now, depending on what pass we are on,
// we will compute the appropriate output
System.out.println("Generating Secret Key(A)");
out = g.modPow(a, p);

System.out.println(out);
}
}

Any suggestions? Right now my solution is to just pipe the output from
my java program since I only need to crunch the numbers one time. Is
there a python implementation of java's Modpow?

thanks,
Blaine
University of Cincinnati
Nov 19 '07 #1
8 4250
blaine <fr*****@gmail.comwrites:
A = (G ** a) % P # G^a mod P
Think of how large the intermediate result G**a will be. That should
explain why it's taking so long. So figure out what Java's modPow
function must be doing, and write something similar. Or, see the
docs for python's built-in pow function.
Nov 19 '07 #2
On Nov 19, 2007 10:32 AM, blaine <fr*****@gmail.comwrote:
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?
Python is quite slow for pure number crunching. Most people use the
numeric/numpy modules and/or psyco to speed up math.

Python + psyco approaches Java for the simple integer operations I've tested.
Nov 19 '07 #3
blaine wrote:
A = (G ** a) % P # G^a mod P

###### END #####
The above code takes a very long time. If I make little a only 16 bits
instead of 512, it takes about 12 seconds on my machine to compute. Is
this incorrect usage of **? I used math.pow and built-in pow. The
math.pow complained about converting a long to a float. The built in
pow() took a very long time as well.
Even in its three-argument form?

"""
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).
"""

Peter
Nov 19 '07 #4
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(233393864576615061551125594316969409746929453 87305773304703652307481857291600972892003907384243 46682521059501689463393405180773510126708477896062 227281603)
P =
long(789738360153468172470088613576628733387936700 72369947923801519511850325509149835061484000988060 10880449684316518296830583436041101740143835597057 941064647)

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 =
23339386457661506155112559431696940974692945387305 77330470365230748185729160097289200390738424346682 52105950168946339340518077351012670847789606222728 1603
>>P
=7897383601534681724700886135766287333879367007236 99479238015195118503255091498350614840009880601088 04496843165182968305834360411017401438355970579410 64647
>>import random
a = random.getrandbits(512)
pow(G, a, P)
32779593927115948792218359274606928218234929455396 27585936047598704303395627109292402670858323756252 13089904773353220710094412059911879608391277133993 0412L

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
Nov 19 '07 #5
On Nov 19, 10:32 am, blaine <frik...@gmail.comwrote:
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?
Did you try the 3-argument version of the built-in pow?

A = pow(G,a,P)
Takes about .1 second on my machine, with your values. (I didn't
verify that the answer I got was correct, though.)

-- Paul
Nov 19 '07 #6
For the interested, the algorithm that is most likely being used is
http://en.wikipedia.org/wiki/Exponentiation_by_squaring

If you scroll down, there is a ruby implementation. Combine this with
a little bit of http://en.wikipedia.org/wiki/Modular_arithmetic and I
wrote a small python function that does what the built-in is probably
doing.

G =
long(233393864576615061551125594316969409746929453 87305773304703652307481857291600972892003907384243 46682521059501689463393405180773510126708477896062 227281603)
P =
long(789738360153468172470088613576628733387936700 72369947923801519511850325509149835061484000988060 10880449684316518296830583436041101740143835597057 941064647)

import random
a = random.getrandbits(512)
#A = (G ** a) % P # G^a mod P
print pow(G, a, P)
def testpower(x, n, P):
result = 1
while n:
if n % 2:
result = (result * x) % P
n = n - 1
x = (x * x) % P
n = n / 2
return result
print testpower(G, a, P)
-Justin
Nov 20 '07 #7
blaine <fr*****@gmail.comwrote:
>
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)
And it won't. Ever. Well, actually, it will finish when it crashes.
>...
G =
long(23339386457661506155112559431696940974692945 38730577330470365230748185729160097289200390738424 34668252105950168946339340518077351012670847789606 2227281603)
P =
long(78973836015346817247008861357662873338793670 07236994792380151951185032550914983506148400098806 01088044968431651829683058343604110174014383559705 7941064647)

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
today...
--
Tim Roberts, ti**@probo.com
Providenza & Boekelheide, Inc.
Nov 20 '07 #8
blaine <fr*****@gmail.comwrites:
As an alternative I
can use Java - but I'd rather have a pure python implementation.
A number of people have suggested using 3-argument pow, but if this is
supposed to be a learning exercise, I think it's worth figuring out
for yourself how 3-argument pow is implemented in terms of ordinary
arithmetic. I'll leave it as a hint: the simplest approach is
probably recursive.
Nov 20 '07 #9

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

36
by: Dag | last post by:
Is there a python module that includes functions for working with prime numbers? I mainly need A function that returns the Nth prime number and that returns how many prime numbers are less than N,...
3
by: ckroom | last post by:
Anyone knows a good algorithm to get the next prime of a number n? prime = nextprime( n ); It's for some stuff about double rehashing, thanks. -- ckroom http://nazaries.net/~ckroom
4
by: t | last post by:
Hello, I am going to write a program to search for prime numbers. There will be a lot of clients participating in this searching so I have to operate on very huge numbers, bigger than can be...
7
by: Freyr | last post by:
Hello, I'm taking an independant course in C++, and one of my questions asks to use the following algorithm to deturmine the factors of any given number: -- Initialize a counter at 2 So Long...
20
by: Tuvas | last post by:
I have made and recently posted a libary I made to do Modular Arithmetic and Prime numbers on my website at http://www.geocities.com/brp13/Python/index.html . I am currently in a crypotology...
10
by: jantod | last post by:
I think there might be something wrong with the implementation of modulus. Negative float values close to 0.0 break the identity "0 <= abs(a % b) < abs(b)". print 0.0 % 2.0 # => 0.0 print...
15
by: Oswald Kluge | last post by:
Dear Reader, I'm trying to implement the following short algorithm: Given a number n, remove all the multiples of n from the list of non-negative numbers from 1 through a limit k. My...
25
by: johnmsimon | last post by:
i need to develop a code that finds a prime right number between 2 and 100000. and print one line of text that indicates if the int. is right prime. i am in beginning programing so complex is...
10
by: Joel Mayes | last post by:
Hi All; I'm teaching myself C, and have written a prime number generator. It is a pretty inefficient implementation of the Sieve of Eratosthenes to calculate primes up to 1,000,000. If anyone...
0
by: VivesProcSPL | last post by:
Obviously, one of the original purposes of SQL is to make data query processing easy. The language uses many English-like terms and syntax in an effort to make it easy to learn, particularly for...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: fareedcanada | last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
So, I have written a code for a cmd called "Send WhatsApp Message" to open and send WhatsApp messaage. The code is given below. Dim IE As Object Set IE =...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.