# generating prime numbers

by Anzas
Tags: generating, numbers, prime
 P: 87 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?
 PF Patron Sci Advisor Emeritus P: 16,094 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.
 PF Patron Sci Advisor Emeritus P: 11,137 Well, if you have giant capacity but only normal speed, you could just look up a database which is sitting on your hard drive ?
PF Patron
Emeritus
P: 16,094

## generating prime numbers

I don't think you grasp just how many 1024 bit primes there are!
 PF Patron Sci Advisor Emeritus P: 10,400 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
PF Patron
Emeritus
P: 11,137
 Quote by Hurkyl I don't think you grasp just how many 1024 bit primes there are!
I didn't really think very much about this and - that's why people don't do this, I guess - that's why I punctuated that line with a question mark instead of a period.

I imagine there would be about 2^1014 primes less than 2^1024 ?
 HW Helper Sci Advisor P: 1,996 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 Rabin-Miller 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 Rabin-Miller, 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.
 P: 87 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)
 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
 P: 87 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