# Prime numbers....is there a pattern?

With everything I learned in high school all but a blur, there are still a few things i recall. One of which is something my algebra teacher told us. She explained to us Prime numbers, and the fact that there is no patter to them. She went on to say that if a pattern were ever to be found the possibilites were seemingly endless. It was somethign I never could understand. How would a pattern of prime numbers make any difference any way? Maybe she was just blowing smoke up my our ass or maybe my memory isn’t as clear as I thought.

Large primes are extremely important in the field of cryptography. Right now, the best method for finding all primes is to try every number, which takes a while. If there were a pattern of primes, it would revolutionize the field.

There are a few localized patterns (they only hold for short sequences of primes), but nothing that all primes fit.

There exists the Ulam Rose which is a type of pattern formed when you spiral the number outwards starting with 1 in the centre.

Try here…

I do remember heraing a mention of “cryptography”, but can any one explain how a pattern would help in this?

I don’t mean to be ‘high and mighty’ but one of the reasons I never post here is that I can usually find all my answers with Google

We did this thread a while back. It has more discussion.

I’m not certain, but I think the discovery of a pattern to the set of prime numbers would eventually turn into a proof that P = NP, and nobody wants that. Such a proof could be turned into an algorithm for breaking any current encryption scheme and be used to access your bank accounts and other private information.

Sometimes the inability to find patterns is a GOOD thing

Well, the Sieve of Eratosthenes doesn’t “try every number”, and that’s been known for thousands of years.

Primality testing being in P (poly time) does not prove that P=NP. OTOH, if it were proven not in P, that would imply P != NP. Also, many encryption algorithms exist. Breaking one doesn’t necessarily break others.

We know now that primality testing is in P. What we still don’t have, and what many of the public key cryptography systems depend on not having, is a fast way to factor large composite numbers.

As to the OP, some things are known about the pattern of prime numbers and many things are not. The Prime Number Theorem describes the asymptotic distribution of the primes; it gives a formula that approximates how many primes there are below any given number. On the other hand, we still don’t know whether or not there are infinitely many “twin primes”: pairs of primes like 11 and 13 that differ by only 2.

True. What I should have said is that with every currently known method, you can’t find the nth prime without finding the first n - 1 primes. That’s what a pattern would help us get around.

Is that right? I thought that if you wanted to know whether n was prime, you just had to know the primes smaller than sqrt(n). For instance, if I want to determine whether 79 is prime, I don’t need to know that 73 is prime (n-1). I only need to know that it isn’t divisible by 2, 3, 5, or 7 (the only primes smaller than sqrt(79)). Or am I misunderstanding your statement?

In order to know the nth term in the sequence of primes, you need to know the first n - 1 terms.

Well, yes, that is a repetition of what you said above, but hardly an explanation. Are you saying that when they announce that 2^zillion - 1 is prime, they’ve found every prime lower than that? In fact, I recall a thread here several months ago asking not what the largest known prime was (a Mersenne prime, I believe), but what is the largest known prime for which all smaller primes are known, obviously implying that those are not the same.

Or are you stating that if you want to know the nth prime for a specific n, then you have to know the first n-1 primes? For instance, if you want to know that 15,485,863 is the millionth prime, then logically you’d have to find every prime smaller than it. If you just want to know that it is prime, then you only have to check to see if it is divisible by any prime (and therefor you must know every prime) below 3,935, the largest integer smaller than its square root.

The hardest thing about you math blokes is just trying to figure out what you’re saying.

The second interpretation is correct. The 5th prime is 11, but the only way you’ll know that is to know the 1st, 2nd, 3rd, and 4th primes.

Ah. Thank you for the clarification.

Prime numbers are those numbers that are only divisible by themselves and 1. For instance, these are prime numbers:
3,5,7,11,13,17,23,29,31,37,41,43,47,51…

There is no pattern…especially as you get higher up… some of the “possible primes” are not really since that 2 or 3 as a divisor begins to work.

Many scientific calculations are predicated on prime numbers. For example, security codes. Many programming functions. If you could “predict” primes with a formula, then they wouldn’t be as valuable as keys.

Isabelle

Public key cryptography that I am familiar does not gain its security because there primes have no pattern but instead because there are a huge number of possible prime numbers that can be used and to try them all takes too long.

How is it that Cryptograhy makes use of prime numbers? Why not use just plain ol’ everyday numbers? Does anyone have a good expantion of the workings of a system that bases its cryptograhy off of prime numbers?

mjcocat

http://www.osforge.com/news/00766.html gives an explanation of the main use of prime numbers in cryptography.

because they’re is no predictable way to develop primes (multi digit primes specifically) no formulaic way to insert them is possible so, alas, it takes too long to plug them in. So you’re talking in circles!