# Prime numbers....is there a pattern? **URL:** \ **Category:** Factual Questions\ **Created:** [June 12, 2003, 1:40pm UTC](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317 "2003-06-12T13:40:45Z")\ **Posts on this page:** 20\ **Page:** 2
**Author:** ![gazpacho](https://avatars.discourse-cdn.com/v4/letter/g/6f9a4e/32.png) [@gazpacho](https://boards.straightdope.com/u/gazpacho)\ **Post date:** [June 13, 2003, 6:32pm UTC](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317/21 "2003-06-13T18:32:47Z")
No Isabelle I am not. If I had a list of all the prime numbers up to 1024 bits it is still computationally infeasible to try all these trillions (probably much much more) of prime numbers. The security does not come from the fact that there are not good algorithms for finding primes. The security comes from the fact that there are so many possible keys. ---
**Author:** ![Isabelle](https://avatars.discourse-cdn.com/v4/letter/i/b5a626/32.png) [@Isabelle](https://boards.straightdope.com/u/Isabelle)\ **Post date:** [June 13, 2003, 7:12pm UTC](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317/22 "2003-06-13T19:12:10Z")
If one were concerned solely with the “keys” there is no reason to restrict those keys to primes. There are far more non-prime numbers, ergo more possible “keys” among the non prime population. Security is not solely a function of the number of possible keys. It also is dependent, in part, on the predictability or deducibility of those keys. Hence, the ability to predict or not predict is in direct correlation to the actual “security” ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [June 13, 2003, 8:57pm UTC](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317/23 "2003-06-13T20:57:42Z")
No, there are actually as many primes as there are non-primes. Did you mean “below a certain integer”? Furthermore, even if the keys are predictable, determining a private key from the public key may be very hard. And for some algorithms, primes have desirable properties that make them better keys than composites. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [June 14, 2003, 9:35pm UTC](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317/24 "2003-06-14T21:35:34Z")
The number of primes below 2[sup]1024[/sup] is approximately 2[sup]1024[/sup]/6.9. This is a really huge number. Makes zillions look penny-ante. I consider 2[sup]80[/sup] to be infinity “for all practical purposes”. No way anyone ever will be able to generate that many primes. One of the key ideas of RSA encryption (used in Pretty Good Privacy) is that multiplying two numbers together is easy, but factoring a number is somewhat hard. Using primes means they can exploit some properties of the Euler Totient Function. (I love being able to mention ETF.) Other encryption schemes like RSA have been developed based upon the same asymmetry of calculations: Quadratic Residue (taking square roots in a mod field), Discrete Logarithms, etc. But factoring has a much longer history of resisting efforts to “crack,” so more people trust that. Note that RSA keys of modest length (e.g, 128 bits) have been broken using free cycle time on computers on the Internet, a la SETI. The technique used had _nothing_ to do with brute force test of divisibility. It involved finding numbers with certain properties in much smaller fields. ---
**Author:** ![MonkeyMensch](https://avatars.discourse-cdn.com/v4/letter/m/82dd89/32.png) [@MonkeyMensch](https://boards.straightdope.com/u/MonkeyMensch)\ **Post date:** [June 14, 2003, 10:09pm UTC](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317/25 "2003-06-14T22:09:49Z")
> [@](#): > > \*Originally posted by Topologist \* > \*\*As to the OP, some things are known about the pattern of prime numbers and many things are not … 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. \*\* Really? This strikes me as intuitive. Of course, some threads of late have disabused me of the usefulness of intuition in mathematics. Is any progress being made on this particular theorem? Does anyone have any ideas, even? ---
**Author:** ![Jabba](https://avatars.discourse-cdn.com/v4/letter/j/b5e925/32.png) [@Jabba](https://boards.straightdope.com/u/Jabba)\ **Post date:** [June 14, 2003, 10:39pm UTC](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317/26 "2003-06-14T22:39:41Z")
That has been an open problem for a long time, and has proved extremely difficult. Call a P[sub]2[/sub] a number which is either prime or the product of two ( not necessarily distinct) primes. Chen has proved that there are infinitely many primes p such that p+2 is a P[sub]2[/sub]. That’s the best result so far. ---
**Author:** ![RM\_Mentock](https://avatars.discourse-cdn.com/v4/letter/r/e274bd/32.png) [@RM\_Mentock](https://boards.straightdope.com/u/RM_Mentock)\ **Post date:** [June 15, 2003, 1:00am UTC](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317/27 "2003-06-15T01:00:08Z")
> [@](#): > > \*Originally posted by bryanmcc \* > **The hardest thing about you math blokes is just trying to figure out what you’re saying.** And it makes it tougher when we use English. ---
**Author:** ![Hari\_Seldon](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hari_seldon/32/5173_2.png) [@Hari\_Seldon](https://boards.straightdope.com/u/Hari_Seldon)\ **Post date:** [June 15, 2003, 1:41am UTC](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317/28 "2003-06-15T01:41:23Z")
I think jabba is wrong; he has got it confused with the Goldbach conjecture: Every even number is a sum of two numbers one of which is prime and the other is either prime or a product of two primes. The number of primes below n = 2^1024 is roughly n/710, which is something like 2^1021. The primes are not the keys. A key is a set of two (large) primes and their product is public. The decoding can be done only if you know the individual factors (at least you hope that is the case) and there is no known feasible way of finding the two factors just knowing the product. The entire theory can be taught in about five minutes to one who knows the basic facts about modular arithmetic, which is why it was so silly to attempt to restrict export of the method. The essential facts were known to Euler 300 years ago. Of course, someone could discover tomorrow (or could have discovered 20 years and kept secret) either a fast factorization algorithm or a way of decoding without knowing the factors. If I made such a discovery, I might try selling it to the highest bidder. ---
**Author:** ![dre2xl](https://avatars.discourse-cdn.com/v4/letter/d/34f0e0/32.png) [@dre2xl](https://boards.straightdope.com/u/dre2xl)\ **Post date:** [June 15, 2003, 2:39am UTC](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317/29 "2003-06-15T02:39:15Z")
OT but why is generating large primes so hard? Let’s take any given sequence of every known prime from 2 without any missing primes. Multiply 2, 3, 5, … P together, and add one… viola, you’ve got another prime. I’m aware that not all primes “in the gaps” between large primes have been found, but this kind of sequential mulitplication gets large very quickly… surely multiplying the entire known unbroken sequence will produce a result larger than what we’ve found so far? If not, then it should be only a matter of expanding this sequence enough (which can’t be _that_ hard…) to find the next largest prime. ---
**Author:** ![RM\_Mentock](https://avatars.discourse-cdn.com/v4/letter/r/e274bd/32.png) [@RM\_Mentock](https://boards.straightdope.com/u/RM_Mentock)\ **Post date:** [June 15, 2003, 3:34am UTC](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317/30 "2003-06-15T03:34:32Z")
> [@](#): > > \*Originally posted by dre2xl \* > **OT but why is generating large primes so hard? Let’s take any given sequence of every known prime from 2 without any missing primes. Multiply 2, 3, 5, … P together, and add one… viola, you’ve got another prime.** That number could be nonprime itself though. Then you’re pretty much back to square one. ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [June 15, 2003, 3:37am UTC](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317/31 "2003-06-15T03:37:10Z")
**dre2xl** , that method doesn’t work, unfortunately: 2_3_5_7_11_13 + 1 = 59_509, not prime. ---
**Author:** ![RM\_Mentock](https://avatars.discourse-cdn.com/v4/letter/r/e274bd/32.png) [@RM\_Mentock](https://boards.straightdope.com/u/RM_Mentock)\ **Post date:** [June 15, 2003, 3:40am UTC](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317/32 "2003-06-15T03:40:45Z")
> [@](#): > > \*Originally posted by dre2xl \* > **OT but why is generating large primes so hard? Let’s take any given sequence of every known prime from 2 without any missing primes. Multiply 2, 3, 5, … P together, and add one… viola, you’ve got another prime.** That number could be nonprime itself though. Then you’re pretty much back to square one. ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [June 15, 2003, 3:42am UTC](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317/33 "2003-06-15T03:42:14Z")
**dre2xl** , that method doesn’t work, unfortunately: 2_3_5_7_11_13 + 1 = 59_509, not prime. ---
**Author:** ![RM\_Mentock](https://avatars.discourse-cdn.com/v4/letter/r/e274bd/32.png) [@RM\_Mentock](https://boards.straightdope.com/u/RM_Mentock)\ **Post date:** [June 15, 2003, 3:49am UTC](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317/34 "2003-06-15T03:49:56Z")
Beauty, **Cabbage** simulposted simulpostings. I don’t think I’ve ever seen that before. ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [June 15, 2003, 3:56am UTC](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317/35 "2003-06-15T03:56:47Z")
Yeah, that’s a first for me, too. 😃 ---
**Author:** ![The\_Weak\_Force](https://avatars.discourse-cdn.com/v4/letter/t/9dc877/32.png) [@The\_Weak\_Force](https://boards.straightdope.com/u/The_Weak_Force)\ **Post date:** [June 15, 2003, 5:34am UTC](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317/36 "2003-06-15T05:34:03Z")
Yes, there is a pattern. Ask Mangetout for details 😉 ---
**Author:** ![Jabba](https://avatars.discourse-cdn.com/v4/letter/j/b5e925/32.png) [@Jabba](https://boards.straightdope.com/u/Jabba)\ **Post date:** [June 15, 2003, 11:07am UTC](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317/37 "2003-06-15T11:07:00Z")
**Hari Seldon** : > [@](#): > > I think jabba is wrong That’s fighting talk 😉 The same sieve methods were used for both results, and one other. It is conjectured that there are infinitely many primes of the form n[sup]2[/sup] + 1. Using sieve methods, Chen has proved that there are infinitely many P[sub]2[/sub] of this form. ---
**Author:** ![Hari\_Seldon](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hari_seldon/32/5173_2.png) [@Hari\_Seldon](https://boards.straightdope.com/u/Hari_Seldon)\ **Post date:** [June 15, 2003, 12:14pm UTC](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317/38 "2003-06-15T12:14:28Z")
Ok, I stand corrected. I was unaware of this result. Sorry. ---
**Author:** ![I\_Brian](https://avatars.discourse-cdn.com/v4/letter/i/c89c15/32.png) [@I\_Brian](https://boards.straightdope.com/u/I_Brian)\ **Post date:** [June 15, 2003, 1:31pm UTC](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317/39 "2003-06-15T13:31:36Z")
I’ve seen this topic somewhere before. 🙂 Never knew there was so much interest in primes. 🙂 ---
**Author:** ![dre2xl](https://avatars.discourse-cdn.com/v4/letter/d/34f0e0/32.png) [@dre2xl](https://boards.straightdope.com/u/dre2xl)\ **Post date:** [June 15, 2003, 3:09pm UTC](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317/40 "2003-06-15T15:09:33Z")
Ah, thanks… I was thinking of Euclid’s proof of infinite number of primes. Thanks. 🙂 [Previous page](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317.md?page=1) [Next page](https://boards.straightdope.com/t/prime-numbers-is-there-a-pattern/181317.md?page=3)