How Can I Generate Two 1024 Bit Prime Numbers Using the AKS Primality Test?

[Anzas]

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?

 

[Hurkyl]

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.

 

[Gokul43201]

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

 

[Hurkyl]

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

 

[chroot]

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

 

[Gokul43201]

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 ?

 

[shmoe]

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.

 

[Anzas]

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)

 

[TenaliRaman]

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

 

[Anzas]

well I am 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

 

[Gokul43201]

Anzas, you can download pgp for free.

 

[Anzas]

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

 

[shmoe]

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.