Exercise 1

Find the smallest $a$
function Min($N$)
for $a \gets 2$ to $N-1$ do
if $\gcd(a,N)=1$ then
return $a$
end if
end for
return $N-1$
end function

Exercise 2

令 $\varphi(N) = (p-1)(q-1)$。由题，有

$$ ed \equiv 1 \pmod{\varphi(N)}. $$

已知 $e = 3$，故存在正整数 $k$ 使得

$$ 3d - 1 = k\varphi(N). $$

由于 $\varphi(N)$ 是偶数，$3d - 1$ 也是偶数，可写为

$$ 3d - 1 = s \cdot 2^{t}, $$

其中 $s$ 为奇数，$t \ge 1$。

从 $2,3,\dots,N-1$ 中随机选取一个整数 $a$。计算

$$ x_{0} = a^{s} \bmod N, $$

然后迭代

$$ x_{i} = x_{i-1}^{2} \bmod N \quad (i = 1,2,\dots). $$

由于 $a^{3d-1} = (a^{s})^{2^{t}} \equiv 1 \pmod{N}$（当 $\gcd(a,N)=1$ 时由欧拉定理保证；若 $\gcd(a,N)>1$ 则直接得到因子），序列 $x_{0}, x_{1}, \dots$ 最终必达到 $1$。设 $i_{0}$ 是使得 $x_{i}=1$ 的最小非负整数，则 $x_{i_{0}-1}$ 满足 $x_{i_{0}-1}^{2} \equiv 1 \pmod{N}$ 且 $x_{i_{0}-1} \not\equiv 1 \pmod{N}$（除非 $i_{0}=0$，此时 $x_{0}=1$ 则需另选 $a$）。若 $x_{i_{0}-1} \equiv -1 \pmod{N}$，则本次选择失败；否则 $x_{i_{0}-1}$ 是 $1$ 的一个非平凡平方根，即

$$ x_{i_{0}-1}^{2} \equiv 1 \pmod{N},\quad x_{i_{0}-1} \not\equiv \pm 1 \pmod{N}. $$

此时

$$ \gcd(x_{i_{0}-1} - 1, N) \quad \text{或} \quad \gcd(x_{i_{0}-1} + 1, N) $$

必为 $N$ 的一个非平凡因子（即 $p$ 或 $q$）。

随机选取的 $a$ 至少有 $1/2$ 的概率使得上述过程成功重复多次可保证以高概率分解 $N$，且每一步计算均为多项式时间，因此能高效分解 $N$。

Exercise 3

证明存在常数 $c, d > 0$，使得对于足够大的 $n$，有：

$$T(n) \leq c \cdot n^{\log_2 3} - d \cdot n$$

假设对于所有 $k < n$，结论成立。即：

$$T(k) \leq c \cdot k^{\alpha} - d \cdot k \quad (\text{其中 } \alpha = \log_2 3)$$

将假设代入原递归式 $T(n) = 2T(\lceil n/2 \rceil) + T(\lceil n/2 \rceil + 1) + O(n)$。
设 $O(n) \leq a \cdot n$（$a$ 为常数）。

$$\begin{aligned} T(n) &\leq 2\left(c \lceil n/2 \rceil^\alpha - d \lceil n/2 \rceil \right) + \left(c (\lceil n/2 \rceil + 1)^\alpha - d (\lceil n/2 \rceil + 1) \right) + an \\ &\leq 3c \left( \frac{n+3}{2} \right)^\alpha - 3d \left( \frac{n}{2} \right) + an \\ \end{aligned}$$

当 $n$ 很大时，$(\frac{n+3}{2})^\alpha = (\frac{n}{2})^\alpha (1 + \frac{3}{n})^\alpha \approx (\frac{n}{2})^\alpha (1 + \frac{3\alpha}{n})$：

$$\begin{aligned} T(n) &\leq 3c \cdot \frac{n^\alpha}{2^\alpha} \left( 1 + \frac{3\alpha}{n} \right) - 1.5dn + an \\ \end{aligned}$$

因为 $2^\alpha = 2^{\log_2 3} = 3$，所以 $\frac{3c}{2^\alpha} = c$：

$$\begin{aligned} T(n) &\leq c n^\alpha + \frac{3c \alpha n^{\alpha-1}}{1} - 1.5dn + an \\ &= c n^\alpha - dn - (0.5dn - 3c\alpha n^{\alpha-1} - an) \end{aligned}$$

所以有：

$$T(n) = O(n^{\log_2 3})$$

Exercise 4

Fixed point in sorted array
$l \gets 1$
$r \gets n$
while $l < r$ do
$mid \gets \lfloor (l + r) / 2 \rfloor$
if $A[mid] = mid$ then
return $mid$
else if $A[mid] < mid$ then
$l \gets mid + 1$
else
$r \gets mid$
end if
end while
print ``No solution''

Exercise 5

(1)

对步数$t$作归纳：
$t=0$时，显然$I[1 \dots n]$是完全相同的。
假设$k(k

(2)

Strongly comparison-based merge sort
function StrongMergeSort($a[1..n]$)
$idx[1..n] \gets [1,2,\dots,n]$
call MergeSort($a, idx, 1, n$)
return $idx$
end function
function MergeSort($a, idx, l, r$)
if $l < r$ then
$m \gets \lfloor (l+r)/2 \rfloor$
call MergeSort($a, idx, l, m$)
call MergeSort($a, idx, m+1, r$)
call Merge($a, idx, l, m, r$)
end if
end function
function Merge($a, idx, l, m, r$)
$tmp[1..r-l+1]$
$i \gets l$, $j \gets m+1$, $k \gets 1$
while $i \le m$ and $j \le r$ do
if $a[idx[i]] \le a[idx[j]]$ then
$tmp[k] \gets idx[i]$
$i \gets i+1$
else
$tmp[k] \gets idx[j]$
$j \gets j+1$
end if
$k \gets k+1$
end while
while $i \le m$ do
$tmp[k] \gets idx[i]$
$i \gets i+1$, $k \gets k+1$
end while
while $j \le r$ do
$tmp[k] \gets idx[j]$
$j \gets j+1$, $k \gets k+1$
end while
for $k \gets 1$ to $r-l+1$ do
$idx[l+k-1] \gets tmp[k]$
end for
end function

以上的归并排序满足强比较算法的所有特性，故归并排序是强比较的

(3)

可以用一棵决策树表示，每个节点代表一次比较，两个分支对应一次比较的真假，每个叶子可以输出一个排列。而这棵决策树有$n!$个叶子，设其为一棵高度为$h$的完全二叉树，则

$$ 2^h\geq n! \implies h\geq \log_{2}(n!) \implies h= \Omega(n\log n) $$

得证

(4)

可能会更快，在数据特殊，比如均为整数且极差较小时。但是排序的稳定性可能被打破。

Exercise 6

Counting sort for integer arrays
$min \gets x[1]$, $max \gets x[1]$
for $i \gets 2$ to $n$ do
if $x[i] < min$ then
$min \gets x[i]$ \ENDIF
if $x[i] > max$ then
$max \gets x[i]$ \ENDIF
end for
$M \gets max - min$
Let $count[0 \dots M]$ be a new array, initialized to $0$
for $i \gets 1$ to $n$ do
$count[x[i] - min] \gets count[x[i] - min] + 1$
end for
$pos \gets 1$
for $j \gets 0$ to $M$ do
for $k \gets 1$ to $count[j]$ do
$x[pos] \gets min + j$
$pos \gets pos + 1$
end for
end for
return $x$

$Ω(nlog n)$ 的下界是针对以比较确定大小关系的排序算法而言的，而计数排序运用的是整数的性质，没有涉及大小比较，故能打破这个下界。