I'm looking for non-magic prime numbers (ones that are very clearly not arbitrarily hand-picked) to use in a python library. Right now, I'm using mersenne primes, but I need one prime that is at least slightly larger than $2^{256}$ (at least $256$ bits), and there are no mersenne primes even remotely close.

What is the best way to find such a prime? Are there other famous lists of primes I should look into other than mersenne primes? Are there good published lists available of prime numbers? What is the best way to test if an extremely large number is a prime number?

  • 2
    $\begingroup$ I thought a "magic" prime number was one with some special property, such as being a Mersenne prime. If you want a truly anonymous prime (which is unlikely to be special or "magic" in any way), you should generate one yourself randomly. $\endgroup$ – ShreevatsaR Feb 7 '14 at 15:53

You want the on-line Prime Numbers Generator and Checker available here. Generate a random 257-bit number somehow, enter it in the box, and select "Find next". It computes the smallest prime number greater than your random number. And it's lightning fast.

Unfortunately it doesn't speak hex, but it does understand expressions, such as "2^256+12345".

  • $\begingroup$ This was perfect, thank you. $\endgroup$ – Ryan Shea Feb 7 '14 at 21:29

Have you tried the largest Mersenne prime known $2^{57885161}-1$? You can find a bunch of other large primes here.

In reference to your question about testing, the easy to code yourself methods are slow and the quicker methods are tricky to code correctly. You are better off taking a prime from a list. Though you can check Wikipedia for more info and links to info about the different types of primality testing.

  • $\begingroup$ You are definitely not better off taking primes from a list! That's going to lead to all sorts of insecurity. Especially if your purpose is anything cryptographic, you should generate the prime randomly (such that it is unlikely anyone else has ever generated the same prime), not pick it from a finite list. It's pretty straightforward to generate random primes of a certain length. $\endgroup$ – ShreevatsaR Feb 7 '14 at 15:52
  • $\begingroup$ @ShreevatsaR Original post didn't mention security. So how do you generate primes of a certain length? $\endgroup$ – John Habert Feb 7 '14 at 16:02
  • $\begingroup$ Yes, perhaps the OP is using "magic" in a sense opposite to the meaning I interpreted it as. You generate primes of a certain length by generating random numbers of that length and checking them each, until one is prime. Heuristics from the prime-number theorem say that the "probability" of a random number of length $n$ being prime is about $1/n$, so after about $n$ trials ($256$ for $n = 256$), you'll have a prime. This is in fact how ssh keys, RSA keys etc. are generated. $\endgroup$ – ShreevatsaR Feb 7 '14 at 16:08
  • $\begingroup$ By the way, for checking whether a number is prime, you can use one of the standard libraries, usually... or something like Miller-Rabin is a good tradeoff between speed and simplicity of implementation. You could even use some special tool, like the online number generator linked in the other answer, or some system like Sage. $\endgroup$ – ShreevatsaR Feb 7 '14 at 16:09
  • $\begingroup$ @ShreevatsaR I agree with how you interpreted magic. But I assumed from post that since he was already using Mersenne, then another Mersenne would do. Though not sure he really needed the biggest one. $\endgroup$ – John Habert Feb 7 '14 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.