Register to reply 
Generating prime numbers 
Share this thread: 
#1
Aug1304, 08:07 PM

P: 88

im making an algorithm in which i need to generate two 1024 bit prime numbers, is there a way of doing this? i read that there are some ways to see how probable it is that a number is prime, can you guys point me in the right direction?



#2
Aug1304, 08:24 PM

Emeritus
Sci Advisor
PF Gold
P: 16,092

I would do a google search on the keywords prime (or primality) + test (or testing). Looking for a mathworld or wikipedia page on it is probably good.
There is a really good primality testing algorithm, but I don't know its name. I think Rabin's test is a good one, but don't quote me on that. 


#3
Aug1304, 09:01 PM

Emeritus
Sci Advisor
PF Gold
P: 11,155

Well, if you have giant capacity but only normal speed, you could just look up a database which is sitting on your hard drive ?



#4
Aug1304, 09:16 PM

Emeritus
Sci Advisor
PF Gold
P: 16,092

Generating prime numbers
I don't think you grasp just how many 1024 bit primes there are!



#5
Aug1304, 09:23 PM

Emeritus
Sci Advisor
PF Gold
P: 10,428

Can't you just download the PGP source (http://www.pgpi.org/) and see which algorithm it uses to get its prime numbers? I can't remember off the top of my head and am about to run to the beach. Be back later.
 Warren 


#6
Aug1404, 09:12 AM

Emeritus
Sci Advisor
PF Gold
P: 11,155

I imagine there would be about 2^1014 primes less than 2^1024 ? 


#7
Aug1404, 10:11 AM

Sci Advisor
HW Helper
P: 1,995

2^1014 is about the right order of magnitude.
You expect the probability a randomly chosen number near 2^1024 is prime is something like 1/1000. The RabinMiller test is usefull, and can tell you a given number is prime with whatever probability you like (the closer you take this probability to 1 the more sure you are it's prime, and also the longer the algorithm takes). Once your number has passed RabinMiller, you can send it into the Elliptic Curve Primality Proving algorithm (ECPP) which can certify that your number is prime (or determine it's composite). This takes longer than a probabilistic test, but if you want guaranteed security, it's the way to go. You should be able to find many versions of both these algorithms (and many others) online. 


#8
Aug1404, 10:49 AM

P: 88

i think i found a way to find probable primes using Fermat's Little Theorem...
if i want to check the number "n" for primality i pick a number "a" such that a < n and if a = a^n mod n is true then n might be prime (i need to try sevral "a" values to have higher probability) 


#9
Aug1404, 12:55 PM

P: 646

fermat's little theorem fails for some numbers (these are called pseudo primes but they hold no interest to whatever u are doing).
One could go with shmoe's suggestion or try AKS primality test (dunno of any software using this one yet so u could be the first :D) Check this page for a lot more interesting stuffs http://www.utm.edu/research/primes/prove/index.html  AI 


#10
Aug1404, 06:23 PM

P: 88

well im trying to implement the rsa encryption algorithm so i think pseudo primes should do as well even though they won't work with some values most chances it will work fine



#12
Aug1504, 05:59 AM

P: 88

well pgp is written in c and im programming in visual basic
porting it would actually be more work then writing it from scratch 


#13
Aug1504, 12:30 PM

Sci Advisor
HW Helper
P: 1,995

http://fatphil.org/maths/AKS/#Implementations There have been many improvements to the algortihm since AKS first appeared, but I don't think any of them are faster than the best implementations of ECPP for practical purposes. 


Register to reply 
Related Discussions  
A prime number which equals prime numbers  General Math  10  
Exponential generating function of FussCatalan numbers  Set Theory, Logic, Probability, Statistics  0  
Lucas Numbers and Generating Functions  Calculus & Beyond Homework  4  
A formula of prime numbers for interval (q; (q+1)^2), where q is prime number.  Linear & Abstract Algebra  0  
Prime Numbers in the Diophantine equation q=(n^2+1)/p and p is Prime  Linear & Abstract Algebra  5 