A fascinating but little known application of prime numbers involves the search for, and communication with, extraterrestrials.  In the 1997 film Contact (adapted from Carl Sagan’s novel by the same name), Ellie Arroway and her team of radio telescope ET hunters pick up a repeating signal from the nearby star Vega (around 25 light years away).  Tuning in they quickly realise the message contains the sequence of early prime numbers 2, 3, 5, 7, 11.  They excitedly conclude that they’ve stumbled upon a bona fide alien signal.  Why?

Foremost, because whilst primes are fundamental to the generation of the natural numbers, they’re also extremely difficult to find and predict.  Over 2300 years ago, in one of the most elegant and famous proofs in number theory, Euclid demonstrated that there are infinitely many primes (see below), yet to this day there’s no known polynomial or simple formula for generating the nth prime.  They appear almost randomly embedded in the space of all natural numbers and this elusiveness means that sequences of primes don’t tend to arise from naturally occurring processes.

Other sequences of numbers frequently occur in nature.  In fact any non-random sequence of numbers we care to think of is probably rooted in some physical process or intuition about our environment. For example, what if we tried to get ET’s attention by broadcasting the following sequence (terminated for some suitable n):

We might argue such a sequence (doubling the preceding digit) would be interpreted as a clear and deliberate signal.  What else could it be confused with? Quite a lot as it happens.  For starters nuclear chain reactions follow such a   growth.  Fire a neutron at a Uranium 235 atom and energy plus two neutrons are released.  Those two neutrons in turn may collide with two more Uranium atoms generating 4 neutrons, and so on.  Clearly this kind of uncontrolled fission happens routinely within the evolution of stars so such a sequence of numbers wouldn’t be an optimal extraterrestrial handshake.  How about instead we send a simple repeating sequence of fixed amplitude, a sort of cosmic door knock if you like:

A signal with these characteristics was detected in 1967 by Jocelyn Bell Burnell in Cambridge, England.  The signal was uncovered during a study of Quasars and resembled a series of regular peaks of fixed amplitude 11/3 second apart.  The team was so baffled by it they identified it with the codename LGM (little green men).  Yet the signal turned out to have a completely natural source – it was in fact the regular and rapid rotation of a distant pulsar (the first such detected and studied) issuing forth regular bursts of electromagnetic radiation.

Semiprimes and the Drake Cryptograph

In the 1970s Frank Drake of Cornell University proposed a simple yet elegant method for interstellar communication utilising primes.  It involved sending a pictorial binary message (comprising just 0’s and 1’s) and a number for deciphering the message, known as a semiprime.  A semiprime is a number generated from the product of exactly and only two primes.  For example six, fifteen and twenty five are semiprime because 6 = 2 x 3 = 3 x 2,  15 = 3 x 5 = 5 x 3 and 25 = 5 x 5.  Twelve is not semiprime because 12 = 2 x 2 x 3 = 2 x 3 x 2 = 3 x 2 x 2.

“I know perfectly well that at this moment the whole universe is listening to us,” Jean Giraudoux wrote in The Madwoman of Chaillot, “and that every word we say echoes to the remotest star.”  That poetic paranoia is a perfect description of what the Sun, as a gravitational lens, could do for the Search for Extraterrestrial Intelligence. – Frank Drake

The idea is you build a picture array with 0’s and 1’s such that the length (or cardinality) of the data set is a semiprime, l = p x q.  This semiprime is supposed to  suggest to the receiving intelligence to arrange the data in two possible configurations:  p x q or q x p.  One of these configurations contains the message.

Example:  Let’s take a really simple example to illustrate the method.  We’ll pitch this in reverse and pretend we’ve just received a Drake cryptograph from outer space.  Our receivers pick up the following repeated signal from the double star Gamma Andromedae:

On first appearance the data looks pretty uninteresting but if we count the number of elements in the list (the cardinality) we get 15.  What’s special about 15?  Well it happens to be semiprime:  3 x 5 = 5 x 3.  Great.  That suggests two clear ways or arranging the bits.  Let’s first try breaking it into 5 columns by 3 rows:

Hmmmm….nothing to see here.  What about 3 columns by 5 rows:

It’s the letter F!  Amazing….we’ve made first contact with an alien civilisation who might join us for a game of interstellar scrabble!

The Arecibo Message

Perhaps the most famous use of Drake’s cryptograph was the Arecibo message broadcast  in 1974 from the recently refurbished Arecibo radio telescope in Puerto Rico towards the globular cluster M13 (25,000 light years away).  The data steam had a cardinality of 1679 bits, which is a semiprime with the following prime factors 73 x 23 or 23 x 73.  The correct orientation for revealing the message is 23 columns x 73 rows.  Voila!

The message (co-authored by Drake, Carl Sagan and others) is supposed to convey a condensed summary of the human species – its technology, biology and location in space (see here for more details).  Whether or not such a message would be understood by another technical civilisation, if successfully decoded, is open to debate.  Any such civilisation would certainly need to share many common traits with the human species at the very least.  But the main motivation behind the message was simply to demonstrate what was possible rather than seriously communicate with denizens who, if they even existed, would take over 50,000 years to call back.

---

Explore the Mathematics

These sections will define in more detail some of the mathematics used in Modulo Universe.  Readers should consider skipping as desired.

Definition of Prime number:  A natural number p > 1 is prime if it is only divisible by itself and 1.

Definition of Composite number:  A natural number c is composite if it has at least one more divisor other than itself and 1 (i.e. it isn’t prime).

So why are primes so fundamental in mathematics?  This next theorem explains why:

The Fundamental Theorem of Arithmetic:  Every integer i > 1 can be represented uniquely (apart from order) as a product of one or more prime numbers.

In other words the prime numbers represent fundamental and indivisible building blocks for the positive integers.  For example 20 = 2 x 10 = 2 x 2 x 5.  32 = 4 x 8 = 2 x 2 x 2 x 2 x 2.

Put another way:  Every positive integer n > 1 can be represented in exactly one way as a product of prime powers.

This leads me to one of the most beautiful and elegant proofs in mathematics – Euclid’s infinite primes.  One of the great appeals of mathematics over other human creations is its eternity.  By this I mean that once you prove something remarkable in mathematics – as Euclid did over 2000 years ago – it’s there forever.  Whereas theories in physics, chemistry and astronomy undergo a constant revision, mathematics is like an indestructible and ever-growing vault.  The literature from this epoch of history might loose some of its original meaning due to the filter of modern culture, yet the logic of greek mathematics cuts through the intervening millennia with a piercing clarity.

I urge you to follow along with this proof as its relatively easy, even without mathematical training.

Theorem (Euclid 300 B.C):  There are an infinite number of primes.

Proof:  Suppose there’s isn’t an infinite number of primes!  Then there must be a biggest prime number – let’s call that P.  We can then make a list of all the known primes including P:

p1, p2, p3, p4,…., P

So far so good.

Now suppose we multiply our list of known primes together to make a number N:

p1.p2.p3…..P = N

Now this number N can’t be prime because it has all these prime divisors.  But what if we add 1 to N?  Let’s call this new number M.

M = N+1

Now M, like any other natural number, must be either a prime or a composite number.  If it’s the former we’ve found another prime larger than N contradicting our assertion.  If it’s a composite then it can be expressed as a product of prime factors.  However none of the primes listed can divide M so there must exist other primes not in our list.  In both cases we’ve contradicted our initial claim so there must be an infinite number of primes!

Definition of Semiprime:  A natural number l is semiprime (or bi-prime) if it is the product of two prime numbers p and q (l = p x q = q x p).

From this definition it’s clear that the square of any prime number must be semiprime and therefore the largest known semiprime is also, conveniently, the square of the largest known prime.  Large semiprimes are popular in encryption systems due to the simplicity of making them (grab two primes and multiply them together) but complexity of factorising them with no prior knowledge.

---