Summary of Lecture 5

L05 – Modulo Arithmetic and Square-and-Multiply Algorithm

2026年3月18日

493.9K

Complexity of arithmetic operations:

• $a = (a_{k-1} \cdots a_0)_2, b = (b_{k-1} \cdots b_0)_2$
  • $a + b, a – b$: $O(k)$ bit operations
  • $ab$: $O(k^2)$ bit operations
• $a = (a_{k-1} \cdots a_0)_2, b = (b_{l-1} \cdots b_0)_2, a \ge b, a_{k-1} = b_{l-1} = 1$
  • $a = bq + r$: $O((k – l + 1) \cdot l)$ bit operations

Complexity of arithmetic operations modulo $N$

• $a, b \in \{0, 1, \dots, N – 1\}$
  • $(a \pm b) \bmod N$: $O(\ell(N))$ bit operations
  • $(ab) \bmod N$: $O(\ell(N)^2)$ bit operations

Modular exponentiation: $a \in \{0, 1, \dots, N – 1\}; e = (e_{k-1} \cdots e_0)_2$

• Square: $x_0 = a; x_i = x_{i-1}^2 \bmod N, i = 1, \dots, k – 1$
• Multiply: $(a^e \bmod N) = (x_0^{e_0} \cdot x_1^{e_1} \cdots x_{k-1}^{e_{k-1}} \bmod N)$
• $a^e \bmod N$: $O(k \cdot \ell(N)^2)$ bit operations

Time-lock puzzle: intrinsically sequential computations

• The puzzle: $(n, t)$
  // $n = pq$ is the product of two unequal primes $p, q$
• The solution: $$a_t = 2^{2^t} \bmod n$$
• The computing process: $a_0 = 2 \bmod n; a_i = a_{i-1}^2 \bmod n, i = 1, 2, \dots, t$
  • Solved in << 35 years
  • There have been hardware and software advances beyond what I predicted in 1999
  • The resources required to do a single squaring have been reduced by much more
    • underestimated how fast computing technology would become

Encrypting to the future:

• $a_t = 2^{2^t} \bmod n, c = m \oplus a_t$
• Given $(n, t)$ and $c$, find $m$

Euclidean Algorithm (EA)

Extended Euclidean Algorithm (EEA)

ALGORITHM:$\mathbf{EEA}(a,b)$

• Input:$a, b$ ($a \ge b > 0$)
• Output:$d = \gcd(a, b)$, integers $s, t$ such that $d = as + bt$
  • $r_0 = a; r_1 = b; \binom{s_0}{t_0} = \binom{1}{0}; \binom{s_1}{t_1} = \binom{0}{1};$
  • $r_0 = r_1 q_1 + r_2 \ (0 < r_2 < r_1); \binom{s_2}{t_2} = \binom{s_0}{t_0} – q_1 \binom{s_1}{t_1}$
  • $\dots$
  • $r_{i-1} = r_i q_i + r_{i+1} \ (0 < r_{i+1} < r_i); \binom{s_{i+1}}{t_{i+1}} = \binom{s_{i-1}}{t_{i-1}} – q_i \binom{s_i}{t_i}$
  • $\dots$
  • $r_{k-2} = r_{k-1} q_{k-1} + r_k \ (0 < r_k < r_{k-1}); \binom{s_k}{t_k} = \binom{s_{k-2}}{t_{k-2}} – q_{k-1} \binom{s_{k-1}}{t_{k-1}}$
  • $r_{k-1} = r_k q_k$
  • output $r_k, s_k, t_k$

EXAMPLE: Execution of the EEA on input $a = 12345, b = 123$

Correctness: We have that $r_i = as_i + bt_i$ for $i = 0, 1, 2, …, k$

• $r_0 = a = (a, b) \binom{s_0}{t_0}; \ r_1 = b = (a, b) \binom{s_1}{t_1};$
• $r_2 = r_0 – q_1 r_1 = (a, b) \binom{s_0}{t_0} – q_1 \cdot (a, b) \binom{s_1}{t_1} = (a, b) \binom{s_2}{t_2};$
• $\dots$
• $r_k = r_{k-2} – q_{k-1} r_{k-1} = (a, b) \binom{s_{k-2}}{t_{k-2}} – q_{k-1} \cdot (a, b) \binom{s_{k-1}}{t_{k-1}} = (a, b) \binom{s_k}{t_k}$

Complexity

THEOREM: Let $\alpha = \frac{1}{2}(1 + \sqrt{5})$. Then $k \le \frac{\ln b}{\ln \alpha} + 1$ in EA and EEA.

• We show that $r_{k-i} \ge \alpha^i$ for $i = 0, 1, …, k-1$
• $k = 1: r_1 \ge \alpha^0$
• $k > 1$:
  • $i = 0: r_k \ge 1 = \alpha^0$
  • $i = 1: r_{k-1} > r_k \Rightarrow r_{k-1} \ge r_k + 1 \ge 2 \ge \alpha^1$
  • Suppose that $r_{k-i} \ge \alpha^i$ for $i \le j$
    • $r_{k-(j+1)} = r_{k-j}q_{k-j} + r_{k-(j-1)}$
      $\ge \alpha^j + \alpha^{j-1}$
      $= \alpha^{j-1}(\alpha + 1)$
      $= \alpha^{j+1}$
• $b = r_1 \ge \alpha^{k-1}$
• $k \le \ln b / \ln \alpha + 1$

Complexity of EA and EEA:$O(\ell(a)\ell(b))$ bit operations // $k$ divisions

RSA Implementation

Randomly choose an integer from the interval $[2^{n-1}, 2^n – 1)$ and test if this integer is a prime.

How many primes in $[2^{n-1}, 2^n – 1)$?

Chebyshev’s Theorem

DEFINITION: For $x \in \mathbb{R}^+$, $\pi(x) = \sum_{p \le x} 1$: the number of primes $\le x$
// $\sum_{p \le x}$ sum over primes

• $\pi(1) = 0, \pi(2) = 1, \pi(3) = 2, \dots$

Notations: Big O, Big Omega, and Big Theta. For a positive function $g(n)$, define

• $O(g(n)) = \{f(n): \exists c, n_0 > 0 \text{ such that } 0 \le f(n) \le cg(n) \text{ for all } n \ge n_0\}$
• $\Omega(g(n)) = \{f(n): \exists c, n_0 > 0 \text{ such that } f(n) \ge cg(n) \text{ for all } n \ge n_0\}$
• $\Theta(g(n)) = \{f(n): \exists c, d, n_0 > 0 \text{ such that } cg(n) \le f(n) \le dg(n) \text{ for all } n \ge n_0\}$

THEOREM (Chebyshev, 1850)$\pi(x) = \Theta\left(\frac{x}{\ln x}\right)$.

LEMMA: Suppose that $m \in \mathbb{Z}^+$. Then $\binom{2m}{m} \ge \frac{2^{2m}}{2m}$ and $\binom{2m+1}{m} \le 2^{2m}$.

• $2^{2m} = (1+1)^m = 1 + \binom{2m}{1} + \dots + \binom{2m}{m} + \dots + \binom{2m}{2m-1} + 1$
  $\le 2 + (2m-1)\binom{2m}{m}$
  $\le 2m\binom{2m}{m}$
• $\binom{2m+1}{m} = \binom{2m+1}{m+1}$
• $\binom{2m+1}{m} + \binom{2m+1}{m+1} \le (1+1)^{2m+1}$
  $\le 2^{2m+1}$

$v_p(n)$: the exponent of $p$ in the prime factorization of $n$
// $p^{v_p(n)} | n, p^{v_p(n)+1} \nmid n$, e.g., $v_2(12) = 2$

LEMMA: Suppose that $p$ is a prime and $n \in \mathbb{Z}^+$. Then $v_p(n!) = \sum_{k \ge 1} \lfloor n/p^k \rfloor$

• proof: see hw1, question 3 (2)
• Example: $v_2(5!) = \lfloor \frac{5}{2} \rfloor + \lfloor \frac{5}{2^2} \rfloor + \lfloor \frac{5}{2^3} \rfloor + \dots = 3$
  // $5! = 120 = 2^3 \times 3 \times 5$

THEOREM: Let $n \in \mathbb{Z}^+$ and $n \ge 2$. Then $$\pi(n) \ge \frac{\ln 2}{2} \cdot \frac{n}{\ln n}$$.

• $n = 2m$: consider the number $t = \binom{2m}{m} = \frac{(2m)!}{m! \cdot m!}$
  • $v_p(t) = \sum_{k \ge 1} \lfloor \frac{2m}{p^k} \rfloor – \sum_{k \ge 1} 2 \lfloor \frac{m}{p^k} \rfloor$
    $= \sum_{k \ge 1} \left( \lfloor \frac{2m}{p^k} \rfloor – 2 \lfloor \frac{m}{p^k} \rfloor \right)$// 0,1
    $\le \log_p 2m$// there are $k$ terms: $p^k \le 2m$
    $= \frac{\ln 2m}{\ln p}$
• $\pi(n) \ln n = \sum_{p \le 2m} \ln 2m$
  $= \sum_{p \le 2m} \frac{\ln 2m}{\ln p} \cdot \ln p$
  $\ge \sum_{p \le 2m} v_p(t) \cdot \ln p$
  $= \ln t$
  $\ge 2m \ln 2 – \ln 2m$
  $\ge m \ln 2 = \frac{\ln 2}{2} n$

• $n = 2m – 1 \ge 3$:
  • $\pi(n) = \pi(2m)$
    $\ge \frac{\ln 2}{2} \cdot \frac{2m}{\ln 2m}$
    $\ge \frac{\ln 2}{2} \cdot \frac{2m-1}{\ln(2m-1)}$
    $= \frac{\ln 2}{2} \cdot \frac{n}{\ln n}$

$\frac{x}{\ln x}$ is increasing when $x \ge 3$