4

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?

Ayman Hourieh
  • 39,603
Ryan Shea
  • 143
  • 2
    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. – ShreevatsaR Feb 07 '14 at 15:53

2 Answers2

6

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".

TonyK
  • 64,559
2

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.

John Habert
  • 4,001
  • 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. – ShreevatsaR Feb 07 '14 at 15:52
  • @ShreevatsaR Original post didn't mention security. So how do you generate primes of a certain length? – John Habert Feb 07 '14 at 16:02
  • 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. – ShreevatsaR Feb 07 '14 at 16:08
  • 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. – ShreevatsaR Feb 07 '14 at 16:09
  • @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. – John Habert Feb 07 '14 at 16:12
  • Yes I think you're right... my first comment was without carefully reading the question: I think he's ok with (and actually wants) "special" prime numbers, so your suggestion of picking one from a list is probably appropriate. – ShreevatsaR Feb 07 '14 at 16:15
  • To clarify, I want a prime number to be used for modular math. Specifically, I want a prime number that is greater than all 256 bit integers. I also want to hardcode that prime number into a python library I'm working on and I want to make sure that anyone reading my code will not be suspicious of the prime number that I used. TonyK's answer is exactly what I was looking for. – Ryan Shea Feb 07 '14 at 21:28