Proofs: Number field sieve for discrete logarithms

Correctness of the quadratic number field sieve for discrete logarithms full

This proof shows: correctness, termination.

We prove the version of the main pseudocode, with $f_1 = x^2 + a_1 x + a_0$ such that $\mathcal{O} = \mathbb{Z}[\omega] = \mathbb{Z}[x]/(f_1)$ is the ring of integers of an imaginary quadratic field of class number $1$, and $f_2 = d x - c$ with $d \ge 1$ and $c^2 + a_1 c d + a_0 d^2 = p$. Let $p \ge 3$ be prime, $G = (\mathbb{Z}/p\mathbb{Z})^*$, cyclic of order $N = p - 1$, let $g \in G$ have order $r$ and let $h \in G$. Let $\gamma$ be the generator of line L3 and $L(z) \in \mathbb{Z}/N\mathbb{Z}$ the logarithm of $z \in G$ to base $\gamma$. Let $\ell = \prod q^e$ over the prime powers $q^e \parallel N$ with $q \mid r$; then $r \mid \ell \mid N$. The bound $B$ satisfies $1 \le B \le (p - 1)/2$. For $n \in \mathbb{Z}$ with $p \nmid n$ we write $L(n)$ for the logarithm of $n \bmod p$. For termination we treat the exponents $m$ of lines L9 and L13 and the column $j$ of line L9 as independent and uniform.

Lemma 1 (membership and the trivial target). Line L1 returns NONE exactly when $h \notin \langle g \rangle$, and line L2 is correct.

Proof. $G$ is cyclic, so its only subgroup of order $r$ is $\{z : z^r = 1\}$, which is $\langle g \rangle$. If $h = 1$, then $x = 0$. $\square$

From now on $h = g^{x^*}$ with $0 \le x^* < r$, unique because $g$ has order $r$, and $h \ne 1$, so $r \ge 2$ and $p \ge 3$.

Lemma 2 (the two maps). Let $s = c d^{-1} \bmod p$. Then $f_1(s) \equiv 0 \pmod p$, the map $\rho : \mathcal{O} \to \mathbb{F}_p$, $a + b\omega \mapsto a + b s$, is a ring map, and $d \, \rho(a + b\omega) \equiv a d + b c \pmod p$ for all integers $a, b$.

Proof. $d^2 f_1(c/d) = c^2 + a_1 c d + a_0 d^2 = p$, and $0 < d < p$, so $d$ is a unit modulo $p$ and $f_1(s) \equiv 0$. Since $\mathcal{O} = \mathbb{Z}[x]/(f_1)$ and $s$ is a root of $f_1$ in $\mathbb{F}_p$, the evaluation $x \mapsto s$ defines a ring map. Finally $d (a + b s) \equiv a d + b \, d s \equiv a d + b c$. $\square$

Lemma 3 (the factor bases). Every column has a nonzero image in $\mathbb{F}_p$, so its logarithm is defined: $-1$, the primes $q \le B$, the unit generator $\varepsilon$, every listed generator $\pi$, and $d$. Every nonzero $z \in \mathcal{O}$ that is a product of prime ideals of norm at most $B$ is $\varepsilon^k \prod \pi^{e_\pi}$ for unique $k \bmod |\mathcal{O}^*|$ and exponents $e_\pi \ge 0$.

Proof. A prime $q \le B < p$ and $-1$ are not divisible by $p$, and $0 < d < p$. Units map to units. For a generator $\pi$ with norm $\pi \bar\pi = n(\pi) \le B < p$, we have $\rho(\pi) \rho(\bar\pi) = \rho(n(\pi)) \ne 0$, so $\rho(\pi) \ne 0$. The ring $\mathcal{O}$ is a principal ideal domain, hence has unique factorization into primes up to units. The list holds exactly one generator for each prime ideal of norm at most $B$: the implementation enumerates all elements of norm at most $B$, keeps those of prime norm and the inert rational primes $q$ with $q^2 \le B$, which are all the prime elements of norm at most $B$, and keeps one canonical associate of each. The unit group is finite and cyclic, generated by $\varepsilon$, so the unit factor is $\varepsilon^k$. $\square$

Lemma 4 (relations). Every row $(\sigma, e_q ; \kappa, e_\pi, \delta ; k')$ of $R$ satisfies $\sigma L(-1) + \sum_q e_q L(q) + \kappa L(\varepsilon) + \sum_\pi e_\pi L(\pi) + \delta L(d) \equiv k' \pmod N$, where $L(\pi)$ and $L(\varepsilon)$ are the logarithms of the images under $\rho$.

Proof. A row from line L7 has $p \nmid N_{ab} = a d + b c$, $N_{ab} = (-1)^\sigma \prod q^{e_q}$, and $a + b\omega = \varepsilon^k \prod \pi^{e_\pi}$. By Lemma 2, $N_{ab} \equiv d \, \rho(a + b\omega)$, which is nonzero modulo $p$. Applying $\rho$ and $L$ to both factorizations gives $\sigma L(-1) + \sum e_q L(q) = L(d) + k L(\varepsilon) + \sum e_\pi L(\pi)$, which is the row with $\kappa = -k$, the negated $e_\pi$, $\delta = -1$ and right side $0$. A row from line L10 has $\gamma^m w_j \equiv (-1)^\sigma \prod q^{e_q}$, where $w_j$ is the image of column $j$ and is absent if $j$ is none; the balanced residue is congruent to $\gamma^m w_j$. Applying $L$ gives $m + L(w_j) = \sigma L(-1) + \sum e_q L(q)$, which is the row with $-1$ in column $j$ and right side $m$. $\square$

Lemma 5 (SOLVE). Let $M = q^e$ with $q$ prime and $M \mid N$. If SOLVE$(R, q, M)$ returns a vector $\lambda$, then $\lambda$ equals the vector of true logarithms of the columns modulo $M$.

Proof. By Lemma 4, the true vector $X$ modulo $M$ satisfies every row modulo $M$, because $M \mid N$. Lines L19 and L20 swap two rows, multiply a row by a unit modulo $M$ (an entry not divisible by $q$ is coprime to $M$), or subtract a multiple of one row from another. Each operation is invertible, so the set of solutions modulo $M$ is unchanged, and $X$ is still a solution afterwards. After column $j$ has been processed, row $j$ has a $1$ in column $j$ and every other row has $0$ there, and later steps keep this. When all columns are processed, row $j$ reads $X_j \equiv$ (right side of row $j$), so the returned $\lambda_j$ equals $X_j$. $\square$

Lemma 6 (scale). After line L11, $\lambda$ is the vector of true logarithms of the columns modulo $\ell$.

Proof. Line L11 is passed only when every SOLVE succeeded, so Lemma 5 applies to each $q^e \parallel \ell$. The moduli are pairwise coprime, and the Chinese remainder theorem gives a unique residue modulo $\ell$ with these reductions. $\square$

Lemma 7 (medium primes). If line L14 assigns a value to $L(Q_i)$, the value is the true $L(Q_i) \bmod \ell$.

Proof. $Q_i \le B^2$ is a prime factor of a nonzero residue $z$ with $|z| < p/2$, so $Q_i < p$ and $L(Q_i)$ is defined. Line L14 accepts $(a, b)$ only if $p \nmid N_{ab}$, $N_{ab} = Q_i^k \cdot (-1)^\sigma \prod q^{e_q}$ with $\gcd(k, \ell) = 1$, and $a + b\omega = \varepsilon^{k'} \prod \pi^{e_\pi}$. As in Lemma 4, $k L(Q_i) + \sigma L(-1) + \sum e_q L(q) \equiv L(d) + k' L(\varepsilon) + \sum e_\pi L(\pi) \pmod N$, and so modulo $\ell$. Since $k$ is a unit modulo $\ell$, solving for $L(Q_i)$ and replacing the column logarithms by $\lambda$, by Lemma 6, gives the value of line L14. $\square$

Lemma 8 (individual logarithms). For $y \in \{g, h\}$, the value of line L16 is the true $L(y) \bmod \ell$.

Proof. Line L15 is passed only when the balanced residue of $y \gamma^m$ equals $(-1)^\sigma \prod q^{d_q} \prod Q_i^{u_i}$ and every $Q_i$ got a value. Then $L(y) + m \equiv \sigma L(-1) + \sum d_q L(q) + \sum u_i L(Q_i) \pmod N$, where the sign is the first entry of the rational exponent vector. Reducing modulo $\ell$ and using Lemmas 6 and 7 gives line L16. $\square$

Lemma 9 (conversion). With $c = \ell / r$, the residue $L(g) \bmod \ell$ is $c u$ for an integer $u$ coprime to $r$, the residue $L(h) \bmod \ell$ is divisible by $c$, and $(L(h)/c) \, u^{-1} \equiv x^* \pmod r$.

Proof. Since $g$ has order $r$ and $\gamma$ has order $N$, $\gcd(L(g), N) = N / r$. For each prime $q \mid r$ with $q^a \parallel r$ and $q^e \parallel N$, the $q$-adic valuation of $L(g)$, taken in $[0, N - 1]$, is exactly $e - a$, which is the valuation of $c$ at $q$, and $c$ has no other prime factors. Reducing modulo $\ell$ does not change a valuation below $e$, so $L(g) \bmod \ell = c u$ with $u$ coprime to $r$. Next, $h = g^{x^*}$ gives $L(h) \equiv x^* c u \pmod \ell$, so $L(h)/c \equiv x^* u \pmod r$, and multiplying by $u^{-1}$ gives $x^*$. $\square$

Correctness. By Lemmas 8 and 9, line L18 returns $x^*$. With Lemma 1, the algorithm returns $x^*$ if $h \in \langle g \rangle$ and NONE otherwise.

Termination. The loop of lines L5 to L7 runs over a finite set of pairs. For the loop of lines L8 to L11, we exhibit for each column a row whose only nonzero entry is $\pm 1$ in that column, and which line L10 appends with positive probability in each trial. For a prime $q \le B$, take $j$ = none and $\gamma^m = q$: since $q \le B < p/2$, the balanced residue is $q$ itself, and the row is $e_q = 1$. For $-1$, take $j$ = none and $\gamma^m = p - 1$: the balanced residue is $-1$, and the row has $\sigma = 1$ and nothing else. For an algebraic column $j$, take $\gamma^m = w_j^{-1}$: then $z = 1$, and the row has $-1$ in column $j$ only. With probability $1$, every column eventually gets such a row, and $R$ eventually has at least $t + 10$ rows. Once these rows are present, every SOLVE succeeds: the row with its only nonzero entry in column $j$ has entry $0$ in every earlier column, so it is never a pivot for an earlier column and is never changed by the clearing steps, which subtract multiples of a pivot row only from rows with a nonzero entry in the pivot column; swaps at a column $j' < j$ move it only among positions at least $j'$, so it is still available when column $j$ is processed, and its entry $\pm 1$ is a unit pivot. The implementation retries SOLVE after each new row of line L10. For the loop of lines L13 to L15, each trial has $y \gamma^m = 1$ with probability $1/N$; then there are no $Q_i$, and line L15 is passed. Each search of line L14 is over a finite set. Hence the algorithm stops with probability $1$. $\blacksquare$