Applications and Natural Occurrences of Prime Numbers

I'm fascinated by prime numbers, and over the years, I've found multiple applications and natural occurrences for them. But can anyone suggest some alternatives that aren't in my list?

Applications of Prime Numbers

• Public key cryptography algorithms
• The lengths of hash tables (not recommended)
• Prime polynomials can be used for hash functions and CRC algorithms
• Programs that search for large prime numbers can be used as “torture tests” for compilers, multitasking operating systems, memory, processors, etc.
• Pseudo-random-number generators
• Hard disk interleaving
• Error-correction codes (quadratic residue codes)
• Since no known natural process generates prime numbers, extraterrestrials might use them at the beginning of a radio transmission so we can distinguish it from a natural process (as in Carl Sagan's Contact).
• Generating organically tiling images

Applications of Coprimality

• If the number of teeth on a sprocket and the number of links in a chain are coprime, then the sprocket-chain system will experience even wear (cyclical wear will be minimized).
• Nanotech symmetrical sleeve bearings, in which the outer sleeve has m-fold rotational symmetry and the inner sleeve has n-fold rotational symmetry, would in theory function most smoothly when m and n are coprime. (Nanosystems, K. Eric Drexler, p. 286)

Natural Occurrences of Prime Numbers

• The 13- and 17-year life cycles of periodical cicadas (genus magicicada) may be an evolutionary advantage (minimizing exposure to predators and competing broods).
• Feel free to leave comments suggesting tags -- for now the moderators are happy to retag as necessary. – Scott Morrison Oct 18 '09 at 3:37
• Community wiki? – Anweshi Aug 3 '10 at 13:48

There is a class of error-correcting codes called quadratic residue codes - these are based on the quadratic residues modulo a prime.

• The quadratic residue codes include the perfect ternary and binary Golay codes, which provide points of entry to the realm of the sporadic groups... – DavidLHarden Apr 9 '11 at 7:38

For a semi-serious application of prime numbers, how about "establishing communication with aliens"? See Carl Sagan's novel "Contact".

• Heh, I think both Carl Sagan and Arthur C. Clarke made mention of alien communication. Added. :) – user618 Aug 4 '10 at 19:04

I hate to say this, but the Yan et al. paper seems a bit crackpotty. (abstract, brief discussion at Google Books from the book by Crandall and Pomerance.) I suspect it's just based on some numerical coincidences.

The others are nice examples, though.

this is somewhat related (but different) to pseudo-random number generators (PRNGs):

The $s$-dimensional Halton sequence is a quasi-Monte Carlo sequence which is a collection of van der Corput sequences in bases $\{b_{1}, b_{2}, \ldots, b_{s}\}$. The bases $b_{i}$ are chosen so that they are pairwise mutually prime. Thus, the natural choice is to use the first $s$ prime numbers.

Quasi-Monte Carlo sequences are number-theoretic sequences designed to give good uniformity in the $s$-dimensional cube. There are randomization techniques which allow them to be to used in simulation like one would with regular PRNGs.

The lengths of hash tables

This is something of a myth. If you have a good hash function, the number-theoretical properties of your table's modulus are irrelevant; conversely, if you have a bad hash function, a prime modulus does little to salvage it.

Indeed, a power-of-two modulus has a lot to recommend itself in practice: you can perform reduction of $x$ modulo a power of two $n$ in one processor cycle using the identity $x\ MOD\ n = x\ AND\ (n-1)$.

Look at the highest-performing hash table implementations and you will find they use powers of two. Examples include Google's sparsehash and Sean Barrett's hash table from his article on Judy arrays.

• I've added a "not recommended" comment at the end of that example, thanks. – user618 Aug 4 '10 at 19:03

Maybe this one is too frivolous, but sometimes, at Chinese restaurants, I get 5 shumai or 7 peking ravioli, instead of 6 or 8, and I've always wondered if that was a deliberate ploy to entice people to order more servings!

• I remember ordering appetizers at several restaurants that couldn't be divided evenly... – user618 Aug 7 '10 at 21:50