{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Modular Arithmetic" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "_Modular arithmetic_ is a system for performing arithmetic in which computations are limited to a finite set with a \"wrap-around\" effect.\n", "\n", "An everyday example of modular arithmetic is used as the time displayed on a clock. For example, 1 hour past 1 o'clock is 2 o'clock and 5 hours past 5 o'clock is 10 o'clock, but 7 hours past 7 o'clock is 2 o'clock. In symbols:\n", "\n", "

\n", "\\begin{gather*}\n", "🕔 + 🕔 = 🕙 \\\\\n", "🕖 + 🕖 = 🕑\n", "\\end{gather*}\n", "

\n", "\n", "This is because 12 o'clock is treated as \"zero\"; if you go past tweleve o'clock then what matters is _how much_ you went past 12 o'clock. In other words, you can remove all multiples of 12 hours from the time to get the \"clock\" time.\n", "\n", "In modular arithmetic this is written as:\n", "\n", "

\n", "\\begin{gather*}\n", "5+5 \\equiv 10 \\pmod{12} \\\\\n", "7+7 \\equiv 2 \\pmod{12}\n", "\\end{gather*}\n", "

\n", "\n", "While at first this might seem like a mere curiosity, in fact modular arithmetic has an enormous number of applications. For example, it underlies the mathematics used to secure credit card information on the internet." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Formal Definition" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Given integers $a$, $b$, and $m$ we say that $a$ and $b$ are _congruent modulo $m$_ and write\n", "\n", "$$a \\equiv b \\pmod{m} \\notag$$\n", "\n", "if $b-a$ is a multiple of $m$. Alternatively, if both $a$ and $b$ have the same remainder when divided by $m$.\n", "\n", "For example, $14\\equiv 26 \\pmod{12}$ because $26-14=2\\cdot12$.\n", "\n", "Using the notation $a\\bmod m$ to mean the remainder produced by dividing $a$ by $m$ we can check that $14\\equiv 26 \\pmod{12}$ by verifying that\n", "\n", "\\begin{equation*}\n", "26 \\bmod 12 = 14 \\bmod 12 = 2 .\n", "\\end{equation*}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Note on notation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note the notations $a=b\\bmod m$ and $a\\equiv b\\pmod m$ are quite similar and this can be useful because they mean similar things. However, it is important to note that they are saying different things.\n", "\n", "* **In the case $a=b\\bmod m$:**\n", "\n", " Here \"mod\" is being used as a _function_ meaning that $b\\bmod m$ has a single fixed value for fixed values of $b$ and $m$.\n", " \n", " For example, $14\\bmod 12=2$.\n", "\n", "\n", "* **In the case $a\\equiv b\\pmod m$:**\n", "\n", " Here \"mod\" is not a function; the expression $a\\equiv b\\pmod m$ does not define $a$ to be a unique integer but *any* integer that has a remainder of $b$ when divided by $m$.\n", " \n", " For example, $2\\equiv 14\\pmod{12}$ but also $-10\\equiv 14\\pmod{12}$.\n", " \n", "\n", "In mathematics the second notation defines what is known as an _equivalence relation_ that partitions integers into \"equivalence classes\". Every integer belongs to one and only one equivalence class mod $m$.\n", "\n", "For example, mod 2 there are exactly two equivalence classes: the class of even numbers and the class of odd numbers. Equivalence classes in modular arithmetic are also known as _residue classes_." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Unique representative" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It is often useful to have a single unique _representative_ for each equivalence class. In the case of modular arithmetic over the integers it is usually conveinient to define the representative of a class to be the smallest nonnegative integer in the class.\n", "\n", "For example, consider the class of integers equivalent to $14\\pmod{12}$ which is $\\{ \\dotsc, -22, -10, 2, 14, 26, \\dotsc \\}$. This class has the representative 2.\n", "\n", "A list containing all possible representatives is known as a _system of representatives_.\n", "For example, with the above choice of representatives we have that every class is represented by one of the following integers:\n", "$$0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 \\notag .$$\n", "\n", "12 is not a representative as it is in the class represented by 0." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Computing modular expressions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Given an expression involving integers and $+$, $-$, and $\\times$ we can evaluate it modulo $m$ by:\n", "\n", "* Reducing each integer to its representative modulo $m$ so that it lies in the range between $0$ and $m-1$.\n", "* Evaluating each operation on the reduced integers.\n", "* Immediately after each operation reduce its result modulo $m$.\n", "\n", "For example:\n", "\n", "\\begin{align*}\n", "20\\times(-89) + 32 &\\equiv 6\\cdot 2 + 4 &&\\pmod{7} \\\\\n", "&\\equiv 12 + 4 &&\\pmod{7} \\\\\n", "&\\equiv 5 + 4 &&\\pmod{7} \\\\\n", "&\\equiv 9 &&\\pmod{7} \\\\\n", "&\\equiv 2 &&\\pmod{7}\n", "\\end{align*}\n", "\n", "This works because any integer $x$ in a modular expression can be replaced by $x^*+qm$ where $x^*$ is the remainder of $x/m$ and $q\\in\\mathbb{Z}$ is the quotient of $x/m$. Expanding this out (e.g., using the distributivity property for integers) will result in $x$ being replaced by $x^*$ in the expression and any additional terms created by this expansion will multiples of $m$ and can therefore be removed modulo $m$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### How large can the intermediate results get?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "When working modulo $m$ the intermediate results will never become larger than $m^2$. The worst case occurs when multiplying $(m-1)\\cdot(m-1)$ but this is smaller than $m^2$.\n", "\n", "This holds _regardless_ of how large the starting integers are or how many operations there are. This allows us to quickly evaluate complicated expressions in modular arithmetic that would be impractical to evaluate using normal arithmetic." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### What about division?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You **cannot** arbitrarily divide both sides of an equivalence in modular arithmetic by a constant.\n", "Even if $x$, $y$, and $m$ are all divisible by $c$, $x\\equiv y\\pmod{m}$ **does NOT** imply that $x/c\\equiv y/c\\pmod{m}$. For example, $0\\cdot2\\equiv 2\\cdot 2\\pmod{4}$ but $0\\not\\equiv2\\pmod{4}$.\n", "\n", "The \"correct\" way to perform this division would be to cancel $c$ from $x$, $y$, and $m$ simultaneously, e.g., $0\\cdot2\\equiv 2\\cdot 2\\pmod{4}$ implies $0\\equiv 2\\pmod{2}$.\n", "\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Modular inverses" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "As demonstrated above, cancellation using division has to be done carefully. At first it would seem as if we cannot even define division in modular arithmetic. For example, what would $1/3 \\pmod{10}$ even mean? However, we will see it _will_ be possible to give meaning to this expression using modular inverses." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Defining division" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In modular arithmetic we don't deal with _fractions_ of a number or _numerical approximations_ of a number. For example, an equation like $1/3=0.333\\ldots$ is meaningless in modular arithmetic.\n", "\n", "However, we can still _algebraically_ deal with expressions like $1/3$. How can we make sense of this? Let's say we denote the quantity $1/3$ (whatever that means) by $x$. If this expression is to make sense then $3x$ should be $1$. In other words, to determine if we can make sense of $1/3$ we would to find $x$ (if it exists) which satisfies the congruence\n", "\n", "$$3x \\equiv 1 \\pmod{m} . \\notag$$\n", "\n", "By definition, this means that $3x-1$ is a multiple of $m$ (let's say that it is $k$ times $m$ for some integer $k$).\n", "\n", "In other words, in order to find the modular inverse of $3$ (modulo $m$) we want to solve\n", "\n", "$$3x - 1 = km \\qquad\\, \\text{for integers x and k}. \\notag$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Look familiar?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The Euclidean algorithm now comes to the rescue! Rewriting this with $y=-k$, we want to solve\n", "\n", "$$3x + ym = 1 \\notag .$$\n", "\n", "Recall that the Euclidean algorithm gives us a method to find integers $x$ and $y$ such that\n", "\n", "$$3x + ym = \\gcd(3,m) . \\tag{*}$$\n", "\n", "Thus, if $\\gcd(3,m)=1$ then an $x$ exists so that $3x$ reduces to $1$ modulo $m$; $x$ is said to be the _modular inverse_ of 3 and is typically denoted by $3^{-1}$. Note that this assumes the modulus $m$ is clear from the context; to be unambiguous it should be denoted $3^{-1}\\pmod{m}$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that 3 and 10 share no common factors, so their $\\gcd$ is $1$; numbers that share no common factor are said to be _coprime_. The above reasoning indicates that we should be able to determine the value of $3^{-1}$ mod $10$.\n", "\n", "To do this, we run the Euclidean algorithm on $3$ and $10$:\n", "\n", "\\begin{align*}\n", "10\\cdot 1&&&+3\\cdot 0 &&= 10 && \\text{initialization} \\\\\n", "10\\cdot 0&&&+3\\cdot 1 &&= 3 && \\text{initialization} \\\\\n", "10\\cdot 1&&&+3\\cdot (-3) &&= 1 && \\text{subtract $\\lfloor{10/3}\\rfloor=3$ times the second from the first}\n", "\\end{align*}\n", "\n", "Thus, $y=1$ and $x=-3$ is a solution of ($*$).\n", "\n", "Note that $7$ is the unique representative (as previously defined) of the equivalence class containing $x=-3$.\n", "\n", "Indeed, $3\\times7=21\\equiv 1\\pmod{10}$ and we have found an inverse of $3$! Thus, we say that $3^{-1}\\equiv7\\pmod{10}$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Uniqueness" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Say $a$ and $m$ are coprime.\n", "Could it be that there are _multiple_ possible values for $a^{-1}\\pmod{m}$?\n", "\n", "At first glance this isn't crazy, since there _will_ be infinitely many integer solutions $(x,y)$ to the equation\n", "\n", "$$ax + my = 1 . \\tag{1}$$\n", "\n", "However, all solutions $x$ will belong to the same congruence class modulo $m$; thus there is indeed only a single solution modulo $m$ and modular inverses (if they exist) are unique.\n", "\n", "Formally, if $(x_0,y_0)$ is a solution of (1) then _all_ solutions are given by\n", "\n", "$$(x_0-mk, y_0+ak) \\qquad\\, \\text{for k\\in\\mathbb{Z}} .$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Non-existence" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "When $a$ and $m$ are not coprime, $a^{-1}\\pmod{m}$ does not exist because there is no solution of\n", "\n", "$$ax + my = 1 . \\tag{2}$$\n", "\n", "Indeed, any common divisor of $a$ and $m$ will divide the left-hand side of (2) so must also divide the right-hand side, i.e., 1—meaning the divisor must be trivial.\n", "\n", "For example, $x=2^{-1}\\pmod{10}$ does not exist, since $2x+10y$ must be even and cannot ever be 1." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Analysis" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We've already seen that addition, subtraction, and multiplication of numbers at most $m$ can be done in $O(n^2)$ word operations where $n=\\operatorname{len}(m)=O(\\log m)$.\n", "\n", "Furthermore, we've also seen that the extended Euclidean algorithm when run on numbers at most $m$ uses $O(n^2)$ word operations.\n", "\n", "Assuming that the operands are specified using the standard unique representative (i.e., by numbers at most $m$) then we can perform addition, subtraction, multiplication, and division (by a number coprime to $m$) in $O(n^2)$ word operations." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Modular exponentiation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "What about computing $a^k \\pmod{m}$? Of course, this could be computed by multiplying $a$ by itself $k-1$ times (and reducing the result modulo $m$ after each multiplication so that the number does not grow extremely large)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Cost analysis" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "As usual, suppose that $n=\\operatorname{len}(m)$. We can also assume that $a$ is reduced modulo $m$. Then multiplying by $a$ uses $O(n^2)$ word operations and reducing the result modulo $m$ also uses $O(n^2)$ word operations.\n", "\n", "Since this must be done $k-1$ times, computing $a^k\\pmod{m}$ using this method requires $O(kn^2)$ word operations." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Is this acceptable?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "At first, this may seem like a decent computational cost, as it is linear in $k$. Linear running times are usually good—assuming they are in the _size of the input_. But in this case the size of the input is $\\operatorname{len}(k)$, not $k$ itself. An $O(k)$ running time is actually **exponential** in the size of the input—which is very bad.\n", "\n", "For example, imagine trying to compute $2^{1234567890}\\pmod{10}$. In this case the result will be a single digit and the exponent $1{,}234{,}567{,}890$ fits in a single 32-bit word. However, using the simple algorithm of repeated multiplication will require over 1.2 billion multiplications!\n", "\n", "Of course, you really don't want to be doing over a billion multiplications to compute a single digit if you don't have to!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Can we do better?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Can we compute $a^k\\pmod{m}$ faster than using repeated mutliplication?\n", "\n", "The answer is yes! In fact, we can compute it using $O(\\log k)$ operations modulo $m$ which is very fast—even for $k$ like $k=1{,}234{,}567{,}890$.\n", "\n", "Moreover, the algorithm essentially only uses a single fairly simple trick.\n", "\n", "The fact that this trick exists makes modular exponentiation a very important and useful operation that has a wealth of applications. For example, later we'll see how it underlies how private information is kept secure on the internet." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Repeated squaring" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Fast modular exponentiation relies on a trick known as _repeated squaring_. The idea is that the sequence of numbers\n", "\n", "\\begin{gather*}\n", "a\\pmod{m} \\\\\n", "a^2\\pmod{m} \\\\\n", "a^{4}\\pmod{m} \\\\\n", "a^{8}\\pmod{m} \\\\\n", "\\vdots \\\\\n", "a^{2^i}\\pmod{m} \\\\\n", "\\vdots \\\\\n", "a^{2^{\\lfloor \\operatorname{lg}(k)\\rfloor}}\\pmod{m}\n", "\\end{gather*}\n", "\n", "can be computed quickly, because each number in the sequence is the square of the previous number. For example, once $a^4\\pmod{m}$ is known, one can compute $a^8\\pmod{m}=a^4\\cdot a^4\\pmod{m}$ using a single multiplication mod $m$. Since there are $\\renewcommand{\\len}{\\operatorname{len}}O(\\len(k))$ numbers in the sequence, computing them all takes $O(\\len(k)\\len(m)^2)$ word operations." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### How does this help?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Okay, so we are quickly able to compute $a^{2^i}\\pmod{m}$ for $i=0,\\dotsc,\\lfloor\\lg(k)\\rfloor$.\n", "\n", "However, it's not immediately clear how this helps us compute $a^k\\pmod{m}$ for arbitrary $k$—since unless it happens to be the case that $k$ is a power of 2 the quantity that we _want_ to compute will not be in the list of numbers that we _did_ compute." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### The solution" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The solution is to \"build\" the number that we want (i.e., $a^k\\pmod{m}$) out of the numbers that we computed (i.e., $a^{2^i}\\pmod{m}$ for $i$ up to $l:=\\lfloor\\lg(k)\\rfloor$).\n", "\n", "How can we do this? Note that $k$ can always be represented as a sum of powers of 2:\n", "\n", "$$k = \\sum_{i=0}^{l} k_i \\cdot 2^i$$\n", "\n", "where $k_i$ is the $i$th bit in the binary representation of $k$. For example, $19=2^4+2^1+2^0$ because 10011 is the binary representation of 19.\n", "\n", "Then we have that\n", "\n", "\\begin{align*} a^k &\\equiv a^{k_0 2^0 + k_1 2^1 + k_2 2^2 + \\dotsb + k_l 2^l} \\pmod{m} \\\\\n", "&\\equiv a^{k_0 2^0}\\cdot a^{k_1 2^1}\\cdot a^{k_2 2^2} \\dotsm a^{k_l 2^l} \\pmod{m} \\\\\n", "&\\equiv \\prod_{\\substack{i=0\\\\k_i=1}}^l a^{2^i} \\pmod{m} .\n", "\\end{align*}\n", "\n", "Thus once $a^{2^i}\\pmod{m}$ have been determined for $i\\leq l$ we can compute $a^k\\pmod{m}$ by multiplying together the $a^{2^i}\\pmod{m}$ for which $k_i=1$ (i.e., when the $i$th bit of $k$ in binary is 1).\n", "\n", "For example, $a^{19}\\equiv a^{16}\\cdot a^2 \\cdot a^1\\pmod{m}$ because we have that $k_4=k_1=k_0=1$ and $k_2=k_3=0$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Cost analysis" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "First, note that the binary representation of a number $k$ can be computed in $O(\\len(k))$ word operations.\n", "\n", "Once we have that and the sequence of numbers from before we have to perform at most $l-1=O(\\len(k))$ multiplications modulo $m$. Note that the worst case occurs when the binary representation of $k$ contains nothing but 1s and the best case occurs when $k$ is a power of 2.\n", "\n", "Thus, the cost of computing $a^k\\pmod{m}$ via repeated squaring is the sum of:\n", "\n", "* The cost of performing repeated squaring: $O(\\len(k)\\len(m)^2)$\n", "* The cost of finding the binary representation of $k$: $O(\\len(k))$\n", "* The cost of building the result out of the numbers computed via repeated squaring: $O(\\len(k)\\len(m)^2)$\n", "\n", "In total, this requires $O(\\len(k)\\len(m)^2)$ word operations." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Built-in Sage function" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The Sage function power_mod performs modular exponentiation using repeated squaring.\n", "\n", "power_mod(a, k, m) will produce the same result as a^k % m but in general power_mod will be much faster than using ^.\n", "\n", "We can demonstrate this using the timeit command:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "timeit('2 ^ 1234567890 % 10')" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "timeit('power_mod(2, 1234567890, 10)')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Simultaneous linear congruences" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Finally, we'll cover a classic number theory problem (whose solution dates back to the 3rd century by the Chinese mathematician Sun-tzu).\n", "\n", "Suppose we want to solve the following system of congruences for $x$:\n", "\n", "\\begin{align*}\n", "x &\\equiv 2 \\pmod{3} \\\\\n", "x &\\equiv 3 \\pmod{5} \\\\\n", "x &\\equiv 2 \\pmod{7}\n", "\\end{align*}\n", "\n", "How could you find a solution $x$?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Brute force" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The obvious answer: try $x=0,1,2,\\dotsc$ one at a time and stop if you find an $x$ which satisfies each of the congruences simultaneously.\n", "\n", "However, what if this method runs indefinitely?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### How far do you need to go?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that if $x$ is a solution then $x+k\\cdot3\\cdot5\\cdot7$ is also a solution for all integers $k$. This follows because $k\\cdot3\\cdot5\\cdot7$ reduces to 0 modulo $3$, $5$, and $7$.\n", "\n", "Thus, in the worst case you have to examine all $x$ from $0$ up to $104=3\\cdot5\\cdot7-1$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Analysis" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If $P=\\prod_i m_i$ is the product of the moduli $m_i$ then in the worst case $P$ possibilities for $x$ will have to be tried, so this method runs in $O(P)$ arithmetic operations modulo $m_i$.\n", "\n", "Again, this might sound reasonable at first but it is exponential in $\\len(m_i)$. Just imagine increasing the first modulus from 3 to 3 trillion. This doesn't even increase the length of the moduli (assuming a 64-bit word size) but increases the running time of this method by a factor of trillion!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example solution" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Consider the first two congruences. Translating them into equations over the integers, we want to find integers $x$, $k$, and $l$ which satisfy\n", "\n", "\\begin{align*}\n", "x &= 2 + 3k &\n", "x &= 3 + 5l\n", "\\end{align*}\n", "\n", "Equating these, we want to solve $2+3k = 3 + 5l$ which is just a slightly-disguised linear Diophantine equation\n", "that can be rewritten in the form\n", "\n", "$$3k-5l=1. \\tag{3}$$\n", "\n", "Since $\\gcd(3,5)=1$, Bézout's identity tells us this equation has a solution in the integers and the extended Euclidean algorithm allows us to find the solution $(k,l)=(2,1)$ leading to $x=8$ which satisfies the first two congruences.\n", "Recall that _all_ solutions of (3) are given by $(k,l)=(2+5a,1+3a)$ for $a\\in\\mathbb{Z}$ leading to $x=8+15a$ as the general solution of the first two congruences.\n", "\n", "Of course, this is only a solution of the first two congruences and we still have a third congruence to consider. However, $x=8+15a$ for $x\\in\\mathbb{Z}$ is equivalent to the congruence $x\\equiv8\\pmod{15}$ so we can rewrite the system as:\n", "\n", "\\begin{align*}\n", "x &\\equiv 8 \\pmod{15} \\\\\n", "x &\\equiv 2 \\pmod{7}\n", "\\end{align*}\n", "\n", "Now we can apply the same procedure as before! To solve these we want to solve $x=8+15l=2+7k$ in integers which can be rewritten as $15l-7k=-6$. This has a solution since $-6$ is a multiple of $\\gcd(15,7)=1$. The extended Euclidean algorithm produces\n", "\n", "$$15\\cdot1 - 7\\cdot2 = 1 \\qquad\\,\\xrightarrow{\\text{multiply by -6}}\\qquad\\, 15\\cdot(-6) - 7\\cdot(-12) = -6$$\n", "\n", "so $(l,k)=(-6,-12)$ and $x=-82$ is a solution. As previously noted, all numbers of the form $-82+105a$ for $a\\in\\mathbb{Z}$ are also solutions. The canonical representation of $x$ is then $23$. Indeed, we find that:\n", "\n", "\\begin{align*}\n", "23 &\\equiv 2 \\pmod{3} \\\\\n", "23 &\\equiv 3 \\pmod{5} \\\\\n", "23 &\\equiv 2 \\pmod{7}\n", "\\end{align*}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Chinese remainder theorem" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The formal mathematical result is known as the \"Chinese remainder theorem\". It says that if $m_0,\\dotsc,m_{r-1}$ are pairwise coprime ($\\gcd(m_i,m_j)=1$ for $i\\neq j$) then\n", "\n", "\\begin{align*}\n", "x &\\equiv a_0 \\pmod{m_0} \\\\\n", "&\\,\\,\\vdots \\\\\n", "x &\\equiv a_{r-1} \\pmod{m_{r-1}} \n", "\\end{align*}\n", "\n", "has a unique solution $x$ modulo $m=m_0\\dotsm m_{r-1}$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### General solution" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Given $a_0,\\dotsc,a_{r-1}$ and $m_0,\\dotsc,m_{r-1}$ how can we find the unique solution $x$?\n", "\n", "In fact, the general solution is of the form\n", "\n", "$$x \\equiv a_0 L_0 + a_1 L_1 + \\dotsb + a_{r-1} L_{r-1} \\pmod{m}$$\n", "\n", "where the $L_i$ are computed so that\n", "\n", "\\begin{align*}\n", "L_i &\\equiv 1 \\pmod{m_i} \\\\\n", "L_i &\\equiv 0 \\pmod{m_k} \\qquad\\text{for all $k\\neq i$.}\n", "\\end{align*}\n", "\n", "Reducing the expression for $x$ modulo $m_i$ shows that $x\\equiv a_i\\pmod{m_i}$, i.e., $x$ is indeed a solution. However, how can we compute values for the $L_i$?\n", "\n", "Since $L_i$ is a multiple of $m_k$ for all $k\\neq i$ it follows that $L_i$ is also a multiple of the product $\\prod_{k\\neq i}m_k=\\frac{m}{m_i}$. Thus we want to find $L_i$ such that\n", "\n", "\\begin{align*}\n", "L_i &\\equiv 1 \\pmod{m_i} \\\\\n", "L_i &\\equiv 0 \\pmod{m/m_i}\n", "\\end{align*}\n", "\n", "which is equivalent to the linear Diophantine equation $s\\cdot m_i+t\\cdot(m/m_i) = 1$. Since $\\gcd(m_i,m/m_i)=1$ we know the extended Euclidean algorithm allows us to find a satisfying $(s,t)$. Setting $L_i:=t\\cdot(m/m_i)$ gives $L_i\\equiv 1\\pmod{m_i}$ and $L_i\\equiv0\\pmod{n/m_i}$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### A general formula" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Explicitly, if you'd like a general formula, note that the $t$ from above is defined to be $(m/m_i)^{-1}\\bmod m_i$. Since $L_i=t\\cdot(m/m_i)$ the general solution for $x$ is\n", "\n", "$$x = \\sum_{i=0}^{r-1} a_i \\cdot ((m/m_i)^{-1}\\bmod m_i)\\cdot(m/m_i) . \\tag{4}$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Cost analysis" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "First, we find the cost of computing $m=\\prod_i m_i$. Note that $\\len(\\prod_{i=0}^k m_i)=O(\\sum_{i=0}^k\\len(m_i))=O(\\len(m))$. Computing each successive product for $k=1,\\dotsc,r-1$ results in a total word operation cost of\n", "\n", "$$O\\biggl(\\sum_{k=1}^{r-1} \\len\\biggl(\\prod_{i=0}^k m_i\\biggr)\\len(m_i)\\biggr) = O(\\len(m))\\cdot\\sum_{k=1}^{r-1}O(\\len(m_i)) = O(\\len(m)^2) .$$\n", "\n", "Next, once $m$ is computed we can compute $m/m_i$ for $i=0,\\dotsc,r-1$ using a total word operation cost of\n", "\n", "$$O\\biggl(\\sum_{i=0}^{r-1}\\len(m/m_i)\\len(m_i)\\biggr) = O(\\len(m))\\cdot \\sum_{i=0}^{r-1}O(\\len(m_i)) = O(\\len(m)^2) .$$\n", "\n", "Similarly, we can compute $(m/m_i)\\bmod m_i$ in the same cost. Next, we can compute $(m/m_i)^{-1}\\bmod m_i$ for $i=0,\\dotsc,r-1$ using a total word operation cost of\n", "\n", "$$O\\biggl(\\sum_{i=0}^{r-1}\\len(m_i)^2\\biggr) = O\\biggl(\\Bigl(\\sum_{i=0}^{r-1}\\len(m_i)\\Bigr)^2\\biggr) = O(\\len(m)^2) .$$\n", "\n", "Similarly, we can compute $L_i=((m/m_i)^{-1}\\bmod m_i)\\cdot(m/m_i)$ in a word operation cost of\n", "\n", "$$O\\biggl(\\sum_{i=0}^{r-1}\\len(m_i)\\len(m/m_i)\\biggr) = \\sum_{i=0}^{r-1}O(\\len(m_i))\\cdot O(\\len(m)) = O(\\len(m)^2) .$$\n", "\n", "Finally, to compute $x$ from (4) assuming that $\\len(a_i)=O(\\len(m_i))$ uses a total word operation cost of\n", "\n", "$$O\\biggl(\\sum_{i=0}^{r-1}\\len(m_i)\\cdot\\len(m)\\biggr) = \\sum_{i=0}^{r-1}O(\\len(m_i))\\cdot O(\\len(m)) = O(\\len(m)^2) .$$\n", "\n", "In summary, we can solve simulaneous linear congruences using the formula (4) provided by the Chinese remainder theorem and this requires $O(\\len(m)^2)$ word operations." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Takeaway" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In summary, the Chinese remainder theorem provides a way of solving simultaneous linear congruences when the moduli of the congruences are pairwise coprime. It also allows us to efficiently compute the unique solution of such congruences—namely, quadratic in the length of the product of the moduli.\n", "\n", "Applications of the Chinese remainder theorem reach far beyond what it may seem like at first glance. In fact, the Chinese remainder theorem essentially says that doing computations modulo $m=m_0\\dotsm m_{r-1}$ is in a sense equivalent to doing computations modulo each of $m_0,\\dotsc,m_{r-1}$. This is useful because computations modulo $m_i$ are cheaper than computations modulo $m$.\n", "\n", "It also opens the possibility for parallelization: a computation that needs to be done modulo $m$ can instead be done modulo $m_i$ for each $i=0,\\dotsc,r-1$. Since each computation modulo $m_i$ is independent, the entire computation can be distributed across $r$ processors. Once they've all finished the final result modulo $m$ can be computed using the Chinese remainder theorem.\n", "\n", "For example, \"Chinese remaindering\" methods are very useful for linear system solving or determinant computation on integer matrices." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Fermat's Little Theorem" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A classic theorem of the mathematician Fermat (known as his \"little\" theorem—not his more famous \"last\" theorem) is the following:\n", "\n", "If $p$ is a prime and $a$ is not a multiple of $p$, then\n", "\n", "$$a^{p-1}\\equiv 1\\pmod{p} . \\tag{5}$$\n", "\n", "It is easy to see that the restriction on $a$ is necessary:\n", "if $a$ _is_ a multiple of $p$ then $a\\equiv 0\\pmod{p}$ meaning $a^{p-1}\\equiv0\\pmod{p}$.\n", "\n", "However, by multiplying both sides of (5) by $a$ gives an easier-to-state form that works for all $a$. If $p$ is a prime and $a$ is an integer then\n", "\n", "$$a^p \\equiv a \\pmod{p} .$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Proof\n", "\n", "There are many ways to prove Fermat's Little Theorem, but we'll present a nice short proof of (5) using properties of modular arithmetic we've seen.\n", "\n", "Consider the numbers $a,2a,\\dotsc,(p-1)a$ all computed modulo $p$. In fact, this list will be a rearrangement of $1,2,\\dotsc,p-1$, i.e., \n", "\n", "\\begin{equation} \\{ai\\bmod p : 1\\leq i