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

In summary, the conversation discusses the need for generating two 1024 bit prime numbers and possible ways to do so. Some suggestions include doing a Google search for primality testing algorithms and looking up a database on the hard drive. The Rabin-Miller test and Elliptic Curve Primality Proving algorithm are mentioned as potential methods. Fermat's Little Theorem and AKS primality test are also discussed as potential options for finding probable primes. The conversation also touches on using PGP for prime number generation and the possibility of porting it to a different programming language.
  • #1
Anzas
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?
 
Physics news on Phys.org
  • #2
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
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
I don't think you grasp just how many 1024 bit primes there are!
 
  • #5
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
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
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
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
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
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
 
  • #11
Anzas, you can download pgp for free.
 
  • #12
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
 
  • #13
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.
 

1. What exactly are prime numbers?

Prime numbers are positive integers greater than 1 that are only divisible by 1 and themselves. In other words, they have no other factors besides 1 and themselves.

2. How are prime numbers generated?

Prime numbers can be generated using various mathematical algorithms and techniques. One common method is the Sieve of Eratosthenes, which involves systematically eliminating multiples of numbers until only prime numbers remain.

3. What is the largest known prime number?

As of 2021, the largest known prime number is 2^82,589,933 - 1, which has over 24 million digits. This number was discovered in December 2018.

4. Why are prime numbers important in cryptography?

Prime numbers are important in cryptography because they are used in the creation of secure encryption keys. The larger the prime numbers used in the key, the more difficult it is to crack the code.

5. Are there any patterns or rules for generating prime numbers?

While there is no known formula for generating all prime numbers, there are certain patterns and rules that can help identify prime numbers. For example, all prime numbers (except 2 and 3) are of the form 6n+1 or 6n-1, where n is a positive integer.

Similar threads

  • Programming and Computer Science
Replies
14
Views
1K
Replies
6
Views
785
  • General Discussion
Replies
4
Views
2K
  • Linear and Abstract Algebra
Replies
21
Views
8K
  • Linear and Abstract Algebra
Replies
6
Views
3K
  • Linear and Abstract Algebra
Replies
11
Views
2K
  • Linear and Abstract Algebra
Replies
6
Views
6K
  • Linear and Abstract Algebra
Replies
3
Views
1K
Replies
1
Views
695
  • Linear and Abstract Algebra
Replies
8
Views
3K
Back
Top