Exercise 1

因为N是质数，所以$gcd(u,N) = 1$，所以u在模N下有乘法逆元$u^{-1}$。
$u^{-1}$在模$N$下唯一，故有$a \equiv u^{-1}v \pmod N$，$(0 \leq a \leq N)$，使得$au \equiv v \pmod N$

Exercise 2

证明

对 $b$ 进行归纳。
$b = 1$时。此时 $a \geq 1$，算法直接计算 $a = q \cdot 1 + 0$，返回 $(0, 1, 1)$，满足 $|0| \leq 1$ 且 $|1| \leq a$。
归纳步骤：假设对所有小于 $b$ 的正整数结论成立。考虑 $b \geq 2$。令 $a = qb + r$，其中 $0 \leq r < b$。

$$ |x| = |y'| \leq b, \quad |y| = |x' - q y'| \leq |x'| + q|y'| \leq r + qb = a. $$

因此结论成立。

计算 $\text{EXTENDED-EUCLID}(11, 25)$

  1. $a = 11, b = 25$，$q = 0, r = 11$，递归 $\text{EXTENDED-EUCLID}(25, 11)$。
  2. $a = 25, b = 11$，$q = 2, r = 3$，递归 $\text{EXTENDED-EUCLID}(11, 3)$。
  3. $a = 11, b = 3$，$q = 3, r = 2$，递归 $\text{EXTENDED-EUCLID}(3, 2)$。
  4. $a = 3, b = 2$，$q = 1, r = 1$，递归 $\text{EXTENDED-EUCLID}(2, 1)$。
  5. $a = 2, b = 1$，$q = 2, r = 0$，递归 $\text{EXTENDED-EUCLID}(1, 0)$。
  6. $a = 1, b = 0$，返回 $(1, 0, 1)$。

回溯：

因此，$\text{EXTENDED-EUCLID}(11, 25)$ 的输出为 $(-9, 4, 1)$。
即$-9 \cdot 11 + 4 \cdot 25 = 1$

Exercise 3

(i)

$(d, x_0, y_0) \gets \text{ExtendedEuclid}(a, N)$
if $d \nmid b$ then
return ``no solution''
else
$a' \gets a / d$
$b' \gets b / d$
$N' \gets N / d$
$\mathit{inv} \gets x_0 \bmod N'$
$x \gets (\mathit{inv} \cdot b') \bmod N'$
return $x$
end if

(ii)

$(d, x_0, y_0) \gets \text{ExtendedEuclid}(a, N)$
if $d \nmid b$ then
return $\emptyset$
else
$a' \gets a / d$
$b' \gets b / d$
$N' \gets N / d$
$\mathit{inv} \gets x_0 \bmod N'$
$x_0 \gets (\mathit{inv} \cdot b') \bmod N'$
$S \gets \emptyset$
for $t \gets 0$ to $d-1$ do
$x \gets x_0 + t \cdot N'$
$S \gets S \cup \{x\}$
end for
return $S$
end if

扩展欧几里得算法 $O(logN)$，输出 $d$ 个解。 $d$ 很大，输出规模本身即 $Θ(d)$

(iii)

设 $d=gcd(a,N)$。存在解当且仅当 $d∣b$ 且 $d∣b′$，此时解集大小为 d。
因此若$S(a,b,N)≠∅$ 且 $S(a,b′,N)≠∅$，则

$$∣S(a,b,N)∣=∣S(a,b′,N)∣=d.$$

Exercise 4

(i)

if $N = 1$ then
return $\textbf{true}$
end if
$\mathit{lo} \gets 1$
$\mathit{hi} \gets N$
while $\mathit{lo} \le \mathit{hi}$ do
$\mathit{mid} \gets \lfloor (\mathit{lo} + \mathit{hi}) / 2 \rfloor$
$\mathit{square} \gets \mathit{mid} \times \mathit{mid}$
if $\mathit{square} = N$ then
return $\textbf{true}$
else
if $\mathit{square} < N$ then
$\mathit{lo} \gets \mathit{mid} + 1$
else
$\mathit{hi} \gets \mathit{mid} - 1$
end if
end if
end while
return $\textbf{false}$

二分查找需 $O(logN)$ 步，每步计算一次乘法，时间复杂度为 $O((logN)^2)$

(ii)

若 $N=q^k$（$k>1，q≥2）$，则 $N≥2^k$，取对数得 $k≤log_2N$。当 $N=1$ 时，可视为平凡情况。

(iii)

if $N = 1$ then
return $\textbf{true}$
end if
for $k \gets 2$ to $\lfloor \log_2 N \rfloor$ do
$\mathit{lo} \gets 1$
$\mathit{hi} \gets N$
while $\mathit{lo} \le \mathit{hi}$ do
$\mathit{mid} \gets \lfloor (\mathit{lo} + \mathit{hi}) / 2 \rfloor$
$\mathit{power} \gets \mathit{mid}^{k}$
if $\mathit{power} = N$ then
return $\textbf{true}$
else
if $\mathit{power} < N$ then
$\mathit{lo} \gets \mathit{mid} + 1$
else
$\mathit{hi} \gets \mathit{mid} - 1$
end if
end if
end while
end for
return $\textbf{false}$

循环次数 $O(logN)$，每次二分查找 $O(logN)$ 步，每步计算 $q^k$ 需 $O(logk)$次乘法（快速幂），总时间复杂度为 $O((logN)^3loglogN)$

Exercise 5

已知 $561=3×11×17$ 是卡迈克尔数。
同余式 $a^{560} \equiv 1 \pmod {561}$ 等价于同时满足

$$a^{560} \equiv 1 \pmod{3}, \quad a^{560} \equiv 1 \pmod{11}, \quad a^{560} \equiv 1 \pmod{17}$$

对每个素数因子 $p \in \{3,11,17\}$，有 $p−1∣560$。由费马小定理，若 $p∤a$，则 $a^{p-1} \equiv 1 \pmod {p}$，从而 $a^{560} \equiv 1 \pmod {p}$； 若 $p∣a$，则 $a^{560} \equiv 0 \pmod {p}$。
因此条件等价于 $a$ 与 $3,11,17$ 均互素，即 $gcd(a,561)=1$。
在 $1≤a<561$ 中，与 $561$互素的个数为
$φ(561)=φ(3)φ(11)φ(17)=2×10×16=320$.
故满足条件的 $a$ 共有 $320$ 个