# Prime numbers **URL:** \ **Category:** Factual Questions\ **Created:** [October 26, 2019, 3:25pm UTC](https://boards.straightdope.com/t/prime-numbers/842498 "2019-10-26T15:25:27Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![HoneyBadgerDC](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/honeybadgerdc/32/1033_2.png) [@HoneyBadgerDC](https://boards.straightdope.com/u/HoneyBadgerDC)\ **Post date:** [October 26, 2019, 3:25pm UTC](https://boards.straightdope.com/t/prime-numbers/842498/1 "2019-10-26T15:25:27Z")
Is there anything particularly relevant about prime numbers? They seem to get a lot of attention and I never understood why. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [October 26, 2019, 3:33pm UTC](https://boards.straightdope.com/t/prime-numbers/842498/2 "2019-10-26T15:33:53Z")
They sure are relevant to mathematicians (and computer scientists, etc.) Do you mean more “natural” applications? For example, there is a [cicada](https://en.wikipedia.org/wiki/Magicicada) known to emerge in prime-numbered year cycles as an evolutionary strategy (predator avoidance). ---
**Author:** ![yearofglad](https://avatars.discourse-cdn.com/v4/letter/y/b782af/32.png) [@yearofglad](https://boards.straightdope.com/u/yearofglad)\ **Post date:** [October 26, 2019, 3:48pm UTC](https://boards.straightdope.com/t/prime-numbers/842498/3 "2019-10-26T15:48:49Z")
They’re useful in cryptography, particularly the products of very large primes. Those products, since they only have 4 factors (1 and themselves, as well as the 2 very large primes used to construct the number), are very difficult and time-consuming to factor, even for computers, and so are useful for encrypting and decrypting. ---
**Author:** ![Bryan\_Ekers](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/bryan_ekers/32/183_2.png) [@Bryan\_Ekers](https://boards.straightdope.com/u/Bryan_Ekers)\ **Post date:** [October 26, 2019, 3:56pm UTC](https://boards.straightdope.com/t/prime-numbers/842498/4 "2019-10-26T15:56:09Z")
One of the more common applications (though most people using it don’t understand or need to care about the mechanics) is RSA cryptography, allowing a person to send secret messages. The gist (highly simplified) is that: Secretly choose a prime number _p_, which by definition can only be divided by 1 and _p_ itself. Secretly choose a different prime number _q_, which by definition can only be divided by 1 and _q_ itself. Multiply _p_ and _q_ to get _N_. _N_, therefore, will only be divisible by 1, _p_, _q_ and _N_ itself. What allows RSA cryptography to work is that once you’ve chosen _p_ and _q_, generating _N_ is easy. If all you have is _N_, trying to work backward to find _p_ and _q_ is difficult. Picture 15. Very quickly, anyone can see that its _p_ and _q_ are 5 and 3. But what if _N_ is 927401749817398759182759192911 ? How long would it take even a very fast computer to find _p_ and _q_? Years? Centuries? The age of the universe? Anyone can generate their own _N_ and publish it freely. This becomes their “public key”. If I wish to send a secret message to someone, I will use their public key to encrypt it. Then it doesn’t matter who might see the encoded message, because the only way to decrypt it is by using _p_ and _q_, which the recipient knows and has _not_ published, as they form his “private key”. ---
**Author:** ![am77494](https://avatars.discourse-cdn.com/v4/letter/a/d2c977/32.png) [@am77494](https://boards.straightdope.com/u/am77494)\ **Post date:** [October 26, 2019, 4:01pm UTC](https://boards.straightdope.com/t/prime-numbers/842498/5 "2019-10-26T16:01:55Z")
With the cryptography applications mentioned, it is also to be said that math guys love prime numbers for the same reason climbers like mountains. They are challenging to get to. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [October 26, 2019, 4:07pm UTC](https://boards.straightdope.com/t/prime-numbers/842498/6 "2019-10-26T16:07:50Z")
> [@Bryan\_Ekers](#): > > ) > > Picture 15. Very quickly, anyone can see that its _p_ and _q_ are 5 and 3. But what if _N_ is 927401749817398759182759192911 ? How long would it take even a very fast computer to find _p_ and _q_? Years? Centuries? The age of the universe? 927401749817398759182759192911 = 11 x 13693 x 6157105819279915810883857 ---
**Author:** ![Andy\_L](https://avatars.discourse-cdn.com/v4/letter/a/c67d28/32.png) [@Andy\_L](https://boards.straightdope.com/u/Andy_L)\ **Post date:** [October 26, 2019, 4:14pm UTC](https://boards.straightdope.com/t/prime-numbers/842498/7 "2019-10-26T16:14:04Z")
> [@DPRK](#): > > 927401749817398759182759192911 = 11 x 13693 x 6157105819279915810883857 Okay, that was pretty quick. Public keys involve numbers that don’t have small divisors (like 11 and 13693), for just that reason ---
**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\ **Post date:** [October 26, 2019, 4:16pm UTC](https://boards.straightdope.com/t/prime-numbers/842498/8 "2019-10-26T16:16:06Z")
“Relevant” to what or to whom? Prime numbers are the building blocks of all (whole) numbers, in somewhat the same way that the chemical elements are the building blocks of all chemical compounds. Water is H[sub]2[/sub]O, and salt is NaCl. 10 is 2\*5, and 24 is 2[sup]3[/sup]\*3. (And because 10 = 2\*5 is the basis for our base-10 numbering system, the fractions that have terminating decimal representations have denominators whose only prime factors are 2 and/or 5. If the denominator has any other prime factor besides 2 or 5, it’s a repeating decimal. That’s just one of the many ways in which primes are relevant to the way numbers “work.”) ---
**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:** [October 26, 2019, 4:28pm UTC](https://boards.straightdope.com/t/prime-numbers/842498/9 "2019-10-26T16:28:15Z")
Another common use of prime numbers in computing is in hashing. Hashing is when you take a long string of something meaningful (a name, a part number, whatever you’re keeping track of and want to access quickly) and use a function to map it into a small range. So you want to keep track of a thousand parts with really long part numbers. Keep them in a table a bit over a thousand places long. Someone types in a part number, apply the hash function to get where it (hopefully) is in the table. Look for it there. (There’s strategies for dealing with two things mapping to the same place.) One common aspect of picking the size of the hash table is to make it a prime number. This makes things like the aforesaid double mapping issue easier to deal with. Pick a k. If the hash maps to m, look there, if it’s not there look at m+k, m+2k, etc. until you find it (or hit a blank spot in which case it’s not in the table). A properly chosen hash function, table size, etc. means you don’t have to look far. But in the worse case you keep looking and looking until you look everywhere. If the table size wasn’t prime, you might loop around the same spots over and over. E.g., a table size 20 and k of 5 you look at 3, 8, 13, 18, 3 … There is an astonishing number of ways that using primes in computing that ensures that things get distributed right, even balanced, etc. The classic Fast Fourier Transform uses large powers of two but creates certain artifacts since those powers of two are quite non-prime. (In a FFT processed image of an asteroid you may see “ghost” dots around it.) There’s an algorithm by Al Borodin that’s almost as fast and uses large primes. Eliminates many artifacts. All this of course reminds me of the Number Theorist G.H. Hardy’s quote: “No one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems unlikely that anyone will do so for many years.” That was 1940. Number Theory was already being used in breaking enemy codes and relativity led to the Bomb. Don’t knock something if it seems impractical. Uses are found quite often. ---
**Author:** ![Bryan\_Ekers](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/bryan_ekers/32/183_2.png) [@Bryan\_Ekers](https://boards.straightdope.com/u/Bryan_Ekers)\ **Post date:** [October 26, 2019, 4:35pm UTC](https://boards.straightdope.com/t/prime-numbers/842498/10 "2019-10-26T16:35:56Z")
> [@DPRK](#): > > 927401749817398759182759192911 = 11 x 13693 x 6157105819279915810883857 Sorry, I meant to say 9274017498173987591827591929119287549275972957923857293579287562936729375290375293759235879238750298672098672395723957293875923857926729367829867296872967. ---
**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:** [October 26, 2019, 5:26pm UTC](https://boards.straightdope.com/t/prime-numbers/842498/11 "2019-10-26T17:26:39Z")
> [@Bryan\_Ekers](#): > > Sorry, I meant to say 9274017498173987591827591929119287549275972957923857293579287562936729375290375293759235879238750298672098672395723957293875923857926729367829867296872967. That’s only 154 digits. I think such numbers can now be factored, although not easily. But the product of two 500 digit primes will be essentially unfactorable, at least without a quantum computer. One interesting fact is that there are algorithms that can quickly test to see if a 500 digit prime with 99.9999999…% probability. There are also much slower ones that give 100% but I doubt they are worth the effort. This is what makes RSA encryption so successful. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [October 26, 2019, 5:55pm UTC](https://boards.straightdope.com/t/prime-numbers/842498/12 "2019-10-26T17:55:01Z")
It’s also clearly divisible by 3343 🙂 But, yes, it gets harder: to generate good RSA moduli you can start out by randomly choosing two (sufficiently) large primes- 500 digits is not overkill here- and multiplying them together. ---
**Author:** ![pmwgreen](https://avatars.discourse-cdn.com/v4/letter/p/edb3f5/32.png) [@pmwgreen](https://boards.straightdope.com/u/pmwgreen)\ **Post date:** [October 26, 2019, 6:25pm UTC](https://boards.straightdope.com/t/prime-numbers/842498/13 "2019-10-26T18:25:44Z")
[The Ishango bone](https://en.wikipedia.org/wiki/Ishango_bone) is 20,000 years old and has a row of tally marks representing 11, 13, 17, and 19, the four primes between ten and twenty. It has been speculated that it was useful to decide if a collection of objects could be evenly divided. Anyway, who ever made it found those numbers interesting enough to write down. ---
**Author:** ![TriPolar](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/tripolar/32/3008_2.png) [@TriPolar](https://boards.straightdope.com/u/TriPolar)\ **Post date:** [October 26, 2019, 6:30pm UTC](https://boards.straightdope.com/t/prime-numbers/842498/14 "2019-10-26T18:30:36Z")
> [@pmwgreen](#): > > [The Ishango bone](https://en.wikipedia.org/wiki/Ishango_bone) is 20,000 years old and has a row of tally marks representing 11, 13, 17, and 19, the four primes between ten and twenty. It has been speculated that it was useful to decide if a collection of objects could be evenly divided. Anyway, who ever made it found those numbers interesting enough to write down. Really? You think that was needed to determine whether a set of 19 or less objects could be evenly divided? ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [October 26, 2019, 6:52pm UTC](https://boards.straightdope.com/t/prime-numbers/842498/15 "2019-10-26T18:52:10Z")
> [@Bryan\_Ekers](#): > > … But what if _N_ is 927401749817398759182759192911 ? Obviously I’ve been ninja’ed, but my old laptop factors this tiny number in a tiny fraction of a second! > [@ftg](#): > > One common aspect of picking the size of the hash table is to make it a prime number. This makes things like the aforesaid double mapping issue easier to deal with. Pick a k. If the hash maps to m, look there, if it’s not there look at m+k, m+2k, etc. until you find it (or hit a blank spot in which case it’s not in the table)… > If the table size wasn’t prime, you might loop around the same spots over and over. E.g., a table size 20 and k of 5 you look at 3, 8, 13, 18, 3 … Yes. BTW, sometimes “quadratic reprobing” is useful (m, m+1, m+4, m+9, …) although it visits only half the table. Another use of prime numbers is in reversible hashing, for example: hashc = datum \* 2340563 % 3787109 datum = hashc \* 3749658 % 3787109 (The first two constants are primes.) Finally, may I plug [_Good Thief_](http://www.script-o-rama.com/movie_scripts/g/good-thief-script-transcript-nolte.html), one of my favorite movies? Bob (Nick Nolte) places a large bet on 17. Anne (Nutsa Kukhianidze) pushes the stack to 18, saying “It’s my birthday. I’m not a prime anymore.” (Not only does the roulette ball land on #18 but, although Bob is still much older than Anne, the age of 18 offers some legitimacy and the viewer senses that the sexual tension between the two need no longer go unrequited.) ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [October 26, 2019, 6:59pm UTC](https://boards.straightdope.com/t/prime-numbers/842498/16 "2019-10-26T18:59:29Z")
> [@DPRK](#): > > … there is a [cicada](https://en.wikipedia.org/wiki/Magicicada) known to emerge in prime-numbered year cycles as an evolutionary strategy (predator avoidance). For a loosely related reason, it is often good practice to arrange that the number of teeth on two interacting gears be relatively prime to each other. ---
**Author:** ![RioRico](https://avatars.discourse-cdn.com/v4/letter/r/f04885/32.png) [@RioRico](https://boards.straightdope.com/u/RioRico)\ **Post date:** [October 26, 2019, 10:21pm UTC](https://boards.straightdope.com/t/prime-numbers/842498/17 "2019-10-26T22:21:48Z")
Prime numbers: 1,2,3,5,7,11,13… Prime ribs: in packs of 3,5,7,11… Coincidence? ---
**Author:** ![TriPolar](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/tripolar/32/3008_2.png) [@TriPolar](https://boards.straightdope.com/u/TriPolar)\ **Post date:** [October 26, 2019, 10:29pm UTC](https://boards.straightdope.com/t/prime-numbers/842498/18 "2019-10-26T22:29:23Z")
> [@RioRico](#): > > Prime numbers: 1,2,3,5,7,11,13… > > Prime ribs: in packs of 3,5,7,11… > > Coincidence? The largest Prime Rib number is 7. All the numbers 1 - 7 are Prime Rib numbers. I do not know if they are related concepts, I know meat pretty well, but math not so much. ---
**Author:** ![pulykamell](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/pulykamell/32/3166_2.png) [@pulykamell](https://boards.straightdope.com/u/pulykamell)\ **Post date:** [October 26, 2019, 10:46pm UTC](https://boards.straightdope.com/t/prime-numbers/842498/19 "2019-10-26T22:46:36Z")
> [@bryan ekers](#): > > sorry, i meant to say 9274017498173987591827591929119287549275972957923857293579287562936729375290375293759235879238750298672098672395723957293875923857926729367829867296872967. 3343 × 80814362767 × 34327563689566697334089737489352304622626569537285926010522105474112102391286515036197395301245419504370957964659993730648 90549347575330407 (or at least that’s what the online factor site is telling me.) ---
**Author:** ![pulykamell](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/pulykamell/32/3166_2.png) [@pulykamell](https://boards.straightdope.com/u/pulykamell)\ **Post date:** [October 26, 2019, 10:52pm UTC](https://boards.straightdope.com/t/prime-numbers/842498/20 "2019-10-26T22:52:26Z")
ETA: Oh, wait, that latter number is continuing to break down as I let it run, so it’s not a complete prime factorization. Oh well. [Next page](https://boards.straightdope.com/t/prime-numbers/842498.md?page=2)