The semiprime directive

[Sheldon and Penny are working a long-division problem on side-by-side whiteboards.]
Sheldon: I’m okay. I’m okay. I’m not okay. [He falls over.]
Leonard: Get up! We can’t lose at math.
Penny: [finishing] 37!
“The Re-Entry Minimization” (Season 6, Episode 4)

The scene is part of a “friendly”parlor game competition, and its highly unusual outcome is due mainly to the fact that Sheldon and Penny are both extremely dizzy, having spent a full minute spinning in circles. But everyone’s so astonished at Penny’s victory that nobody comments on the many interesting facts about the particular numbers involved.

The long division problem given to both of them is 851 ÷ 23 = 37, and as it happens both 23 and 37 are prime numbers. A prime number is a positive integer that has exactly two positive integer factors: itself and 1; in other words, there is only one pair of numbers that can be multiplied together to give that number. So 17 is a prime number, because it can be divided evenly only by 1 and 17, and 19 is prime, because it can be divided evenly only by 1 and 19, but 18 isn’t, because it can be divided evenly by more than two numbers: 1, 2, 3, 6, 9, and 18. The lowest prime number is 2, which is also the only even prime number, since all larger even numbers can be divided by 2 as well as by themselves and 1.

A number that is the product of two primes is called a semiprime. Since a semiprime can be divided evenly by more than just itself and 1, it’s not a prime, but it’s “nearly”a prime. A semiprime that is the square of a prime has only three distinct factors (for example, 9, which is the square of 3, can be divided only by 1, 3, and 9), while all other semiprimes have only four (for example, 15 can be divided only by 1, 3, 5, and 15).

In the field of cryptography, semiprimes are of more than mere academic interest. The “public key”encryption methods used by many, many online and electronic services assign two large, unique prime numbers to each individual. He keeps those numbers private but publicizes their product, a large semiprime. The semiprime and its factors form two ends of a bidirectional encryption machine: any message encrypted via one can be decrypted via the other. Anyone can send that person a secret message by using the public semiprime to encrypt it, since only the two private factors will decrypt it. Conversely, a person can prove his own identity by encrypting any message via his two factors; the fact that his semiprime (and no other) will decrypt it proves that he is in possession of the factors.

The security of such a system depends on the fact that although it takes very little time for a modern computer to come up with two extremely large prime numbers and multiply them together, the reverse operation (factoring a large semiprime into its two constituent primes) can only be done by extremely slow trial and error. There are tricks for determining whether a number is evenly divisible by various small numbers (e.g., a number is divisible by 2 if it ends in 0, 2, 4, 6, or 8; it’s divisible by 3 if the sum of its digits is divisible by 3; it’s divisible by 5 if it ends in 0 or 5), but there aren’t tricks for most large numbers.

And large means large: the semiprimes used in encryption systems are typically several hundred decimal digits long. Even with a vast network of computers, it could easily take billions of years to stumble upon the factors of a single such semiprime. (At one time, when encryption methods used primes with fewer digits, it was suggested, not entirely jocularly, that it might be feasible for every television set manufactured in China to contain a chip that could receive public keys to be cracked, try dividing random numbers into them, and if it hit upon a solution, flash an on-screen message instructing the loyal citizen to run to the telephone and recite the following series of digits.)

If large quantum computers ever become feasible, it’s expected that they’ll be able to factor large semiprimes in a very short amount of time, leaving encryption schemes vulnerable. A quantum computer works by using quantum bits of information (called qubits, pronounced CUE-bits) for its inputs, outputs, and internal values. Unlike a normal (“classical”) bit, which can only take on one of two values (representing 0 and 1) at a time, a qubit can represent both a 0 and a 1 at the same time. You can only give a classical computer one combination of 0s and 1s to process each time you run its program, but a quantum computer acts on every possible combination of 0s and 1s all at once. Various four-bit prototype quantum computers have been built and have successfully factored the semiprime 15 into 3 and 5. Such a machine behaves as though it were dividing 15 not by one candidate number at a time but by all candidate numbers simultaneously.

Interestingly, taking the digits of 15 and reversing their order yields 51, which is another semiprime (51 = 3 × 17). A semiprime that is the decimal reversal of another semiprime is, rather imaginatively, called an emirpimes. The plural of emirpimes is emirpimeses, or alternately semirpimes because it makes such a cute almost-palindrome (a word or phrase that reads the same backwards as forwards). The dividend in Penny and Sheldon’s division problem, 851, is also an emirpimes, since its decimal reversal (158) is another semiprime (having 2 and 79 as its only nontrivial factors).

Decimal reversals are of special interest largely because we write numbers in base ten, which is because we happen to have ten fingers to count on. (This is in contrast to primes and semiprimes, which are features of numbers regardless of the base in which they’re expressed.) The 37 that Penny gets as her result is interesting for another reason: it’s an emirp: a prime that is the decimal reversal of another prime. (The divisor in the problem, 23, is a prime but not an emirp, because its reversal, 32, isn’t prime.)

So the division problem, already remarkable because Penny solves it and Sheldon doesn’t, is even more remarkable because it represents the last step in factoring a semiprime, and more remarkable still because it features an emirpimes and an emirp. In fact, the reversal of this very emirp (73) is prominently featured in this very scene. It appears on the front of Sheldon’s T-shirt, harking back to an earlier episode in which he insists that 73 is “the best number,” a claim he justifies with (among others) the fact that it’s an emirp.1

Whether all these connections represent a deliberate wink on the part of the show’s writers or science consultant is unknown, but in the words of Ernest Hemingway, “isn’t it pretty to think so?” 2

ENDNOTES

1. “The Alien Parasite Hypothesis” (Season 4, Episode 10)

2. Ernest Hemingway, The Sun Also Rises (New York:Charles Scribner’s Sons, 1926).