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 on Wikipedia.

31.1-3 🌟

Proves that the $a \mid b$ relation is transitive.

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<p \implies p \nmid k$. Therefore, $\gcd⁡(k, p)=1$.

31.1-5

We start from the fact that $\gcd(a,n)=1$, thus

$$\begin{align*} 1 &= ax+ny && \text{(by Theorem (3.12))} \\ b &= abx +nby && \text{(after multiplying both sides by } b \text{)} \\ b &= nkx+nby && \text{(} n \mid ab \implies ab=kn \text{)} \\ b &= n(kx+by) \\ &\therefore n|b. \end{align*}$$

31.1-6 🌟

Proves that for all integers $a$ and $b$ and all primes $p$, $(a + b)^p = a^p + b^p \quad(\!\!\!\mod p)$.

Lemma 1

For any integers $a_1,a_2,\dots,a_n$ and $p$, if $\gcd(a_i,p)=1$ for all $i=1,2,\dots,n$, then $\gcd(\prod_{i=1}^n a_i,p)=1$.

Proof We prove the lemma by induction on $n$. The base case $n=2$ trivially holds by Theorem 31.6. For $n>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 and Lemma 1, for $0<k<p$, $\gcd(k!,p)=1$ and $\gcd((p-k)!,p)=1$, so $\gcd(k!(p-k)!, p) = 1$. By Theorem 31.7 we can conclude that $p \mid \binom{p}{k}$. Thus, in a binomial expansion all terms except the first and last one are divisible by $p$, which concludes the proof.

31.1-7

We successively apply the Division theorem, thus

$$\begin{align*} x &= q'b + (x \!\!\!\!\mod b) \\ &= q'ka + (x \!\!\!\!\mod b) && \text{(} a\mid b \implies b=ka \text{)} \\ &= q'ka + q''a + ((x \!\!\!\!\mod b) \!\!\!\!\mod a) \\ &= (q'k+q'')a+((x \!\!\!\!\mod b) \!\!\!\!\mod a) \\ &\therefore (x \!\!\!\!\mod b) \!\!\!\!\mod a = x \!\!\!\!\mod a, \end{align*}$$

because $0 \le ((x \bmod b) \bmod a) < a$, so it represents a unique remainder modulo $a$.

For the second part, we get

$$\begin{align*} x &= y \space(\!\!\!\!\!\! \mod b) \\ x \!\!\!\!\mod b &= y \!\!\!\!\mod b \\ (x \!\!\!\!\mod b) \!\!\!\!\mod a &= (y \!\!\!\!\mod b) \!\!\!\!\mod a \\ x \!\!\!\!\mod a &= y \!\!\!\!\mod a && \text{(by the first part)} \\ x &= y \space(\!\!\!\!\!\! \mod a). \end{align*}$$

31.1-8

Assume that multiplication of two $\beta$-bit integers requires $O(\beta^2)$ time and equality test of two $\beta$-bit integers requires $O(\beta)$ time. The algorithm below only showcases an existence of a solution in time polynomial in $\beta$ without claiming anything about its asymptotic optimality. As a matter of fact, it is far from being optimal.

The smallest candidate is $a=2$ and $2^\beta>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 🌟

Proves that the $\gcd$ operator is associative.

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 that uses only facts mentioned in the book.

31.1-12

The $O(\beta^2)$ time algorithm shown here 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 is a powerful technique in algorithm design. The steps to accomplish this are laid out below:

1

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$.

2

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).

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.

1

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)$.

2

Base case

If $d=1$ then return the single digit representation of $n$.

3

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$.

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 with a derailed solution.

31.2-1

You can read the proof here. 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.

31.2-2

We create a table, similar to Figure 31.1 from the book, by running the next Python 3 script.

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 🌟

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$.

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.

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 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 <j \le n$. We have two cases:

1. If $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*}$$

Exercise 31.1-10 proves that the $\gcd$ operator is associative. This property extends to arbitrary number of arguments due to the generalized associative law.

$$\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, 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 🌟

Shows how to compute a generalized least common multiple using the binary $\gcd$ operator.

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.

1

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 <r$ partition the set of input numbers into two groups:

   1. $A_j=\{n_i:\text{the }j\text{th bit from the right in the binary form of }i \text{ is }1\}$

   2. $B_j=\{n_i:\text{the }j\text{th bit from the right in the binary form of }i \text{ is }0\}$

3. For each $j$ produce $a_j=\prod_{n \in A_j} n$ and $b_j=\prod_{n \in B_j} n$, thus forming $r$ pairs $(a_j,b_j)$.

2

Proving correctness

If the set of input numbers are pairwise relatively prime, then $\gcd(n_s,n_t)=1$ for $s \neq t$. Fix any $j$. Suppose for the sake of contradiction that some prime $p\mid a_j$ and $p\mid b_j$. Consequently, there are some distinct numbers $n_s \in A_j$ and $n_t \in B_j$ such that $p\mid n_s$ and $p\mid n_t$. But that contradicts the initial assumption about our set of input numbers. Thus, no such prime exists, and $\gcd(a_j,b_j)=1$ for all $j$, as our choice of $j$ was arbitrary.

If the derived pairs are relatively prime, then $\gcd(a_j,b_j)=1$ for all pairs. Take any two distinct indices $s$ and $t$ that differ at bit position $j$. WLOG assume that $s$ has 1 and $t$ has 0. Therefore, $n_s \in A_j$ and $n_t \in B_j$. Suppose for the sake of contradiction that some prime $p\mid n_s$ and $p\mid n_t$. But we know that $n_s\mid a_j$ and $n_t\mid b_j$, so this implies that $p\mid a_j$ and $p\mid b_j$. But that contradicts the initial assumption about derived pairs being relatively prime. Therefore, the set of input numbers are pairwise relatively prime, since our choice of indices $s$ and $t$ was arbitrary.

3

Explaining the special case

For $k=4$ we see that $A_0=\{n_1,n_3\}$, $A_1=\{n_2,n_3\}$, $B_0=\{n_0,n_2\}$ and $B_1=\{n_0,n_1\}$. Therefore, the derived pairs are $(n_1n_3,n_0n_2)$ and $(n_2n_3, n_0n_1)$. They all satisfy the properties of being pairwise relatively prime. Notice that we are using 0-based indexing, so just shift indices by one to map them to those from the book.

31.3-1

$$\def\arraystretch{1.5} \begin{array}{c:c:c:c:c} +_4 & 0 & 1 & 2 & 3 \\ \hdashline 0 & 0 & 1 & 2 & 3 \\ \hdashline 1 & 1 & 2 & 3 & 0 \\ \hdashline 2 & 2 & 3 & 0 & 1 \\ \hdashline 3 & 3 & 0 & 1 & 2 \end{array}$$

$$\def\arraystretch{1.5} \begin{array}{c:c:c:c:c} \cdot_5 & 1 & 2 & 3 & 4 \\ \hdashline 1 & 1 & 2 & 3 & 4 \\ \hdashline 2 & 2 & 4 & 1 & 3 \\ \hdashline 3 & 3 & 1 & 4 & 2 \\ \hdashline 4 & 4 & 3 & 2 & 1 \end{array}$$

Here are two possible mappings:

1. $f(0)=1,f(1)=3,f(2)=4,f(3)=2$

2. $f(0)=1,f(1)=2,f(2)=4,f(3)=3$

31.3-2

Subgroups of $\Zeta_9$ are $\{0\}$, $\{0,3,6\}$ and $\Zeta_9$ itself. Subgroups of $\Zeta_{13}^*$ are $\{1\}$, $\{1,12\}$, $\{1,3,9\}$, $\{1,5,8,12\}$, $\{1,3,4,9,10,12\}$ and $\Zeta_{13}^*$ itself.

31.3-3 🌟

Introduces the cancellation law from the parent group to prove properties of a subgroup.

We only need to show two things (since associativity is automatically inherited from $\oplus$):

• The identity element $e \in S'$.

• Every element $a \in S'$ has its inverse $a^{-1} \in S'$.

Choose any fixed element $a \in S'$. Define a modular function $f_a: S' \to S'$ such that $f_a(x) = a \oplus x$ (see also Exercise 31.3-5). Suppose $f_a(x) = f_a(y)$ for some $x, y \in S'$. This means $a \oplus x = a \oplus y$. Because $a, x$ and $y$ also belong to the parent group $S$, we know $a$ has an inverse $a^{-1} \in S$. If we left-multiply both sides by $a^{-1}$, we get $x=y$. Because $f_a(x) = f_a(y) \implies x = y$, the function $f_a$ is injective. Since $S'$ is finite, this entails that $f_a$ is surjective, too. In other words, $f_a$ is a bijection.

Because $a \in S'$ and $f_a$ is bijective, there must be some element $b \in S'$ that maps to $a$. This gives

$$f_a(b) = a \implies a \oplus b = a.$$

In the parent group $S$, the only element that satisfies this equation is the identity element $e$. Therefore, $b=e$. Since $b \in S'$, we have proven that $e \in S'$.

Because $e \in S'$ and $f_a$ is bijective, there must be some element $b \in S'$ that maps to $e$. This gives

$$f_a(b) = e \implies a \oplus b = e.$$

In the parent group $S$, the only element that satisfies this equation is the inverse element $a^{-1}$. Therefore, $b=a^{-1}$. Since $b \in S'$, we have proven that $a^{-1} \in S'$.

31.3-4

Apply equation (31.21) to get

$$\phi(p^e)=p^e\bigg(1-\frac{1}{p}\bigg)=p^e\bigg(\frac{p-1}{p}\bigg)=p^{e-1}(p-1).$$

31.3-5

We proceed by showing the $f_a$ is a bijection. Any bijection from a set to itself is a permutation of that set. Since the domain and codomain of $f_a$ are of the same cardinality, it is enough to show that $f_a$ is a surjective function.

According to Theorem 31.13, $\Zeta_n^*$ is a finite abelian group. Consequently, $a^{-1} \in \Zeta_n^*$. Select any $b \in \Zeta_n^*$. For $a^{-1}b \in \Zeta_n^*$, we get

$$f_a(a^{-1}b)=a(a^{-1}b)\!\!\!\!\mod n=(aa^{-1})b\!\!\!\!\mod n=b \!\!\!\!\mod n=b.$$

31.4-1

We have $a=35$, $n=50$ and $b=10$. The extended version of Euclid's algorithm returns $(5,3,-2)$, so $d=5$ and $x_0=3(10/5)=6$. The step size is $50/5=10$, thus all solutions are $\{6,16,26,36,46\}$.

31.4-2

Based on Corollary 31.26, there is a multiplicative inverse $a^{-1}\!\!\mod n$, so multiplying both sides of $ax=ay\space(\!\!\!\!\mod n)$ by $a^{-1}$ we get $a^{-1}ax=a^{-1}ay\space(\!\!\!\!\mod n)$, which implies that $x=y\space(\!\!\!\!\mod n)$.

If $\gcd(a,n)>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 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 🌟

Explains the factor theorem applied modulo $p$.

I recommend reading the proof based on Euclidean division of polynomials, which is aligned with the narrative from the book.

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$.

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

Element	Order
1	1
2	10
3	5
4	5
5	5
6	10
7	10
8	10
9	5
10	2

The smallest primitive root is 2 and the indices $ind_{11,2}(x)$ of $x \in \Zeta_{11}^*$ are shown below.

Element	Index
1	0
2	1
3	8
4	2
5	4
6	9
7	7
8	3
9	6
10	5

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.

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) 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<d<\phi(n)$ we know that $k=1 \lor k=2$. We can rewrite the previous expression as $3d-1=k(n-(p+q)+1)$. Apparently, $3d-1<n \implies k=1$ and $3d-1>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. 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.

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.

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<q$. We have that $\lambda(n)=\text{lcm}(p-1,q-1) \implies q-1\mid \lambda(n)$. On the other hand, $q-1 \nmid n-1$ because by the Division theorem we have $n-1=pq-1=(q-1)p+(p-1)$. But this is again a contradiction with the property that $\lambda(n)\mid n-1$. Therefore, $n$ must be consisted of at least three primes.

31.8-3

By Exercise 31.6-2 we have $x^2=1\space(\!\!\!\!\mod n) \iff n\mid (x-1)(x+1)$. If $x$ is a nontrivial square root of 1 modulo $n$, then by Corollary 31.35 $n$ is composite, so $2<x<n-1$ (you can easily check that $x=2$ produces a prime $n=3$). It follows that $n \nmid x-1$ and $n \nmid x+1$, thus prime factors of $n$ are distributed between these two terms of a product. Therefore, $\gcd(x-1,n)$ and $\gcd(x+1,n)$ are both nontrivial divisors of $n$.

Problems

31-1 Binary gcd algorithm

a.

By Corollary 31.4, we have $\gcd(a,b)=\gcd(2(a/2),2(b/2))=2\gcd(a/2,b/2)$.

b.

By equation (31.13), $\gcd(a,b)$ doesn't have a prime factor 2. Dividing $b$ by 2 reduces the exponent of 2 in $b$, hence making it closer to zero. Consequently, $\gcd(a,b)=\gcd(a,b/2)$.

c.

Let $d_1=\gcd(a,b)$ and $d_2=\gcd(a-b,b)$. 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 b$, so by equation (31.4) we have $d_1\mid a-b$. Based on Corollary 31.3 we can conclude that $d_1\mid d_2$

We know that $d_2\mid a-b$ and $d_2\mid b$, so by equation (31.4) we have $d_2\mid (a-b)+b=a$. Based on Corollary 31.3 we can conclude that $d_2\mid d_1$.

Since $a-b$ is even and $b$ is odd, the division of $a-b$ by 2 is justified according to part (b).

d.

I recommend reading this study of the binary GCD algorithm with insightful C++ based optimizations.

31-2 Analysis of bit operations in Euclid’s algorithm

In all subproblems below assume that $1<b \le a$, so that $q \ge 1$.

a.

We do all the arithmetic in binary by processing the bits of $a$ from the most significant to the least, accumulating the initial $O(\lg b)$ bits of $a$ into a value (current residue $r$) greater or equal than $b$, as they would anyhow produce leading zeros of a quotient.

In the analysis of the long division algorithm, the bits of the quotient and the divisor are counted differently because they play distinct roles. Each bit of $q$ is determined in one step of the algorithm. Thus, the number of steps required to compute all bits of $q$ is proportional to it's number of bits $\lfloor \lg q \rfloor+1=O(1+\lg q)$. This expression is nonzero even if $q \le1$.

The algorithm still requires at least one step to compare $a$ and $b$ even if $q=0$ (when $a<b)$. The expression $1+\lg q=1+0=1$ aims to encompass this case, despite $\lg q$ being undefined here.

At each step, the algorithm performs operations (e.g., comparisons or subtractions) involving the divisor $b$. Since it has approximately $O(\lg b)$ bits, these operations require that many bit operations per step. Therefore, the total count is $O(1+\lg q) \times O(\lg b)=O((1+\lg q)\lg b)$. This complexity reflects that the algorithm's time is dominated by the number of quotient bits (steps) and the size of the divisor (cost per step).

The remainder $r$ gets calculated along the way (see also Exercise 31.1-12) and has $O(\lg b)$ bits.

b.

The reduction requires us to compute the remainder that can be accomplished in time as given in part (a). We know that $a=qb+r$, where $0 \le r < b$.

$$\begin{align*} \mu(a,b)-\mu(b,a \space \!\!\!\!\!\mod b) &= \mu(a,b)-\mu(b,r) \\ &=(1+\lg a)(1+\lg b)-(1+\lg b)(1+\lg r) \\ &=(1+\lg b)(\lg a-\lg r) \\ &= (1+\lg b)\lg\left(q\frac{b}{r} + 1\right) \\ &> (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. The recurrence $T(n)=T(n-1)+\Theta(1)$ resolves to $T(n)=O(n)$, since memoization prevents repeated work.

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.

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) 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)$.