Generating prime numbers

  • Thread starter Anzas
  • Start date
  • #1
87
0
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?
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
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. :smile:
 
  • #3
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,082
20
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
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
I don't think you grasp just how many 1024 bit primes there are!
 
  • #5
chroot
Staff Emeritus
Science Advisor
Gold Member
10,239
39
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
 
Last edited:
  • #6
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,082
20
Hurkyl said:
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 ?
 
Last edited:
  • #7
shmoe
Science Advisor
Homework Helper
1,992
1
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.
 
  • #8
87
0
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
644
1
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
87
0
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
 
  • #11
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,082
20
Anzas, you can download pgp for free.
 
  • #12
87
0
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
shmoe
Science Advisor
Homework Helper
1,992
1
TenaliRaman said:
or try AKS primality test (dunno of any software using this one yet so u could be the first :D)

several implementations:
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.
 

Related Threads on Generating prime numbers

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
24
Views
6K
  • Last Post
2
Replies
44
Views
11K
  • Last Post
2
Replies
28
Views
7K
  • Last Post
Replies
11
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
10
Views
3K
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
4
Views
4K
  • Last Post
Replies
3
Views
2K
Top