{
"cells": [
{
"cell_type": "markdown",
"id": "87a5ecbc",
"metadata": {},
"source": [
"# An introduction to modular arithmetic\n",
"\n",
"Most of my tech-savvy peers have heard of the RSA algorithm or RSA certificates.\n",
"It is commonly used to generate ssh key pairs, for example.\n",
"\n",
"```bash\n",
"ssh-keygen -t rsa -f mykey\n",
"```\n",
"\n",
"The command above produces two files, a private and public key.\n",
"\n",
"```shell\n",
"ll mykey*\n",
".rw------- 2.6k djustice 7 Aug 18:25 mykey\n",
".rw-r--r-- 586 djustice 7 Aug 18:25 mykey.pub\n",
"```\n",
"\n",
"You can share the public key, but the private key must be kept secure (also note the file permission differences).\n",
"Public means public, too!\n",
"You can see someone's public key on Github by appending `.keys` to their username.\n",
"It may respond with `ssh-rsa ...` or something else depending on the algorithm used to generate the key (EdDSA is common).\n",
"\n",
"\n",
"```shell\n",
"curl https://github.com/some-user.keys\n",
"ssh-rsa lots-o-chars...\n",
"```\n",
"\n",
"Many of us in the tech world have seen this base64-encoded soup daily, but have you ever peeked under the hood?\n",
"I think the RSA algorithm is one of the more tractable subjects in cryptography, and it opens the door to many other ideas in number theory.\n",
"\n",
"The RSA algorithm works because of the properties of prime numbers and modular arithmetic.\n",
"I will start with the latter, and I hope to work the former into another post as I develop this topic.\n",
"My goal is to spark an interest, not to provide a rigorous discussion.\n",
"There is plenty of jargon to discuss, so please try to work through it.\n",
"There is a reason for many of these terms, and I will do my best to justify them as we go.\n",
"\n",
"We will only be working with integers in this article, so think of the set of whole numbers from -∞ to ∞.\n",
"For example: {..., -3, -2, -1, 0, 1, 2, 3, ...}.\n",
"This set is known in mathematical circles as ℤ.\n",
"The symbol is used because it represents a precise idea in a compact space.\n",
"\n",
"## Clock arithmetic\n",
"\n",
"Some mathematicians don't like the clock metaphor for modular arithmetic, but I think it is a great starting point.\n",
"In my own experiences, I have had the most success explaining this subject to other people using clocks, and the comparison doesn't have any sharp edges that will confuse you later on.\n",
"\n",
"![wall clock](/images/clock.jpg \"wall clock\")\n",
"\n",
"Starting with a 12-hour wall clock, we will create a number system called \"the integers modulus 12\".\n",
"That is quite a bit to write several times in a row, so you will often see ℤ mod 12, or simply \"mod 12\".\n",
"This wouldn't be a techy post without some code!\n",
"The modulus function is essentially the remainder of division by some number; in the current case, 12.\n",
"Most programming languages perform the operation using the binary operator `%` (binary means it takes two arguments)."
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "b0b9eeb1",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The remainder of 1 divided by 12 is 1.\n",
"The remainder of 2 divided by 12 is 2.\n",
"The remainder of 3 divided by 12 is 3.\n",
"The remainder of 4 divided by 12 is 4.\n",
"The remainder of 5 divided by 12 is 5.\n",
"The remainder of 6 divided by 12 is 6.\n",
"The remainder of 7 divided by 12 is 7.\n",
"The remainder of 8 divided by 12 is 8.\n",
"The remainder of 9 divided by 12 is 9.\n",
"The remainder of 10 divided by 12 is 10.\n",
"The remainder of 11 divided by 12 is 11.\n",
"The remainder of 12 divided by 12 is 0.\n",
"The remainder of 13 divided by 12 is 1.\n"
]
}
],
"source": [
"for n in range(1, 14):\n",
" print(\"The remainder of {n} divided by 12 is {r}.\".format(n=n, r=n % 12))"
]
},
{
"cell_type": "markdown",
"id": "933a1571",
"metadata": {},
"source": [
"Those first few lines can trip people up.\n",
"Why is 1 the remainder of 1 divided by 12?\n",
"It is because `12 * 0 + 1 = 1`.\n",
"Pay close attention to the last few values.\n",
"The remainders don't continue to increment without bound, they roll over back to zero!\n",
"\n",
"Okay, I will admit that it probably isn't that exciting.\n",
"Most of us should remember these facts from grade school.\n",
"Continuing our introduction (or refresher), do you recall that we can perform arithmetic in this number system?\n",
"Ask yourself, if the hour hand is on 5 right now, what time will it be in 37 hours?\n",
"The answer is\n",
"\n",
" (5 + 37) mod 12 = 42 mod 12 = 6 o'clock\n",
"\n",
"Here is another way to think of it.\n",
"`37 mod 12 = 1` and `5 + 1 = 6`.\n",
"Is that a coincidence?\n",
"It is not!\n",
"\n",
"What about multiplication; does that work in our modular system?\n",
"What does `5 * 9` hours equal?\n",
"\n",
" (5 * 9) mod 12 = 45 mod 12 = 9 o'clock\n",
" \n",
"This may seem a bit contrived, but there are practical applications.\n",
"It is 2 o'clock when you start your delivery run.\n",
"You drive 3 hours north to the warehouse, then make 3, 3-hour round-trips to a remote depot and back.\n",
"What time do you return to the warehouse?\n",
"\n",
" [(2 + 3) + (3 * 3)] mod 12 = (5 + 9) mod 12 = 14 mod 12 = 2 mod 12 = 2\n",
"\n",
"This is fairly basic number theory; things you most likely already know.\n",
"If we dig a bit deeper, an interesting structure emerges.\n",
"\n",
"![mod12](/images/mod12.png \"mod 12\")"
]
},
{
"cell_type": "markdown",
"id": "17f49147",
"metadata": {},
"source": [
"Consider the numbers on the ray originating at 4.\n",
"\n",
" {..., -20, -8, 4, 16, 28, 40, ...}\n",
"\n",
"When performing arithmetic in `mod 12`, we can substitute any of these numbers with each other and achieve the same result.\n",
"Mathematicians call this an _equivalence class_.\n",
"The terminology is necessary because we are trying to describe a precise idea.\n",
"Clearly, -20 and 40 are **not** equal to one another.\n",
"However, in the `mod 12` number system, they are equivalent when we perform computations.\n",
"This is typically written as `[4]` where\n",
"\n",
" [4] = {..., -20, -8, 4, 16, 28, 40, ...}\n",
"\n",
"Each number `n` in this set is _related_ to ℤ by `n mod 12 = 4`, or more compactly: `{n | n ∈ ℤ, n mod 12 = 4}`.\n",
"\n",
"Look at a few more of these equivalence classes:\n",
"\n",
" [0] = {..., -24, -12, 0, 12, 24, 36, ...},\n",
" [1] = {..., -23, -11, 1, 13, 25, 37, ...},\n",
" [2] = {..., -22, -10, 2, 14, 26, 38, ...},\n",
" ...\n",
" [11] = {..., -13, -1, 11, 23, 35, 47, ...}\n",
"\n",
"Start at any column and make your way down subtracting 1 each time.\n",
"When you get to the bottom, move one column to the right.\n",
"Notice anything interesting?\n",
"Every single number in ℤ is represented in one of these... partitions.\n",
"Division already has a definition in mathematics, so we will use the phrase _partition_ to describe these collections of numbers.\n",
"The really neat part is that this system of partitions representing all the integers works in _any_ modular base!\n",
"My teenage son who has no use for math even admitted that this is pretty cool, so put that in your pipe and smoke it!\n",
"\n",
"## Homework\n",
"\n",
"This wouldn't be an article on math without some homework.\n",
"Use your favorite search engine and read about the Caesar cipher.\n",
"Write an implementation in your favorite language and see if your friends can break it.\n",
"Just don't send it to me; I am terrible at cryptography.\n",
"😂\n",
"You can strengthen the cipher by using a random permutation of the alphabet, but both ends of the conversation must use the same permutation.\n",
"This is still susceptible to frequency attacks, so don't use it to send GPG keys over the internet.\n",
"\n",
"## Next steps\n",
"\n",
"This subject is inspired by the work I did on my research paper to earn my B.S. in Applied Mathematics.\n",
"My plan is to translate it in a way that will be consumable by most programmers (really anyone) who have a little bit of mathematics background.\n",
"\n",
"If I don't get hit by a bus, I hope to write:\n",
"\n",
"- [Prime numbers, the Extended Euclidean Algorithm, and the GCD](https://blog.wificidr.net/posts/prime-numbers-the-extended-euclidean-algorithm-and-the-gcd/).\n",
"- [The Modular Inverse, an attempt to explain it without hand-waving](https://blog.wificidr.net/posts/the-modular-inverse/).\n",
"- How RSA works (the math, not the code).\n",
"\n",
"I am going to provide a detailed guide, but it is up to the reader to sit down and draw their own conclusions about how these things work.\n",
"Math is not a spectator sport!\n"
]
},
{
"cell_type": "markdown",
"id": "d613bccc",
"metadata": {},
"source": [
"## References\n",
"\n",
"Clock photo: https://commons.wikimedia.org/wiki/File:B_%26_HB_Kent_Pocket_Watch_(52584138758).jpg"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.11.5"
},
"nikola": {
"category": "",
"date": "2023-07-31 18:42:56-05:00",
"description": "",
"link": "",
"slug": "modular-arithmetic",
"tags": [
"math",
"rsa"
],
"title": "Modular arithmetic",
"type": "text"
}
},
"nbformat": 4,
"nbformat_minor": 5
}