> For the complete documentation index, see [llms.txt](https://evarga.gitbook.io/sh-intro-to-algs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://evarga.gitbook.io/sh-intro-to-algs/part-vii-selected-topics/chapter-31.md). # 31. Number-Theoretic Algorithms ## Exercises ### 31.1-1 Based on Theorem 31.1 (Division theorem), we have $$ c=\lfloor c/a\rfloor a+r=\lfloor (a+b)/a\rfloor a+r=1\cdot a+r, $$ since $$a>b>0$$. Furthermore, $$c=a+b \implies r=b=c !\mod a$$. ### 31.1-2 Read [Euclid's proof](https://en.wikipedia.org/wiki/Euclid's_theorem#Euclid's_proof) on Wikipedia. ### 31.1-3 🌟 {% hint style="success" %} Proves that the $$a \mid b$$ relation is transitive. {% endhint %} We have $$a \mid b \implies b=pa$$ and $$b\mid c\implies c=qb$$ for integers $$p$$ and $$q$$. Therefore, $$c=(pq)a\implies a\mid c$$. ### 31.1-4 The only divisors of $$p$$ are 1 and $$p$$. No divisor of $$k$$ except 1 divides $$p$$, since $$k\

2$$, we have $$ \begin{align\*} \gcd(a\_i, p) &=1 && \text{(for all } i=1,2,\dots,n \text{)} \\ &\implies \gcd(\prod\_{i=1}^{n-1}a\_i, p)=1 \land \gcd(a\_n,p)=1 && \text{(by the inductive hypothesis)} \\ &\implies \gcd(\prod\_{i=1}^na\_i, p)=1 && \text{(by Theorem (3.16))}. \end{align\*} $$ According to the principles of mathematical induction, we can conclude that the lemma holds for all $$n \ge 2$$. $$\blacksquare$$ $$ \binom{p}{k} \cdot k!(p-k)! = p \cdot (p-1)! \implies p \mid \left( \binom{p}{k} \cdot k!(p-k)! \right). $$ Based on [Exercise 31.1-4](#id-31.1-4) and Lemma 1, for $$0\n \implies k \in \[2,\beta)$$. Therefore, we iterate over all possible exponents $$k$$ in increasing order and see if the $$k$$th root of $$n$$ is an integer. We can leverage binary search over the interval $$\[2,n)$$ in searching for this root. We iteratively raise each candidate $$a$$ to the $$k$$th power by multiplying the current product with $$a$$ (initially setting it to 1). In each iteration, we also check if this product is greater than $$n$$, so that we stop as soon as possible. This stage demands $$O(\beta)(O(\beta^2)+O(\beta))=O(\beta^3)$$ time. In case of a match, we finish the search, otherwise, recurse into the lower or upper subinterval depending on whether $$a^k>n$$ or not, respectively. If the subinterval becomes empty, then we declare an unsuccessful attempt to find the root for the given exponent. All in all, we can determine whether a given $$\beta$$-bit integer $$n$$ is a nontrivial power in $$O(\beta^5)$$ time. ### 31.1-9 #### Proof of 31.6 By definition, $$\gcd(a,b)$$ is the largest element in the set $$D\_{(a,b)}$$ of the common divisors of $$a$$ and $$b$$. Analogously, $$\gcd(b,a)$$ is the largest element in the set $$D\_{(b,a)}$$ of the common divisors of $$b$$ and $$a$$. We know that $$D\_{(a,b)}=D\_{(b,a)}$$ and there cannot be two different largest element in a set. Therefore, $$\gcd(a,b) = \gcd(b,a)$$. #### Proof of 31.7 $$d\_1=\gcd(a,b) \implies (d\_1\mid a) \land (d\_1\mid b)$$, but this also means that $$d\_1\mid (-a)$$, hence $$d\_1 \le d\_2=\gcd(-a,b)$$. With similar reasoning we can conclude that $$d\_2 \le d\_1$$, therefore $$d\_1=d\_2$$. #### Proof of 31.8 $$ \begin{align\*} \bm{\gcd⁡(a,b)}&=\gcd⁡(b,a) && \text{(by property (31.6))} \\ &=\gcd⁡(−b,a) && \text{(by property (31.7))} \\ &=\bm{\gcd⁡(a,-b)} && \text{(by property (31.6))} \\ &=\bm{\gcd⁡(−a,-b)} && \text{(by property (31.7))} \\ &=\gcd⁡(−b,−a) && \text{(by property (31.6))} \\ &=\gcd⁡(b,−a) && \text{(by property (31.7))} \\ &=\bm{\gcd⁡(−a,b)} && \text{(by property (31.6))} \\ &\therefore \gcd⁡(a,b)=\gcd⁡(|a|,|b|). \end{align\*} $$ #### Proof of 31.9 By property (31.8) we have that $$\gcd⁡(a,0)=\gcd⁡(|a|,0)$$. Any common divisor of $$|a|$$ and 0 cannot be larger than $$|a|$$, so $$\gcd⁡(a,0)=|a|$$ (any integer divides 0). As a side note, if $$a=0$$ then $$\gcd⁡(0,0)=0=|a|$$. #### Proof of 31.10 By property (31.8) we have that $$\gcd⁡(a,ka)=\gcd⁡(|a|,|ka|)=\gcd⁡(|a|,|k||a|)$$. We have the following three cases: * If $$k=0$$ then $$\gcd⁡(a,0)=|a|$$ by property (31.9). * If $$a=0$$ then $$\gcd(0,0)=0=|a|$$. * Let $$a \neq 0 \land k \neq 0$$. We know that $$|a|$$ divides itself, and $$|a|$$ divides $$|k||a|$$. Because $$|a|$$ is a common divisor, and no divisor of $$|a|$$ can be strictly greater than $$|a|$$, it must be the greatest common divisor. Therefore, $$\gcd(|a|, |k||a|) = |a|$$. ### 31.1-10 🌟 {% hint style="success" %} Proves that the $$\gcd$$ operator is associative. {% endhint %} Let $$d\_1=\gcd(a,\gcd(b,c))$$ and $$d\_2=\gcd(\gcd(a,b),c)$$. We prove the statement from the book by showing that $$d\_1\mid d\_2$$ and $$d\_2\mid d\_1$$, thus by equation (31.5) they must be equal, as both of them are nonnegative. We know that $$d\_1\mid a \land d\_1\mid \gcd(b,c)$$, which entails that $$d\_1\mid b \land d\_1\mid c$$. The fact that $$d\_1$$ divides both $$a$$ and $$b$$ implies that it also divides $$\gcd(a,b)$$ by Corollary 31.3. Therefore, $$d\_1\mid d\_2$$ by applying again Corollary 31.3. Using the same reasoning we can conclude that $$d\_2\mid d\_1$$, which finishes the proof about associativity of the $$\gcd$$ operator. ### ★ 31.1-11 You can read the proof [here](https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic#Uniqueness_without_Euclid's_lemma) that uses only facts mentioned in the book. ### 31.1-12 The $$O(\beta^2)$$ time algorithm shown [here](https://en.wikipedia.org/wiki/Division_algorithm#Integer_division_\(unsigned\)_with_remainder) also handles the edge case when a divisor is larger than a number to be divided. ### 31.1-13 We follow the hint from the book. The main idea is to split a $$\beta$$-bit binary number and obtain the top and bottom halves of the result with separate recursions. The divide step must enable an easy assembly of these partial results. Since we are converting into a decimal representation it makes sense to split according to powers of 10. The key insight is to precompute these powers (in binary) to facilitate efficient splitting. [Precomputation](https://en.wikipedia.org/wiki/Precomputation) is a powerful technique in algorithm design. The steps to accomplish this are laid out below: {% stepper %} {% step %} ### Configure parameters Calculate the total number of decimal digits $$D=\lceil\beta \lg\_{10}2\rceil$$, set the recursion depth $$L=\lceil\lg D\rceil$$, and create 1-indexed lookup tables $$S$$ (stores split points) and $$P$$ (stores powers of 10) as static arrays of size $$L$$. {% endstep %} {% step %} ### Fill the lookup tables For each level $$i=1,2,\dots,L$$: 1. Determine the split point $$S\_i=\lceil D/2^i \rceil$$ (half the digits at level $$i$$). 2. Compute $$P\_i=10^{S\_i}$$ using exponentiation by squaring. Each $$P\_i$$ has $$\Theta(\beta/2^i)$$ bits, so computing it demands $$O(M(\beta /2^i)\lg \beta)$$ time. The total time is $$\sum\_{i=1}^L {O(M(\beta /2^i)\lg \beta)}=O(\sum\_{i=1}^L {M(\beta /2^i)\lg \beta)}=O(M(\beta)\lg \beta)$$ assuming $$M$$ satisfies the properties of standard multiplication algorithms, like, being non-decreasing as well as the sum of $$M$$ over geometrically decreasing sizes is dominated by $$M(\beta)$$ (sort of weak regularity). {% endstep %} {% endstepper %} ### Recursive conversion function Assume that handling decimal representation is not influencing the asymptotical behavior of our main routine. For example, concatenating strings (and padding with leading zeros) takes linear time with respect to the number of digits. Because $$O(\beta)$$ is strictly bounded by $$O(M(\beta))$$ since $$M(\beta) = \Omega(\beta)$$, the string operations do not ruin the asymptotic time complexity. {% stepper %} {% step %} ### Function signature Our function has the signature $$Convert(n, d, i)$$, where * $$n$$ is the number to convert * $$d$$ is the upper bound on number of decimal digits of $$n$$ * $$i$$ is the current recursion level The function returns a decimal representation of $$n$$. It should be initially called with $$Convert(N, D, 1)$$. {% endstep %} {% step %} ### Base case If $$d=1$$ then return the single digit representation of $$n$$. {% endstep %} {% step %} ### Recursive case 1. Compute the values for the top $$t=\lfloor n /P\_i \rfloor$$ and bottom $$b=n !!\mod P\_i$$ halves. 2. Recursively obtain the decimal representation of the top half $$r\_{top}=Convert(t,d-S\_i,i+1)$$. 3. Recursively obtain the decimal representation of the bottom half $$r\_{bottom}=Convert(b,S\_i,i+1)$$. 4. Pad $$r\_{bottom}$$ with leading zeros to length $$S\_i$$. 5. Produce a combined result $$r=r\_{top} \Join r\_{bottom}$$ by concatenating the two halves. 6. Remove leading zeros from $$r$$, if any. 7. Return $$r$$. {% endstep %} {% endstepper %} The recurrence formula is $$T(\beta)=2T(\beta/2)+M(\beta)$$. We have two variations on the recurrence using the fact that $$M(\beta)=\Omega(\beta)$$: * If $$M(\beta)=\Theta(\beta\lg \beta)$$ then by the Master theorem $$T(\beta)=\Theta(M(\beta)\lg \beta)$$. * If $$M(\beta)=\Theta(\beta^{1+\epsilon})$$ for some $$\epsilon>0$$ then by the Master theorem $$T(\beta)=\Theta(M(\beta))$$ assuming $$M(\beta)$$ satisfies the regularity condition (most standard multiplication/division algorithms do). We can conclude that $$T(\beta)=O(M(\beta)\lg \beta)$$ taking into account the pre-computation and conversion times, too. ### 31.1-14 See the answer [here](https://brainstellar.com/puzzles/18) with a derailed solution. ### 31.2-1 You can read the proof [here](https://www.math.cmu.edu/~cnewstea/teaching//old/teaching/21-127-S14/handouts/gcd-with-fta.pdf). There are two remarks about external references in the content: * Proposition 1(iv) is about the rule $$(a \neq 0 \land d\mid a) \implies |d| \le |a|$$. * Proposition 1(i) is [Exercise 31.1-3](#id-31.1-3). ### 31.2-2 We create a table, similar to Figure 31.1 from the book, by running the next Python 3 script. ```python rows = [] def add_row(a, b, d, x, y): rows.append((a, b, a // b if b > 0 else '-', d, x, y)) def print_rows(): headers = ("a", "b", "⌊a/b⌋", "d", "x", "y") col_widths = [len(h) for h in headers] for row in rows: for i, val in enumerate(row): col_widths[i] = max(col_widths[i], len(str(val))) sep = "+" + "+".join("-" * (w + 2) for w in col_widths) + "+" fmt = "|" + "|".join(f" {{:>{w}}} " for w in col_widths) + "|" print(sep) print(fmt.format(*headers)) print(sep) for row in reversed(rows): print(fmt.format(*row)) print(sep) def extended_euclid(a, b): if b == 0: add_row(a, b, a, 1, 0) return (a, 1, 0) (d, x, y) = extended_euclid(b, a % b) (x, y) = (y, x - (a // b) * y) add_row(a, b, d, x, y) return (d, x, y) extended_euclid(899, 493) print_rows() ``` Observe the usage of the list `rows` to reverse the output shown below. ``` +-----+-----+-------+----+----+----+ | a | b | ⌊a/b⌋ | d | x | y | +-----+-----+-------+----+----+----+ | 899 | 493 | 1 | 29 | -6 | 11 | | 493 | 406 | 1 | 29 | 5 | -6 | | 406 | 87 | 4 | 29 | -1 | 5 | | 87 | 58 | 1 | 29 | 1 | -1 | | 58 | 29 | 2 | 29 | 0 | 1 | | 29 | 0 | - | 29 | 1 | 0 | +-----+-----+-------+----+----+----+ ``` ### 31.2-3 🌟 {% hint style="success" %} Proves that for all integers $$a,k,n$$ we have $$\gcd(a,n)=\gcd(a+kn,n)$$. Consequently, $$a=1\space(!!!!\mod n) \implies \gcd(a,n)=1$$. {% endhint %} Let $$d\_1=\gcd(a,n)$$ and $$d\_2=\gcd(a+kn,n)$$. We proceed by showing that $$d\_1\mid d\_2$$ and $$d\_2\mid d\_1$$, thus according to equation (31.5) they are equal. We know that $$d\_1\mid a$$ and $$d\_1\mid n$$, so by equation (31.4) we have $$d\_1\mid a+kn$$. Based on Corollary 31.3 we can conclude that $$d\_1\mid d\_2$$. We know that $$d\_2\mid n$$, so $$n=pd\_2$$ for some integer $$p$$. Furthermore, $$d\_2\mid a+kn$$, thus $$a+kn=qd\_2$$ for some integer $$q$$. Therefore, $$a=qd\_2-kn=qd\_2-kpd\_2=(q-kp)d\_2$$ implies $$d\_2\mid a$$. Based on Corollary 31.3 we can conclude that $$d\_2\mid d\_1$$. $$a=1\space(!!!!\mod n) \implies a=1+kn$$, so $$\gcd(1+kn,n)=\gcd(1,n)=1$$ by equation (31.18). Consequently, we have $$\gcd(a,n)=1$$. ### 31.2-4 Below is the iterative version of Euclid's algorithm in Python 3. ```python def iterative_euclid(a, b): while b > 0: a, b = b, a % b return a ``` ### 31.2-5 If $$b=0$$ then the call $$\text{Euclid}(a,b)$$ immediately hits the base case and returns, so no recursive calls are made. Assume that $$b>0$$. The steps to prove the first bound are as follows: 1. Let $$k$$ be the number of recursive calls made by $$\text{Euclid}(a,b)$$. 2. By Lamé's theorem, we know that $$b \ge F\_{k+1}$$. 3. By the standard bounds of the Fibonacci sequence, we know that $$F\_{k+1} \ge \phi^{k-1}$$ for $$k \ge 1$$. 4. Combining these gives $$b \ge \phi^{k-1}$$, so $$k \le 1 + \log\_\phi b$$. Let $$d=\gcd(a,b)$$. Because $$a=d\cdot (a/d)$$ and $$b=d\cdot (b/d)$$, the remainder at each step of the algorithm is also perfectly scaled by $$d$$: $$ a \bmod b = d \cdot ((a/d) \bmod (b/d)). $$ Because every single division operation yields a remainder exactly $$d$$ times larger than the reduced version, the sequence of recursive calls progresses identically. The call $$\text{Euclid}(a, b)$$ will make the exact same number of recursive calls as $$\text{Euclid}(a/d, b/d)$$. Now, proceeding in almost the same way as above, we can establish that the call $$\text{Euclid}(a,b)$$ makes at most $$1 + \log\_\phi (b/\gcd(a,b))$$ recursive calls. ### 31.2-6 Assume that $$k>2$$, otherwise we would immediately reach the base case. $$F\_{k+1}=F\_k+F\_{k-1}$$, hence by [Exercise 31.1-1](#id-31.1-1) we have that $$F\_{k-1}=F\_{k+1} !!\mod F\_k$$. Therefore, the call to $$\text{Extended\text{\textendash}Euclid}(F\_{k+1},F\_k)$$ recurses into $$\text{Extended\text{\textendash}Euclid}(F\_k,F\_{k-1})$$, and this process continues until hitting the base that happens right after the call to $$\text{Extended\text{\textendash}Euclid}(F\_3,F\_2)$$ . The final call $$\text{Extended\text{\textendash}Euclid}(F\_2,0)$$ returns a 3-tuple $$(1,1,0)$$. Thus, $$\gcd(F\_{k+1},F\_k)=1$$. We now need to find out the coefficients $$x$$ and $$y$$. In general, $$\text{Extended\text{\textendash}Euclid}(F\_{k+1},F\_k)$$ returns a 3-tuple $$(1,(-1)^{k+1}F\_{k-2},(-1)^kF\_{k-1})$$. We prove this by induction on $$k$$. The base case $$k=2$$ obviously holds. For $$k>2$$ the quotient $$q=\lfloor F\_{k+1}/F\_k \rfloor=\lfloor (F\_k+F\_{k-1})/F\_k \rfloor=1$$. Thus, $$(d,x,y)=(d',y',x'-y')$$ at all levels. By the inductive hypothesis the call to $$\text{Extended\text{\textendash}Euclid}(F\_k,F\_{k-1})$$ returns a 3-tuple $$(1,(-1)^kF\_{k-3},(-1)^{k-1}F\_{k-2})$$, thus $$\text{Extended\text{\textendash}Euclid}(F\_{k+1},F\_k)$$ returns $$ \begin{align\*} (1,(-1)^{k-1}F\_{k-2},(-1)^kF\_{k-3}-(-1)^{k-1}F\_{k-2}) &= (1,(-1)^{k+1}F\_{k-2},(-1)^kF\_{k-3}+(-1)^kF\_{k-2}) \\ &= (1,(-1)^{k+1}F\_{k-2},(-1)^k(F\_{k-3}+F\_{k-2}) \\ &= (1,(-1)^{k+1}F\_{k-2},(-1)^kF\_{k-1}) \quad \checkmark \end{align\*} $$ Observe in line 1 that $$(-1)^{k-1}=(-1)^{k+1}$$. ### 31.2-7 We proceed by induction on $$n$$. The base cases are when $$n=1 \lor n=2$$. If $$n=1$$ then we have nothing to permute and for $$n=2$$ we can apply equation (31.6). For $$n>2$$ assume that the inductive hypothesis holds for $$n$$ arguments. Every permutation is consisted of individual pairwise swaps of elements. An informal indirect proof is an ability of any sorting algorithm to find the matching permutation that results in proper ordering of elements. This is attained in a step-by-step fashion, swapping each time a pair of elements on different positions. Thus, let us consider elements $$a\_i$$ and $$a\_j$$ where $$0\le i \0$$ then it immediately follows by the inductive hypothesis that $$\gcd⁡(a\_0,a\_1,\dots,a\_i,\dots,a\_j,\dots,a\_n)=\gcd⁡(a\_0,a\_1,\dots,a\_j,\dots,a\_i,\dots,a\_n)$$. 2. If $$i=0$$ then we have the following sequence of equivalent transformations: $$ \begin{align\*} \gcd⁡(a\_i,a\_1,\dots,a\_j,\dots,a\_n)&=\gcd⁡(a\_i,\gcd(a\_1,\dots,a\_j,\dots,a\_n)) \\ &= \gcd⁡(a\_i,\gcd(a\_j,a\_1,\dots,a\_n)) && \text{(by the inductive hypothesis)} \\ &= \gcd⁡(\gcd(a\_j,a\_1,\dots,a\_n),a\_i) && \text{(by equation (31.6))} \\ &= \gcd⁡(a\_j,\gcd(a\_1,\dots,a\_n,a\_i)) && \text{(by the associativity rule)} \\ &= \gcd⁡(a\_j,\gcd(a\_1,\dots,a\_i,\dots,a\_n)) && \text{(by the inductive hypothesis)} \\ &=\gcd⁡(a\_j,a\_1,\dots,a\_i,\dots,a\_n). \end{align\*} $$ {% hint style="info" %} [Exercise 31.1-10](#id-31.1-10) proves that the $$\gcd$$ operator is associative. This property extends to arbitrary number of arguments due to the [generalized associative law](https://en.wikipedia.org/wiki/Associative_property#Generalized_associative_law). {% endhint %} $$ \begin{align\*} \gcd⁡(a\_0,a\_1,\dots,a\_n) &= \gcd⁡(a\_0,\gcd⁡(a\_1,\dots,a\_n)) \\ &= xa\_0+y\gcd⁡(a\_1,a\_2,\dots,a\_n) \\ &=xa\_0+y(x'a\_1+y'\gcd⁡(a\_2,a\_3,\dots,a\_n)) \\ &=xa\_0+y(x'a\_1+y'(x''a\_2+y′′\gcd(a\_3,a\_4,\dots,a\_n))) \\ &=\dots \end{align\*} $$ Let $$d\_k=\gcd(a\_k, d\_{k-1})$$ at some step $$1 \le k \le n$$. Based on [Exercise 31.2-5](#id-31.2-5), the number of divisions for this single step is bounded by $$ O(1 + \lg(d\_{k-1} / d\_k)). $$ Taking into account all steps, we get a telescoping sum $$ \text{Total Divisions} \le \sum\_{k=1}^n O\left(1 + \lg\left(\frac{d\_{k-1}}{d\_k}\right)\right)=O(n) + O(\lg d\_0 - \lg d\_n)=O(n+\lg (\max{a\_0,a\_1,\dots,a\_n})). $$ ### 31.2-8 🌟 {% hint style="success" %} Shows how to compute a generalized $$$$least common multiple using the binary $$\gcd$$ operator. {% endhint %} The base case is defined as (the RHS is an optimization to avoid an overflow error) $$ \text{lcm}(a,b)=\cfrac{|a\cdot b|}{\gcd(a,b)}= |a| \cdot \left( \frac{|b|}{\gcd(a,b)} \right). $$ The generalization to arbitrary number of arguments is almost the same as with the generic $$\gcd$$ (see the previous exercise). Therefore, $$ \text{lcm}(a\_1,a\_2,\dots,a\_n)=\text{lcm}(a\_1,\text{lcm}(a\_2,a\_3,\dots,a\_n)). $$ If any $$a\_i = 0$$, we should immediately halt and return 0. ### 31.2-9 We first describe the general case and later demonstrate it using the example with $$k=4$$ from the book. WLOG assume that indices are 0-based. {% stepper %} {% step %} ### Constructing the derived pairs 1. Write each index $$i \in {0,1,\dots,k-1}$$ into unique binary form using exactly $$r=\lceil \lg k \rceil$$ digits, padding with leading zeros, as needed. 2. For each bit position $$0 \le j \1$$, then the previous conclusion is not valid. One counterexample is $$2x=2y\space(!!!!\mod 4)$$, where $$x=1$$ and $$y=3$$ is also a valid solution. ### 31.4-3 Yes, it will work, forcing the procedure to emit solutions in sorted order. Among those $$d$$ distinct solutions, which are $$n/d$$ positions apart from each other, one will always belong to the interval $$\[0,n/d)$$. Let it be $$x\_i=x'(b/d)+i(n/d)\space(!!!!\mod n)$$ for some $$i \in \[0,d)$$. [Exercise 31.1.-7](#id-31.1-7) implies that $$x\_i=x'(b/d)\space(!!!!\mod n/d)$$, hence setting $$x\_0=x\_i\space(!!!!\mod n/d)$$ is the smallest starting value. Since the code starts at the minimum value and adds a positive constant each time without ever wrapping around the modulo boundary, the output is guaranteed to be strictly increasing. ### ★ 31.4-4 🌟 {% hint style="success" %} Explains the [factor theorem](https://en.wikipedia.org/wiki/Factor_theorem) applied modulo $$p$$. {% endhint %} I recommend reading the [proof](https://en.wikipedia.org/wiki/Factor_theorem#Proof_3) based on Euclidean division of polynomials, which is aligned with the narrative from the book. {% hint style="info" %} For deriving broader conclusions from the factor theorem, it is crucial for $$p$$ to be prime. For example, if $$p=8$$ then the polynomial $$f(x)=x^2+7\space(!!!!\mod p)$$ has 4 roots $${1,3,5,7}$$ instead of $$t=2$$, where $$t$$ is a degree of $$f$$. {% endhint %} We proceed by induction on degree $$t$$. The base case $$t=1$$ follows from Corollary 31.25. For $$t>1$$, we have $$f(x)=(x-a)g(x)$$, so $$f$$ has at most $$1+(t-1)=t$$ distinct roots modulo $$p$$ (after applying the inductive hypothesis on $$g(x)$$). Notice, that any other root of $$f$$ is forced to be a root of $$g$$. Suppose $$f$$ has another distinct zero $$b$$, such that $$b \neq a$$ and $$ f(b)=(b-a)g(b) = 0 \pmod p. $$ $$p \mid (b-a)g(b) \implies p \mid (b-a) \lor p \mid g(b)$$ (recall that $$p$$ is prime). Since $$b \neq a \pmod p$$, it must be that $$p \mid g(b)$$, so $$g(b) = 0 \pmod p$$. This concludes the proof for all $$t \ge 1$$. ### 31.5-1 We follow the process outlined in Theorem 31.27. We have $$x\_1=4$$, $$n\_1=5$$, $$x\_2=5$$, $$n\_2=11$$, $$m\_1=11$$, $$m\_1^{-1}=1\space(!!!!\mod 5)$$, $$c\_1=11\cdot 1=11$$, $$m\_2=5$$, $$m\_2^{-1}=9\space(!!!!\mod 11)$$ and $$c\_2=5 \cdot 9=45$$. Thus, $$x=11\cdot4+45\cdot 5\space(!!!!\mod 55)$$. All solutions are of the form $$49+55k$$ for arbitrary integers $$k$$. ### 31.5-2 We follow the steps outlined in Theorem 31.27. We have $$m\_1=56$$, $$m\_1^{-1}=5\space(!!!!\mod 9)$$, $$c\_1=280$$, $$m\_2=63$$, $$m\_2^{-1}=7\space(!!!!\mod 8)$$, $$c\_2=441$$, $$m\_3=72$$, $$m\_3^{-1}=4\space(!!!!\mod 7)$$ and $$c\_3=288$$. Thus, $$x=1 \cdot 280+2\cdot 441+3\cdot 288\space(!!!!\mod 504)$$. All solutions are of the form $$10+504k$$ for arbitrary integers $$k$$. ### 31.5-3 Let $$x=a^{-1}\space(!!!!\mod n)$$. We simply employ equation (31.30) and Corollary 31.29 to get that $$ax=1\space(!!!!\mod n)$$ has a component-wise modular representation of $$(1,1,\dots,1)$$, where every component is $$a\_ix\_i=1\space(!!!!\mod n\_i)$$. Therefore, $$x\_i=a\_i^{-1}\space(!!!!\mod n\_i)$$. This correspondence works in both directions. ### 31.5-4 Let $$n=\prod\_{i=1}^k n\_i$$, where all terms of this product are pairwise relatively prime. According to Theorem 31.27, there is a one-to-one correspondence between a root of the equation $$f(x)=0\space(!!!!\mod n)$$ and its component-wise modular representation. Based on Corollary 31.29, we also have that $$f(x)=0\space(!!!!\mod n)$$ if and only if $$f(x)=0\space(!!!!\mod n\_i)$$ for $$i=1,2,\dots,k$$. Furthermore, by the basic rules of modular arithmetic $$f(x)=0\space(!!!!\mod n\_i) \iff f(x !!!\mod n\_i)=0\space(!!!!\mod n\_i)$$. Let a $$k$$-tuple $$(x\_1,x\_2,\dots,x\_k) \in \Zeta\_{n\_1} \times \Zeta\_{n\_2} \times \dots \times \Zeta\_{n\_k}$$ be one solution of the system of equations $$f(x\_i)=0\space(!!!!\mod n\_i)$$ for $$i=1,2,\dots,k$$. Consequently, $$x \in \Zeta\_n$$ computed from inputs $$(x\_1,x\_2,\dots,x\_k)$$, by following the steps from Theorem 31.27, represents a zero of $$f$$ modulo $$n$$. By the fundamental counting principle, the total number of ways to form a valid $$k$$-tuple $$(x\_1, x\_2, \dots, x\_k)$$ is exactly the product of the number of valid choices for each coordinate. Therefore, the number of roots modulo $$n$$ equals the product of the number of roots modulo each $$n\_i$$. ### 31.6-1
ElementOrder
11
210
35
45
55
610
710
810
95
102
The smallest primitive root is 2 and the indices $$ind\_{11,2}(x)$$ of $$x \in \Zeta\_{11}^\*$$ are shown below.
ElementIndex
10
21
38
42
54
69
77
83
96
105
### 31.6-2 $$ x^2=1\space(!!!!!!\mod p^e) \iff p^e|x^2-1 \iff p^e|(x-1)(x+1). $$ ### 31.6-3 Replace lines 6 and 7 with the following two lines: ``` else d = Modular-Exponentiation(a,(b-1)/2, n) // b is odd return (a*((d*d) mod n)) mod n ``` ### 31.6-4 Below is the iterative modular repeated squaring algorithm in Python 3. ```python def modular_exponentiation(a, b, n): result = 1 d = a % n while b > 0: if b % 2 == 1: result = (result * d) % n d = (d * d) % n b >>= 1 return result ``` ### 31.6-5 By Euler's theorem we know that $$a^{\phi(n)}=1\space(!!!!\mod n) \iff aa^{\phi(n)-1}=1\space(!!!!\mod n)$$. Therefore, we can calculate the inverse by calling $$\text{Modular-Exponentiation}(a, \phi(n)-1,n)$$. ### 31.7-1 $$\phi(n)=(p-1)(q-1)=280$$, so $$d=187\space(!!!!\mod 280)$$. The encryption of the message $$M=100$$, by equation (31.37), is $$P(100)=254$$. You can test that everything is proper by calling $$\text{Modular-Exponentiation}(254, 187,319)$$ (see [Exercise 31.6-4](#id-31.6-4)) and getting back the original message 100. ### 31.7-2 Let$$$$$$\beta$$ denote the number of bits in $$n=pq$$ and assume that $$p$$ and $$q$$ are large primes. As $$e=3$$, we have $$3d=1\space(!!!!\mod \phi(n))$$ that is equivalent to $$3d-1=k(p-1)(q-1)$$ for some integer $$k$$. Since $$0\n \implies k=2$$. We can find $$x=p+q=n-(3d-1)/k+1$$. Plugging in $$q=n/p$$ into the expression for $$x$$ we get $$x=p+n/p \implies n=p(x-p)$$. The last equation can be solved for $$p$$ using the [quadratic formula](https://en.wikipedia.org/wiki/Quadratic_formula). Obviously, once we have $$p$$ we can trivially find $$q$$. All listed steps (including the integer square root) can be executed in time polynomial in $$\beta$$, hence the whole process is also doable in time polynomial in $$\beta$$. ### ★ 31.7-3 $$ \begin{align\*} P\_A(M\_1)P\_A(M\_2) &= M\_1^eM\_2^e\space(!!!!!!\mod n) \\ &= (M\_1M\_2)^e\space(!!!!!!\mod n) \\ &= P\_A(M\_1M\_2). \end{align\*} $$ Suppose an attacker possesses a ciphertext $$C\_A=P\_A(M\_A)$$. She/he executes the following procedure to reveal $$M\_A$$: 1. Generate a new message $$M\_R \in \Zeta\_n^\*$$. 2. Compute $$C=C\_AP\_A(M\_R)$$. 3. Try to decrypt $$C$$ and store the result into $$M$$. 4. If successful, then find $$M\_R^{-1}$$ modulo $$n$$ and compute $$M\_A=(MM\_R^{-1}\bmod n)$$. 5. Goto step 1. The chance of success at step 3 is 1%. The number of trials follows the geometric distribution with an expected value of 100. Finding inverses modulo $$n$$ is step 4 can be efficiently carried out using the extended Euclid's GCD algorithm. Almost all generated messages at step 1 will be relatively prime to $$n$$, since the chance of stumbling across one that contains a prime factor of $$n$$ is practically zero. All in all, an attacker can reveal the original message with high probability. ### 31.8-1 One example is $$n=7\cdot5=35$$, where 6 is a nontrivial square root of 1 modulo 35, since $$6^2=1\space(!!!!\mod 35)$$. Such a root always exists for $$n$$ that satisfies the conditions from this exercise. Decompose $$n$$ into a product $$n\_1n\_2$$, where $$n\_1$$ and $$n\_2$$ are odd numbers greater than 1 that are relatively prime to each other. By Corollary 31.28, there exists an $$x$$ simultaneously satisfying the equations $$ \begin{align\*} x&=-1\space (!!!!!\mod n\_1) \\ x&=\space\space\space1\space (!!!!!\mod n\_2). \end{align\*} $$ Corollary 31.29 gives that $$x\neq±1\space (!!!!\mod n)$$. On the other hand, we have $$ \begin{align\*} x^2&=1\space (!!!!!\mod n\_1) \\ x^2&=1\space (!!!!!\mod n\_2). \end{align\*} $$ Corollary 31.29 gives that $$x^2=1\space (!!!!\mod n)$$. Therefore, $$x$$ is a nontrivial square root of 1 modulo $$n$$. ### ★ 31.8-2 In number theory, $$\lambda(n)$$ is known as the [Carmichael function](https://en.wikipedia.org/wiki/Carmichael_function). Euler’s phi function is a multiplicative function that we can see after substituting $$n=\prod\_{i=1}^rp^{e\_i}$$ to get $$ \begin{align\*} \phi(n)&=\phi(p\_1^{e\_1}\dots p\_r^{e\_r}) \\ &=p\_1^{e\_1}\dots p\_r^{e\_r}(1-1/p\_1) \dots (1-1/p\_r) && \text{(by equation (31.21))} \\ &=p\_1^{e\_1-1}(p\_1-1)\dots p\_r^{e\_r-1}(p\_r-1) \\ &=\phi(p\_1^{e\_1})\dots\phi(p\_r^{e\_r}) && \text{(by Exercise (31.3-4))}. \end{align\*} $$ It follows that $$\phi(n)$$ is a multiple of $$\lambda(n)$$, thus $$\lambda(n)\mid \phi(n)$$. Another proof, based on group theory, is given [here](https://en.wikipedia.org/wiki/Carmichael_function#%CE%BB\(n\)_divides_%CF%86\(n\)). Suppose for the sake of contradiction that a Carmichael number $$n$$ is not "square-free," thus it has a factor $$p\_i^{e\_i}$$ where $$e\_i>1$$. Consequently, $$p\_i\mid \phi(p\_i^{e\_i}) \implies p\_i\mid \lambda(n)$$. Furthermore, $$p\_i\mid n \implies p\_i \nmid n-1$$, which is a contradiction with the property that $$\lambda(n)\mid n-1$$. Therefore, $$n$$ must be "square-free." Suppose for the sake of contradiction that a Carmichael number $$n$$ is a product of two primes $$p\ (1+\lg b)\lg (q+1) \\ &> (1 + \lg b) \frac{1}{2}(1 + \lg q) \\ &> \frac{1}{2} \lg b (1 + \lg q). \end{align\*} $$ We have proven that $$O((1 + \lg q)\lg b)=O(\mu(a,b) - \mu(b,r))$$. #### c. As shown in part (b), EUCLID takes at most $$c(\mu(a,b)-\mu(b,a \space !!!!\mod b))$$ bit operations on the first recursive call, at most $$c(\mu(b,a \space !!!!\mod b)-\mu(a \space !!!!\mod b, b\space !!!\mod (a \space !!!!\mod b)))$$ on the second, and so on. This sum telescopes, hence we end up with $$c\mu(a,b)-O(1)=O(\mu(a,b))$$. When applied to two $$\beta$$-bit inputs we get $$O(\mu(a,b))=O((1+\beta)^2)=O(\beta^2)$$. ### 31-3 Three algorithms for Fibonacci numbers #### a. The algorithmic recurrence of the running time is $$T(n)=T(n-1)+T(n-2)+\Theta(1)$$. We use a substitution method to prove that this version cannot do better than being exponential in $$n$$. The constant $$c\_1>0$$ denotes the lower bound in $$\Theta(1)$$. Assume that $$T(n) \ge cF\_n$$ for $$n \ge 2$$. $$ \begin{align\*} T(n)&=T(n-1)+T(n-2)+\Theta(1) \\ &\ge cF\_{n-1}+cF\_{n-2}+c\_1 && \text{(by the inductive hypothesis)} \\ &= cF\_n+c\_1 \\ &>cF\_n \\ &\therefore T(n)=\Omega(F\_n). \end{align\*} $$ This concludes the proof, as Fibonacci numbers grow exponentially. #### b. Here is the Python 3 script showcasing [memoization](https://en.wikipedia.org/wiki/Memoization). The recurrence $$T(n)=T(n-1)+\Theta(1)$$ resolves to $$T(n)=O(n)$$, since memoization prevents repeated work. ```python import functools @functools.cache def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2) print(fib(100)) ``` It will print in the blink of an eye `354224848179261915075`. Try commenting out the annotation to see the difference. #### c. We can leverage the repeated squaring method, with a small change, that instead of multiplying numbers we will work with small constant sized matrices. Each matrix operation will then also take constant time. We prove the next statement using induction on $$n$$, following the hint from the book. $$ \begin{align\*} \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^n &= \begin{bmatrix} F\_{n-1} & F\_n \\ F\_n & F\_{n+1} \end{bmatrix}. \end{align\*} $$ The base case $$n=1$$ obviously holds. For $$n>1$$ we have $$ \begin{align\*} \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^n &= \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{n-1} \\ &= \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} F\_{n-2} & F\_{n-1} \\ F\_{n-1} & F\_n \end{bmatrix} && \text{(by the inductive hypothesis)} \\ &= \begin{bmatrix} F\_{n-1} & F\_n \\ F\_{n-2}+F\_{n-1} & F\_{n-1}+F\_n \end{bmatrix} \\ &= \begin{bmatrix} F\_{n-1} & F\_n \\ F\_n & F\_{n+1} \end{bmatrix} \quad \checkmark \end{align\*} $$ At the end, we need to read out the matching cell containing $$F\_n$$. #### d. Fibonacci numbers have $$\beta=\Theta(n)$$ binary digits, as explained [here](https://en.wikipedia.org/wiki/Fibonacci_sequence#Magnitude). The bare recursive variant still has exponential running time. Increasing the amount of work at each level cannot invalidate the previously established lower bound. The memoized version has a new recurrence $$T(n)=T(n-1)+\Theta(n)$$ that solves to $$T(n)=\Theta(n^2)$$. The matrix version employs both addition and multiplication of numbers, hence it has a new recurrence $$T(n)=T(n/2)+\Theta(n^2)$$. Case 3 of the master theorem states that $$T(n)=\Theta(n^2)$$. ### 31-4 Quadratic residues #### a. Theorem 31.32 implies that $$\Zeta\_p^\*$$ is a cyclic group, so it has a generator $$g$$, where all values $$g^i$$ modulo $$p$$ are distinct for $$i=0,1,\dots,p-2$$. Every even index is associated with a quadratic residue, since $${(g^{i/2}})^2=g^i\space(!!!!\mod p)$$. Thus, the number of quadratic residues is at least $$(p-1)/2$$. Suppose for the sake of contradiction that there is also some odd index $$i$$ such that $$x^2=g^i\space(!!!!\mod p)$$ for some $$x \in \Zeta\_p^\*$$. We must have that $$x=g^j\space(!!!!\mod p)$$ and $$g^{2j}=g^i\space(!!!!\mod p)$$. Theorem 31.33 implies that $$2j=i\space(!!!!\mod \phi(p))$$, where $$\phi(p)=p-1$$. But this is impossible, since $$p-1 \nmid 2j-i$$ due to mismatch in parity. We can conclude that the the number of quadratic residues is exactly $$(p-1)/2$$. #### b. If $$a$$ is a quadratic residue modulo $$p$$, then there is an $$x$$ such that $$ a^{(p-1)/2}=(x^2)^{(pi-1)/2}=x^{p-1}=1=\bigg(\frac{a}{p}\bigg)\space(!!!!!\mod p) \space\space\space\space\text{ (by Fermat's theorem)}. $$ Otherwise, $$g^i=a\space(!!!!\mod p)$$ for some odd index $$i$$ (see part(a)). According to Fermat's theorem $$g^{p-1}=g^0=1\space(!!!!\mod p)$$, so it must be that $$g^{(p-1)/2}=-1\space(!!!!\mod p)$$, as powers of $$g$$ are distinct for $$i=0,1,\dots,p-2$$. We have $$ a^{(p-1)/2}=(g^i)^{(p-1)/2}=(g^{(p-1)/2})^i=(-1)^i=-1=\bigg(\frac{a}{p}\bigg)\space(!!!!!\mod p). $$ We can call `modular_exponentiation(a, (p-1)/2, p)` (see [Exercise 31.6-4](#id-31.6-4)) and check whether the returned value is 1. If we let $$\beta=\lg p$$, then It requires $$O(\beta^3)$$ bit operations. #### c. By part (b), $$a^{(p-1)/2}=a^{2k+1}=1\space(!!!!\mod p)$$, so $$(a^{k+1})^2=a^{2k+2}=a\cdot a^{2k+1}=a\space(!!!!\mod p)$$. Therefore, $$a^{k+1}$$ is a square root of $$a$$ modulo $$p$$. We can again use modular exponentiation to efficiently find it using $$O(\beta^3)$$ bit operations. #### d. Run the algorithm of part (b) by repeatedly trying random numbers $$a \in \[2,p)$$ until $$\big(\frac{a}{p}\big)=-1\space(!!!!\mod p)$$. Half the elements in $$\Zeta\_p^\*$$ are not quadratic residues, thus each experiment can be regarded as a Bernoulli trial with probability 1/2. The expected number of trials follows the geometric distribution and equals 2. The average number of arithmetic operations is $$O(\beta)$$.