You may be wondering where modular arithmetic came from, this is not just any math after all. As mysterious as modular arithmetic it did not always exist, this miraculous math was invented. Although we do not have an exact date for when this math first arose we do know that there were traces of ideas about it. Back 1500 years ago. From Euclid’s Elements we know that the Greeks had an algorithm to generate all whole number solutions. Furthermore over 1800 years ago contained within the Chinese text Sun Zi Suan Jing were statements which are now used and considered as The Chinese Remainder Theorem! But since it is hard to know who did what in the past when we talk about the modern modular arithmetic that we use today it is Carl Friedrich Gauss that is credited with its introduction in his book Disquisitiones Arithmeticae during the 1800’s. This introduction spread the ideas of modern modular arithmetic became widely known throughout the world. The spread of this knowledge leads us to the use of modern modular arithmetic the most famous being Cryptography.
Now for the finale, I would like to introduce you to the world of Cryptography. In Greek cryptos means “secret or hidden”. Thus, the name explains its meaning, Cryptography is the art of coding messages so that only those that know the key can understand it. To begin I would like to start by sharing some definitions that will help you understand concepts in Cryptography.
Definitions
Plaintext: The input for encryption algorithms, can take the form of text, audio, video, and images. This is the original message before being coded
Ciphertext: The output of encryption processes, and input for decryption processes. This is the message after being coded.
Encryption: The process of encoding a message or information using some type of method of scrambling a plaintext message to create a ciphertext.
Key : A piece or pieces of information that determines the functional output of an encryption.
Decryption: The process of taking encrypted text and converting it back to plaintext.
Cipher: An algorithm that is used for performing encryptions or decryptions. There are 3 main types of substitution ciphers that we will talk about these are; Additive, Multiplicative, and Affine.
Additive Cipher: An algorithm that specifically uses modules addition for performing encryptions or decryptions it does this by shifting each letter of the plaintext alphabet to obtain a Ciphertext alphabet.
The History
To understand Cryptography we have to go back to its beginnings and delve into its history. The first well known cipher to be widely used was the Caesar cipher around 58 BC. The Caesar cipher was a simple Additive Cipher. Caesar simply shifted the letters of the plaintext to encrypt the plaintext letter to be ciphertext. The relevance of doing this was to pass secret messages during wars, so that commands could be given without the enemies knowing the command if the message was intercepted. This was a huge advantage to those who used encrypted messages during wars. However, a simple Additive Cipher is not a strong lock, in other words, it’s easy to crack. Around 800 years after Caesar time an Arab mathematician, Al-Kindi exposed the secrets of cracking Caesar cipher to the world. He used a method of coded cracking called frequency analysis. Frequency analysis is the process of studying letters or groups of letters within a ciphertext to attempt to partially reveal the message. Try out this applet from Khan Academy to familiarize yourself with the Caesar cipher also try out the activity Frequency Fingerprint Exploration to familiarize yourself with decoding using frequency analysis.
| Caesar Cipher Exploration |
| Frequency Fingerprint Exploration |
Later the Affine Cipher was more commonly used as it was stronger than the Caesar cipher. The Affine Cipher uses a formula where the key consists of two numbers, we’ll represent these two numbers in their general form as a and b. So to encrypt using the Affine Cipher we first assign each letter in the alphabet to a number. Then for c representing any number (most English speakers use 26=m since there are 26 letters in the alphabet), p representing the letter in its number form and c representing the ciphertext letter we use the formula c ≡ ap+b (mod m) where 1 ≤ a ≤ m and 1 ≤ b ≤ m . With this formula one is able to encrypt a message using the Affine Cipher. Now if one wants to decrypt a message encrypted with the Affine Cipher then the formula is the inverse of the encryption formula which is, p ≡ a-1 (c-b) (mod m). This decryption formula works because a
Throughout the years ciphers became more and more advanced. After World War II, the United States and the Soviet Union entered the Cold War. During this time the rise of public-key cryptography began. Public-key cryptography is the encryption method that takes a pair of a public and a private key and then uses an algorithm for secure data communication. The benefit of this is that two parties can create a personalized strong encryption and decryption process without meeting. The basis of public-key cryptography is modular arithmetic. So putting that together the parties agree on a prime number such as 17. Then the primitive root of that prime number is found. (A primitive root b is a primitive root mod p if for every integer a coprime to b, there is an integer k such that bk ≡ a ). In this case, the primitive root is 3 then 3 becomes known as the generator. When we raise 3 to any exponent
Now I will explain the Diffie-Hellman Key Exchange, as two parties agree on using the prime number 17 and its primitive root 3. Then one party picks a number lets say 15 and performs the operation 3
So why is Cryptography so important? Well, it is extremely beneficial in warfare. During WWII vital information was passed via ciphertext by all major powers. These encryptions were performed by machines, the most famous were the Enigma in Germany and the SIGABA in the United States. In WWII both processes for encryption and decryption evolved becoming more specificated. Due to the help of modular arithmetic, and the work of many decoders and coder, the Allies advanced the ending of the war.
If you are interested in learning more about how Cryptography was used in WWII then check out this website:
Nowadays we may not be in a World War but modular arithmetic still proves to be useful. For international banking money, books and etc the processes of transition from one country to another were becoming quite complicated. Numbers were being misplaced and orders were being mixed up leading to some situations people could only describe as a disaster. So it’s no surprise that people would want this fixed, and thus we now have the International Standard Book Number (ISBN), and different encryption and decryptions for banking situations. The ISBN 10 uses a particular method called the reverse weighting system. This involves taking a number and multiplying the first digit by 10, the second by 9, the third by 8 and so on until the 10th digit is multiplied by 1. Where the sum of these digits should be divisible by 11. The ISBN 13 uses a method where all the odd place digits are added and all the even place digits are added and the sums multiplied by 3 and then added. This number is divisible by 10. Because ISBN 10 is divisible by 11 and ISBN 13 is divisible by 13 modular arithmetic can be used to check for errors and violations. These processes are also useful for bank account numbers, credit cards and etc especially since nowadays many people use digital money and without the right encryptions and decryptions, money would not be safe. If you are interested in seeing examples of how this is used then check out this website it will help guide you through some specific examples:
While there are many uses to modular arithmetic I am afraid this journey is coming to an end. After all, this was just an introductory website to modular arithmetic and the goal of showing you the basics along with some cool history and application has been completed. I hope you enjoyed learning about this invented mathematics and gained an interest in the uses of modular arithmetics and its particular ways of operation. Thank You for joining me on this wild ride, if this website interested you and you’d like to learn more cool math topics check out my colleague’s webpages at the following link!