Proofs: Summation polynomial index calculus

Correctness of summation polynomial index calculus full

This proof shows: correctness, termination.

Let $E$ be the curve over $\mathbb{F}_{p^2}$, $G = E(\mathbb{F}_{p^2})$ of order $N$, $P, Q \in G$ and $n = \operatorname{ord}(P)$. For termination we treat the draws of line L10 as independent: $a_j$ and $b_j$ uniform in $[0, r)$, and $U_j$ a random affine point in which every affine point of $G$ has positive probability, which holds for the sampling described on the page. DECOMPOSE is a function of $R$: its internal random choices in the root finding change only the time, because the roots are returned in increasing order.

Lemma 1 (the frame). For each prime power $r^e \,\|\, n$ put $u_r = n / r^e$, $P_r = u_r P$ and $Q_r = u_r Q$. If $nQ = O$, then $Q \in \langle P \rangle$ if and only if $Q_r \in \langle P_r \rangle$ for every $r$. In that case, if $x_r P_r = Q_r$ for every $r$, the $x$ of line L7 satisfies $xP = Q$, and it is the only such $x$ in $[0, n)$.

Proof. The $u_r$ have greatest common divisor $1$, so there are integers $w_r$ with $\sum_r w_r u_r = 1$. If $Q = yP$, then $Q_r = y P_r$. Conversely, if $Q_r = x_r P_r$ for every $r$, then $Q = \sum_r w_r u_r Q = \sum_r w_r Q_r$. For $x$ with $x \equiv x_r \pmod{r^e}$, $x P_r = x_r P_r$ because $P_r$ has order $r^e$, so $xP = \sum_r w_r u_r x P = \sum_r w_r x P_r = \sum_r w_r Q_r = Q$. Uniqueness in $[0, n)$ holds since $P$ has order $n$. $\square$

Lemma 2 (the Sylow subgroup). If $r$ is a prime with $r \mid n$ and $r^2 \nmid N$, then $e = 1$, $P_r$ has order $r$, $\langle P_r \rangle = \{T \in G : rT = O\}$, and $G = \langle P_r \rangle \oplus rG$ with $rG$ of order $N / r$. If moreover $nQ = O$, then $Q_r \in \langle P_r \rangle$.

Proof. $r^e$ divides $n$, which divides $N$, so $e = 1$, and $P_r = (n/r)P$ has order $r$. The kernel of $T \mapsto rT$ is a subgroup whose order is a power of $r$ dividing $N$. It contains $P_r$, so it has order exactly $r$ and equals $\langle P_r \rangle$. Hence $rG$ has order $N / r$, which is prime to $r$. So $rG \cap \langle P_r \rangle = \{O\}$, and the orders multiply to $N$, which gives the direct sum. Finally $r Q_r = nQ = O$, so $Q_r$ lies in the kernel. $\square$

Lemma 3 (rows are true). If DECOMPOSE$(R)$ returns $e$, then $R = \sum_{x \in \mathcal{B}} e_x P_x$.

Proof. At line L16, $R = (x_R, y)$ with $x_R \in \mathcal{B}$, and $y^2 = x_R^3 + a x_R + b = y_{x_R}^2$, so $y = \pm y_{x_R}$ and $R = \pm P_{x_R}$ with the sign returned. At line L20 the equality $\varepsilon_1 P_{x_1} + \varepsilon_2 P_{x_2} = R$ is checked before the row is returned, and the row adds $\varepsilon_1$ at $x_1$ and $\varepsilon_2$ at $x_2$, also when $x_1 = x_2$. $\square$

Lemma 4 (elimination). After $k$ relations have been processed in lines L12 to L15, every stored row $v$ of $K$ and every dependency $c$ found so far satisfy $v \equiv \sum_i c^{(v)}_i e_i$ and $\sum_i c_i e_i \equiv 0 \pmod r$, where $c^{(v)}$ is the combination kept with $v$. The dependencies found so far form a basis of the left kernel $\{c \in (\mathbb{Z}/r)^k : \sum_i c_i e_i \equiv 0\}$.

Proof. A new row $e_k$ starts with combination $c = $ the unit vector at $k$. Each step of line L12 subtracts a multiple of a stored row together with its combination, and line L15 scales both by the same unit, so the relation $v \equiv \sum_i c_i e_i$ is kept. A row that reduces to $0$ gives a dependency. The stored rows have distinct leading columns, and a stored row with leading column $\ell$ has zeros before $\ell$; reducing the new row column by column in increasing order makes it zero at every stored leading column, so a nonzero result has a new leading column. Hence the stored rows stay in echelon form and are linearly independent, and they span the same space as $e_1, \dots, e_k$ modulo $r$, because each operation is invertible. So $|K|$ is the rank $\rho_k$ of $e_1, \dots, e_k$. Each relation adds either a row to $K$ or a dependency, so $k - \rho_k$ dependencies have been found. The dependency found at relation $j$ has coefficient $1$ at $j$ and $0$ after $j$, so these vectors are linearly independent. The left kernel has dimension $k - \rho_k$, so they form a basis. $\square$

Lemma 5 (a dependency gives the logarithm). In RELATIONS$(P, Q, r)$ with $r \,\|\, N$, $\operatorname{ord}(P) = r$ and $Q = x^* P$, let $c$ be a dependency with $A = \sum_i c_i a_i$ and $C = \sum_i c_i b_i$. Then $A + x^* C \equiv 0 \pmod r$. So if $C \not\equiv 0$, line L14 returns $x^* \bmod r$.

Proof. Take the $c_i$ as integers in $[0, r)$. By Lemma 3, $\sum_i c_i e_i = r w$ for an integer vector $w$, so $\sum_i c_i R_i = r \sum_x w_x P_x$. Let $h = N / r$. Then $h \sum_i c_i R_i = \sum_x w_x (N P_x) = O$. On the other side, $R_i = (a_i + x^* b_i) P + r U_i$, so $h \sum_i c_i R_i = h (A + x^* C) P + \sum_i c_i (N U_i) = h (A + x^* C) P$. Hence $h (A + x^* C) \equiv 0 \pmod r$, and $r \nmid h$ because $r^2 \nmid N$. $\square$

Correctness. If $nQ \ne O$, then $Q \notin \langle P \rangle$ and line L2 returns NONE correctly. Otherwise, for each $r$: if $r^2 \mid N$, baby-step giant-step on $\langle P_r \rangle$ of order $r^e$ returns $x_r$ with $x_r P_r = Q_r$ or reports that none exists. If $r^2 \nmid N$, Lemma 2 gives $Q_r \in \langle P_r \rangle$ and Lemma 5 shows that RELATIONS returns $x_r$ with $x_r P_r = Q_r$. By Lemma 1, line L5 returns NONE exactly when $Q \notin \langle P \rangle$, and otherwise line L7 returns the unique $x \in [0, n)$ with $xP = Q$.

Termination. Lines L1 to L7 run over finitely many primes, and baby-step giant-step stops. Drawing $U$ stops with probability $1$, because the right side of the curve equation is a square for some $x$; for example $\mathcal{B} \ne \emptyset$, which the implementation checks. Root finding in DECOMPOSE stops with probability $1$ (see the Cantor-Zassenhaus algorithm), and its loops are finite. It remains to show that the loop of lines L9 to L15 stops with probability $1$.

Fix $x_0 \in \mathcal{B}$ and $S = P_{x_0}$. By Lemma 2 write $S = \sigma P + S'$ with $S' \in rG$, and pick an affine $U'$ with $rU' = S'$: if $S' = O$, take $U' = P$, which is affine since $P \ne O$; otherwise any preimage is affine. Let $\pi > 0$ be the probability that $rU_j = S'$. For every $\beta \in [0, r)$, $R_j = S$ and $b_j = \beta$ hold exactly when $rU_j = S'$ and $a_j \equiv \sigma - x^* \beta \pmod r$, which has probability $\pi / r^2$. So each draw gives $R_j = S$ with probability $\pi / r > 0$, and given that, $b_j$ is uniform in $[0, r)$, independently of the other draws. DECOMPOSE$(S)$ returns a row at line L16. Hence, with probability $1$, there are two relations $j < k$ with $R_j = R_k = S$ and $b_j \ne b_k$, because $r \ge 2$. Their rows are equal, since DECOMPOSE is a function of $R$, so the vector with $1$ at $j$ and $-1$ at $k$ is in the left kernel after relation $k$, with $C = b_j - b_k \not\equiv 0$. Suppose the loop has not stopped when relation $k$ has been processed. Then every dependency found so far had $C \equiv 0$. By Lemma 4 they span the left kernel, and $C$ is linear in $c$, so $C \equiv 0$ on the whole kernel, a contradiction. So the loop stops by relation $k$, and the algorithm stops with probability $1$. $\blacksquare$