The power of prime numbers in computing

Everyone knows that a prime number is one that cannot be made by multiplying other whole numbers together. This deceptively simple attribute hides a world of complexity that has engaged mathematicians ancient and modern. This quality of primes also has essential applications in computer science and the realm of cryptography.

The Fundamental Theorem of Arithmetic

Like its name implies, the Fundamental Theorem of Arithmetic says something profound about the way numbers behave. It says that every number can be described as the product of a specific set of primes multiplied together. This is a curious result that comes from the basic definition of prime. I say “curious” because it is at once a surprising and useful fact: a somewhat hidden but also almost direct outcome of the definition of primeness.

This kind of mental maneuver, where you take the properties of mathematical objects and keep extrapolating out their ramifications, leads eventually to essential cryptographic algorithms like Diffie-Hellman, RSA, and Elliptic curve.

The Fundamental Theorem of Arithmetic tells us that every number (besides 1) is either prime itself or the unique product of primes. As a simple example, consider the number 25:

25 = 5 * 5

In other words, 25’s “prime signature” is 5 * 5. Only 25 has that signature and 5 * 5 only comes out to 25. If you think about the entire range of whole numbers—that is, the infinitude of integers—you’ll see that the theorem guarantees us an enormous space of uniquely identifiable instances.

Take an arbitrary number and ask the question: What is its prime factorization? That is, what is its prime signature? The answer to that question turns out to be very difficult, especially when compared with the inverse operation, of creating a number that is the product of two known primes.

The fundamental theorem underpins this difficulty because it means in the entire space of numbers, each number has but one set of prime factors. It also means that brute-force attacking such problems is not feasible. For 25, of course, you can just figure out 5 * 5, but what about a number with a thousand digits? It is computationally unfeasible to guess at the factors.

Primes in hash functions

Another interesting area where primes pop up in coding is creating hash functions. In a hash function, the primary job is to take an input and transform it into a number that stands in its place. The number is a reduction of the overall input, and this fact makes it useful for many things like checksums and structures like hashtables.

Hashing for a hashtable (the hash function for the object being placed into the collection; i.e., Java’s hashCode) uses a modulo of a constant, and that constant is recommended to be a prime. In that case, using a prime for the constant can help reduce the likelihood of collisions. That’s because the primeness of the number makes for a more even distribution of modulus, because there are fewer common denominators with the hashtable’s function.

For the same reason, a prime on the hashtable “bucket count” helps prevent asymmetric collisions. In essence, using primes on the hashing constant and bucket count helps to ensure a good random distribution of items in buckets by reducing the likelihood of significant relationships between the two.

The discussion of this relationship on Stack Overflow is a nice launch pad for further investigation on the topic of primes and hashes.

Another fertile ground of primes and hashing working together is in functions like SHA-256 and MD5. These are used all over the place for things like hashing passwords and as elements of cryptocurrency. SHA 256 from scratch with pen and paper is a fun walkthrough of doing SHA-256 by hand, as part of the process of building a Bitcoin key from scratch. It highlights the role primes play.

Primes and modular math

Another fascinating area of math with many implications for programming is modular math. This is sometimes called “clock math” because it takes a finite range of numbers and counts only what is leftover. An example is the way we use the numbers from 1 to 12 on the clock and only use the excess, so that 13 hours becomes 1 o’clock (assuming we begin at 12).

Modular math crops up in many areas, especially cryptography, and using primes with it is often necessary to attain the necessary properties, like having a multiplicative inverse. Cambridge University Press has a great breakdown of primes as moduli.

Sieve of Eratosthenes

Now let’s flip things around a bit and look at how coding helps us handle and understand one of the classic problems of math: discovering primeness. An ancient algorithm was described by Eratosthenes, working in the 3rd century BC. The algorithm, now called the Sieve of Eratosthenes, provides a set of steps for finding all the primes for a given number.

The basic idea behind the algorithm is to take a number, n, and through a series of passes, eliminate the non-prime numbers. What remains when you’re done is the set of primes you are after. There are many possible ways to refine this process, but the basic modern version of the sieve begins by taking 2 and noting it as prime, then finding all the even numbers up to n, noting them as not prime. Then, we move to 3 and perform the same thing for multiples of 3. Continuing on, we do the same for all the numbers up to n, only skipping those numbers we have already noted as non-prime.

This is a very ancient example of an algorithm, and a programmer’s ability to put it into an executable format is a superpower, for sure. Here is a version in JavaScript (from Wikipedia):

function getPrimeNumbers(max) {
	// A list of booleans where index 2 being true corresponds to 2 being prime
	var isPrime = [];

	// Initial population of isPrime
	for (var i = 0; i < max; i += 1) {
		if (i != 0 && i != 1) {
			isPrime.push(true);
		}
		else {
			isPrime.push(false);
		}
	}

	// Iterate over entire list
	// Element => true if index is prime else false
	for (var i = 0; i < max; i += 1) {
		if (isPrime[i]) {
			for (var j = i + i; j < max; j += i) {
				isPrime[j] = false;
			}
		}
	}

	var primes = [];

	// Assemble list of primes
	for (var i = 0; i < max; i += 1) {
		if (isPrime[i]) {
			primes.push(i);
		}
	}

	return primes;
}

Many other approaches to discovering the primes for a given field have been developed, including the Sieve of Atkin and fascinating approaches to probabilistic testing of primality like the Miller–Rabin primality test (seen here in C++). Its probabilistic nature means Miller-Rabin is fast—O(k log3 n)—but may sometimes give false positives.

So, the algorithm for finding primes is well-known and even simple to code. It is astounding that despite the initial simplicity and millennia of attention from some of the most brilliant mathematical minds, the characteristics and nature of primes remain a mysterious and active area of research.

The Riemann Hypothesis

One of the most interesting unsolved problems in math is the Riemann Hypothesis (here’s the codebase for calculating it). Riemann was a student of Gauss, whose name you might know from the “Gaussian blur” in software like Adobe Photoshop. Gauss devised a function to estimate the occurrence of primes, known now as the Prime Number Theorem. Reimann’s function, called the zeta function, incorporates complex numbers into its infinite series and increases the accuracy of the Gauss theorem. The Riemann Hypothesis sheds light on the fundamental behavior of numbers, and how it impacts computer science is an open question. Proving the hypothesis is perhaps the most prominent effort in theoretical math.

Alan Turing is probably the most well-known figure at the point where mathematics and computing meet. (Turing’s paper on the computability of numbers provided the conceptual basis for modern computers.) He had a long and profound relationship with primes and in particular the Riemann Hypothesis. He was working on building a Riemann Hypothesis machine when he was interrupted by the outbreak of World War II, where he applied lessons from that endeavor to the task of constructing an analytical machine to crack the Nazi cyphers.

Turing’s final paper addressed the Riemann zeta function.

Prime numbers in quantum computing

Quantum computing may one day threaten current cryptographic practices in a systematic way. One of the chief reasons is that qubits may—if the hardware can be worked out—eventually be able to rattle off prime numbers, reducing the computation time required to perform Diffie-Hellman-like functions in the reverse direction.

Conclusion

This article has surveyed many of the areas where prime math and computer science come together. It’s an incredibly interesting area because it begins with such simplicity, but ties directly into highly sophisticated realms of number theory that are at the forefront of research. Programming and primes will continue to inform each other in a back-and-forth of influences for as long as we are using computers. This is especially true in cryptography, where a central facet is the nature and behavior of primes.