I have some questions about those crazy numbers, primes…
Is there any method other than brute force to find them?
How are they used, and why are they so important?
Has there ever been a case where a prime was found that was smaller than the largest known one? For example “finding” 3 when 5 was already known.
The largest known primes are generally Mersenne primes, which take the form 2[sup]n[/sup]-1. Not all such numbers are prime, and they go through a brute-force screening process to determine if they are prime or not. It is certainly possible and even likely that there are many non-Mersenne primes that are smaller than than the largest known ones that have not yet been discovered or were discovered after the larger ones were found. Brute force is the only way to definitively find primes. No formula has yet been found which can generate them at will indefinitely.
There are algorithms such as Miller-Rabin that test the primality of a randomly chosen integer. It’s faster than the brute force method, but there is a small chance you’ll get an incorrect result.
When you get into the very large (say 100 digits or more) prime numbers, then you can use them in encryption schemes. The RSA algorithm uses large prime numbers. If you want to learn more about this, check your library for books on modern cryptography.
Don’t know the answer to that last question, sorry.
Prime checking can now be done relativly quickly, due to a new result of Agrawal, Kayal and Saxena.
Many really large prime numbers found these days are “Mersenne Prime.” Most prime numbers smaller than these are missed. In other words, prime seaching does not go in strict order.
There are, of course, infinitly many prime intergers. I have heard primes are used somehow in encryption, though I don’t really know how.
There was an algorithm published last year which can determine with 100% accuracy whether a number is prime, and it does it quickly.
Primes are important because every natural number can be uniquely represented as a product of powers of primes. This allows you to do everything from encryption to Gödel numbering–the former being entirely practical, and the latter being entirely theoretical.
If the answer to the third question is no, it’ll be yes someday.
O(ln[sup]6[/sup]n) time is faster than any brute force method, but I wouldn’t call it quick in terms of the largest known primes!
Anything that runs in polynomial time wrt the input size is quick in my book. YMMV.
While I was playing silly games with a program based on Pythagoras’/Fermat’s theorem, I stumbled on a method of generating primes (I don’t think it finds all of them, but the result was, as far as I was able to test (test, not prove) always prime.
Damned if I can remember what the formula was though; it was something simple like n[sup]2[/sup] + (n+1)[sup]3[/sup] + (n+2)[sup]4[/sup].
I suspect it has all been done before; can anyone refresh my memory?
Mangetout, there is no (nontrivial–meaning non-constant) polynomial that produces only primes, though there are polynomials that produce only primes for long strings of integers:
x[sup]2[/sup] + x + 41 (Euler’s polynomial)
is prime for x = 0, 1, 2,…, 39.
Also
36x[sup]2[/sup] - 810x + 2753
is prime for x = 0, 1,…, 44.
(The last one holds the current record length for a prime producing quadratic polynomial, AFAIK).
My guess is that you discovered a similar such polynomial.
Damn! I’ll have to see if I can dig out the code (I don’t hold out much hope as I have replaced my PC several times since); you’re probably right, but I wish I could remember the method. I don’t have the math skills to attempt a real proof so all I could do was leave it churning out results overnight and check them by brute force.
Gaaah! this is so frustrating; I can remember where I was when I thought of it, I can remember what I was doing, I can remember what the weather was like and who I was with, but I CAN’T get the method! - I do know we tested it way beyond x=44 though…
You threw away the winning lottery card!
I will have to go through all my old floppy disks tonight - it’s just possible that I saved the code somewhere.
Thanks for that, but I didn’t recognise anything there; it was something really stupidly simple, like
n[sup]x[/sup] + nsup[/sup] + nsup[/sup] => P
or
n[sup]x[/sup] + n+1sup[/sup] + n+2sup[/sup] => P
-like those, but not exactly those, obviously.
I stumbled over it on the train on the way to work one morning; I had been looking at Pythagoras’ and Fermat’s theorems the night before and I was playing about with the formulae in my head (for small values of n and x) when it dawned on me that the last few results had been primes (I’m pretty sure they were smallish ones, too) - when I got to work, I wrote a very simple program to test it and it did appear to produce only primes (brute force division of 2 to sqr(P)) - it churned out thousands of results (we did not have the time to test all of them once they got very big, but we were unable to find a non-prime by random sampling).
In public key ecryption, large primes are multiplied to generate encryption keys. (The key is used to do bit-by-bit and-ing (or is it or-ing?) against the message to generate the encrypted message). To decode the message you have to know the primes (or maybe just one, can’t remember).
Anyway, notwithstanding the gaps in my knowledge, the point is that do break a code based on a 128-bit key you have to factor a very large number into its constituent primes, which would take impractically long to do (using today’s computing technology).
Mersenne primes are of the form 2[sup]p[/sup]-1. If the exponent isn’t prime, it isn’t prime (but not the contrapositive).
Mersenne prime candidates are not tested by brute force. The Lucas-Lehmer test is fairly simple and efficient. In particular, it can take advantage of how binary is done on computers. There are a very large number of tests that are completely non-brute force for testing primes.
Since there are less than 40 Mersenne primes and the density of primes is n/ln n, there are an immense number of “unknown” primes smaller than the largest known Mersenee prime.
Unfortunately, in their quest for “the largest known prime”, researchers skip over large numbers of exponents hoping to hit a good range with a Mersenne prime. It is quite possible that there are more Mersenne primes smaller than the largest known.
BTW, the largest known prime in recent decades hasn’t always been a Mersenne prime. There is an fast test for numbers similar to Mersenne numbers involving 3 as the base of the exponent.
As the last part of the OP. It is very easy, given two large primes, to multiply them together to get a product. OTOH, given a product of two large unknown primes, we know of no way to find those primes. The prime numbers can be thought of as a secret key for encryption. This can be exploited (along with other properties of prime products, such as the Euler Totient Function) to create encryption schemes. The most famous of which is the RSA algorithm used by a lot of privacy software. (E.g., in PGP.)
It is not obvious to me that there are an infinite number of primes. Can someone offer a concise argument to illustrate this?
Assume there are only n primes. Take their product, and add 1. Is that number prime or composite? If it’s prime, QED. If not, it’s divisible by some prime–but not any of the first n primes. Again, QED.
That proof was known to Euclid, btw.
Thanks, ultrafilter.
