Significance and Application

Primes are used extensively in cryptography. Cryptography involves writing and solving codes as it is the study of secure communication. Two simple cryptography examples that will be discussed are additive and multiplicative ciphers.

When beginning a cipher, each letter in the alphabet is assigned a position. A basic example is assigning the letter $a$ the first position, $b$ the second, all the way down to $z$ in the 26th position. Positions can be assigned in reverse, or perhaps $a$ can be the fifth position, $b$ the sixth, $c$ the seventh all the way down to $z$ which would then be in the fourth position. An additive cipher uses a simple added key mod 26 to map a plaintext letter $a$ (denoted by lowercase letters) onto an encoded letter, say $F$ (denoted by capital letters). In this example, assuming that $a$ is in position 1, the additive key would be $5$ since F is the 6th letter of the alphabet. Then, to determine the position of the other encoded letters, one would add 5 to the plaintext letter's position mod 26. Use this method to determine what plaintext letter $v$ will map onto. It is the 22nd letter of the alphabet, so $22+5=27 \equiv 1 mod 26$. Therefore, $v$ becomes encoded to $A$.

To break the code and translate the encoded letters back to the plaintext letters, you need the additive inverse. The additive inverse is whatever number when, added to they key, results in $0 mod 26$. In the above example with additive key of 5, the additive inverse is 21 since $5+21 = 26 \equiv 0 mod 26$.

Multiplicative ciphers are slightly more complicated and begin to employ the important properties of prime numbers. When multiplicative ciphers, one multiplies the plaintext letter position by the multiplicative key to find the encoded position. Using the same key of 5, plaintext letter $a$ would correspond to encoded letter $E$, $b$ (2nd in the alphabet) to $J$ (10th in the alphabet), $c$ (3rd in alphabet) to $O$ (15th in alphabet), and so on. This works becausse 5 is a prime number. Note that it also works if they key is relatively prime to 26, like 9, but for simplicity's sake only prime cases will be discussed.

What happens, then, when the key is not prime, or relatively prime to 26? Consider the example with multiplicative key 4.

Plaintext $a$ corresponds to $D$ because $1 \cdot 4 =4 mod 26$ . Plaintext $b$ corresponds to encoded $H$ because $2 \cdot 4 = 8 mod 26$. This key is without issue until plaintext $n$. Plaintext $n$ is the 14th letter in the alphabet. Then $14 \cdot 4 = 56$, which is congruent to $4 mod 26$, so $n$ corresponds ot encoded letter $D$. This presents an issue becaue plaintext $a$ is already mapped onto $D$. Thus, multiple plaintext letters correspond to the same encoded letter, so this code is ineffective (Lewand, 2001).

So why is it important that the multiplicative key is a prime? Remember the property that in $[\mathbb{Z}]_p$ where $p$ is a prime, if $ab=0$, then either $a$ or $b$ is zero. There are not multiple solutions ot the equation like where $p$ is not a prime. Therefore, in cryptography, when using a prime or relatively prime multiplicative key, there won't be multiple cases where differing plaintext letters correspond to the same encoded letter.

Like in the case of an additive cipher, cracking a code with a multiplicative key requires a multiplicative inverse. A multiplicative inverse is the number that, when multiplied by the key, results in $1 mod 26$. In the case where the multiplicative key is 3, for example, the multiplicative inverse is $9$ since $3 \cdot 9 = 27 \equiv 1 mod 26$.

Additive and multiplicative ciphers are examples of secret key cryptography. A pair sending each other encoded messages would need to have an agreed upon key, unknown to anyone else, for the code to be effective. Modern method cryptography also has a public key. Primes are essential for public key cryptography because they are very difficult to find and predict, especially when very large. Encoding messages using public key cryptography utilizes very large prime numbers. Two large primes, $p$ and $q$ are multiplied together, resulting in $N$. Then, there is needed a number $e$ that is relatively prime to N, and a number $d$ such that $de \equiv N$. The numbers $N$ and $e$ are made public, everything else secret. The receiver of the code has the private key necessary to easily decode the message. It's simple to multiply two large numbers together to encode a message, but it's very difficult to take a large number and determine which primes are its factors. Therefore, even if the key is public, it still takes a long enough time break the code that the message is considered computationally secure. Multiple supercomputers could take up to a month factoring a 140-digit number (Languasco & Perelli, 2003).

Use this Desmos Activity to practice additive and multiplicative ciphers!

A famous example of using prime numbers in cryptography is Alan Turing and the people of Bletchley Park's work to break the German Enigma code machine. Turing had an incredible mind fascinated by number theory and by prime numbers in particular. These interests led him to develop the first stored-program digital computer. Luckily for Turing, public key cryptography wasn't available during World war II, because if today's supercomputers take hundreds of years to break public key codes, it is doubtful that even he would have been able to crack the German code as much as he did (Booker, 2016).





Prime numbers remain some of the most sought after and difficult to find numbers. Numerous mathematicians still devote their time to discovering new prime numbers. Primes are used in keeping online information secure, banking information protected, and much more. Something as seemingly simple as multiplying two big numbers together is the bawsis for the safety of millions of people's information. Not only are prime numbers the building blocks of every number conceivable, they are also the building blocks of security.