I Math Guide: Mathematical foundations for Halo 2 and Zcash Orchard 9 Roots of unity and evaluation domains 11 Probability, asymptotics, and computation

10 Elliptic curves

The multiplicative groups of the preceding sections harbour a structural weakness. As 7.22 recorded, the discrete logarithm in $\mathbb{F}_{p}^{\times}$ does not resist attack at the generic square-root cost: the index-calculus family of algorithms exploits the fact that residues come from ordinary integers, and integers factor into primes, to solve the problem in subexponential time. The practical consequence is severe. To push the cheapest known attack on $\mathbb{F}_{p}^{\times}$ beyond $2^{128}$ operations, the prime $p$ must run to thousands of bits, and every exponentiation drags that bulk along. What cryptography wants instead is a group of roughly $2^{255}$ elements for which no attack faster than the square-root bound is known—a group without known exploitable arithmetic behind its elements, where the generic $O(\sqrt{N})$ attacks of 7.22 remain the best known. This section constructs the standard supplier of such groups.

An elliptic curve is, concretely, the solution set of a certain cubic equation in two variables, together with one extra “point at infinity”. Its notable feature is that this solution set carries the structure of an abelian group, defined by a strikingly geometric rule; and that inverting scalar multiplication in this group is hard—the discrete logarithm problem in a well-chosen elliptic-curve group appears to require exponential time. The combination of clean algebraic structure with a hard computational problem is exactly what cryptography requires.

Throughout the section we work over a field $K$ whose characteristic (4.30) is neither $2$ nor $3$ . In the applications $K$ is a finite prime field $\mathbb{F}_{p}$ with $p$ a large prime, but the basic theory is cleaner over a general field, and we specialise when needed. The reader should keep in mind the two Pasta curves

E_{p}:y^{2}=x^{3}+5\quad\text{over }\mathbb{F}_{p},\qquad E_{q}:y^{2}=x^{3}+5% \quad\text{over }\mathbb{F}_{q},

where $p$ and $q$ are the two $255$ -bit primes

	$\displaystyle p$	$\displaystyle=2^{254}+0x224698fc094cf91b992d30ed00000001,$
	$\displaystyle q$	$\displaystyle=2^{254}+0x224698fc0994a8dd8c46eb2100000001.$

These are the primes that 6.23 and 7.18 handled as black boxes; here they finally acquire their curves. The constants are the deployed ones: the primes and the curve equations $y^{2}=x^{3}+5$ are specified in §5.4.9.6 (“Pallas and Vesta”) of the Zcash protocol specification. The curve $E_{p}$ , defined over $\mathbb{F}_{p}$ , is called Pallas; the curve $E_{q}$ , defined over $\mathbb{F}_{q}$ , is called Vesta. Together they form a cycle: the number of $\mathbb{F}_{p}$ -points of Pallas equals $q$ , and the number of $\mathbb{F}_{q}$ -points of Vesta equals $p$ —a coincidence of design, not chance, whose meaning unfolds across the section. The equation $y^{2}=x^{3}+5$ serves as the running example throughout, with a toy curve over $\mathbb{F}_{11}$ developed in parallel for hand computation.

10.1 Weierstrass equations

Definition 10.1 (Short Weierstrass equation).

Let $K$ be a field of characteristic $\neq 2,3$ , and let $a,b\in K$ . The short Weierstrass equation with coefficients $a, b$ is the equation

y^{2}=x^{3}+ax+b.

(9)

The elements $a$ and $b$ are the Weierstrass coefficients.

Over a field of characteristic $\neq 2,3$ , an invertible affine change of variables always reduces the most general cubic of this shape, $y^{2}+a_{1}xy+a_{3}y=x^{3}+a_{2}x^{2}+a_{4}x+a_{6}$ , to the form (9): completing the square in $y$ (possible since $2\neq 0$ ) removes the $x y$ and $y$ terms but changes the quadratic coefficient to $a_{2}+a_{1}^{2}/4$ ; translating with the substitution $x=X-(a_{2}+a_{1}^{2}/4)/3$ (possible since $3\neq 0$ ) removes the $X^{2}$ term. This is precisely why characteristics $2$ and $3$ are excluded: those cases require the longer Weierstrass form, and they are not relevant to the Pasta curves, which live over large prime fields.

Not every choice of $a, b$ gives a usable curve. We must exclude the cubics whose graph has a self-intersection or a cusp, because the group law defined below breaks down at such a singular point.

Definition 10.2 (Discriminant and nonsingularity).

The discriminant of the short Weierstrass equation (9) is

\Delta=-16\,(4a^{3}+27b^{2})\in K.

(10)

The equation, and the cubic $f(x)=x^{3}+ax+b$ , is nonsingular (or smooth) if $\Delta\neq 0$ , equivalently $4a^{3}+27b^{2}\neq 0$ . (The factor $-16$ is a convention inherited from the general Weierstrass form; over our fields it is nonzero and affects nothing.)

The quantity $4a^{3}+27b^{2}$ is exactly the obstruction to $f$ having distinct roots. The following lemma makes this explicit by a computation reusable for any depressed cubic—a cubic with no square term—and is the engine of the smoothness criterion.

Lemma 10.3 (Discriminant of a depressed cubic).

Let $f(x)=x^{3}+ax+b=(x-r_{1})(x-r_{2})(x-r_{3})$ with $r_{1},r_{2},r_{3}$ in some field containing $K$ . Then

\prod_{i<j}(r_{i}-r_{j})^{2}=-(4a^{3}+27b^{2}).

Proof.

Expanding $(x-r_{1})(x-r_{2})(x-r_{3})$ and comparing coefficients with $x^{3}+ax+b$ gives Vieta’s relations for the depressed cubic:

r_{1}+r_{2}+r_{3}=0,\qquad r_{1}r_{2}+r_{1}r_{3}+r_{2}r_{3}=a,\qquad r_{1}r_{2% }r_{3}=-b.

Differentiating $f(x)=\prod_{i}(x-r_{i})$ by the product rule and evaluating at a root kills every term but one: $f^{\prime}(r_{i})=\prod_{j\neq i}(r_{i}-r_{j})$ . Multiplying the three evaluations pairs each factor $(r_{i}-r_{j})$ with $(r_{j}-r_{i})$ :

\prod_{i}f^{\prime}(r_{i})=\prod_{i<j}(r_{i}-r_{j})(r_{j}-r_{i})=(-1)^{3}\prod% _{i<j}(r_{i}-r_{j})^{2}.

It remains to compute $\prod_{i}f^{\prime}(r_{i})=\prod_{i}(3r_{i}^{2}+a)$ . Expanding the product and collecting the elementary symmetric functions of the squares $r_{i}^{2}$ ,

\prod_{i}(3r_{i}^{2}+a)=27\prod_{i}r_{i}^{2}+9a\sum_{i<j}r_{i}^{2}r_{j}^{2}+3a% ^{2}\sum_{i}r_{i}^{2}+a^{3}.

Vieta’s relations evaluate each symmetric function: with $e_{1}=0$ , $e_{2}=a$ , $e_{3}=-b$ ,

\sum_{i}r_{i}^{2}=e_{1}^{2}-2e_{2}=-2a,\qquad\sum_{i<j}r_{i}^{2}r_{j}^{2}=e_{2% }^{2}-2e_{1}e_{3}=a^{2},\qquad\prod_{i}r_{i}^{2}=e_{3}^{2}=b^{2}.

Substituting, $\prod_{i}f^{\prime}(r_{i})=27b^{2}+9a^{3}-6a^{3}+a^{3}=4a^{3}+27b^{2}$ , and the two displays together give $\prod_{i<j}(r_{i}-r_{j})^{2}=-(4a^{3}+27b^{2})$ . □

Proposition 10.4 (Smoothness, four ways).

Let $f(x)=x^{3}+ax+b\in K[x]$ . The following are equivalent.

1.

The quantity $4a^{3}+27b^{2}$ of 10.2 is nonzero.
2.

The cubic $f$ has no repeated root in the algebraic closure $\overline{K}$ —the smallest extension field of $K$ in which every nonconstant polynomial over $K$ factors into linear factors.
3.

The polynomials $f$ and $f^{\prime}$ are coprime in $\overline{K}[x]$ .
4.

There is no point $(x_{0},y_{0})\in\overline{K}^{2}$ satisfying the curve equation $y^{2}=f(x)$ together with the two partial-derivative equations $2y=0$ and $f^{\prime}(x)=0$ .

Proof.

Equivalence $(1)\Leftrightarrow(2)$ : over $\overline{K}$ the monic cubic factors as $f=(x-r_{1})(x-r_{2})(x-r_{3})$ , and 10.3 gives $\prod_{i<j}(r_{i}-r_{j})^{2}=-(4a^{3}+27b^{2})$ . The left side vanishes exactly when two roots coincide, so $f$ has a repeated root if and only if $4a^{3}+27b^{2}=0$ .

Equivalence $(2)\Leftrightarrow(3)$ : this is the derivative test of 5.40, applied over $\overline{K}$ where $f$ splits: a repeated root of $f$ is a common root of $f$ and $f^{\prime}$ , hence a common factor $(x-\alpha)$ , and conversely a nontrivial $\gcd(f,f^{\prime})$ has a root in $\overline{K}$ which is then a repeated root of $f$ .

Equivalence $(4)\Leftrightarrow(2)$ : a singular point of the affine curve $y^{2}=f(x)$ is a point where both partial derivatives of $g(x,y)=y^{2}-f(x)$ vanish, namely $\partial g/\partial y=2y=0$ and $\partial g/\partial x=-f^{\prime}(x)=0$ . Since $\operatorname{char}(K)\neq 2$ , the first equation forces $y_{0}=0$ ; the curve equation then gives $f(x_{0})=0$ , which combined with $f^{\prime}(x_{0})=0$ says $x_{0}$ is a repeated root of $f$ (5.40(1)). Conversely a repeated root $x_{0}$ of $f$ yields the singular point $(x_{0},0)$ . □

Definition 10.5 (Elliptic curve and rational points).

An elliptic curve over $K$ is a short Weierstrass equation (9) with nonzero discriminant, $4a^{3}+27b^{2}\neq 0$ . For any field extension $L\supseteq K$ , the set of $L$ -rational affine points is

E^{\mathrm{aff}}(L)=\{\,(x,y)\in L\times L:y^{2}=x^{3}+ax+b\,\},

and the set of $L$ -rational points is

E(L)=E^{\mathrm{aff}}(L)\cup\{\mathcal{O}\},

where $\mathcal{O}$ is a single formal symbol called the point at infinity. When $L=K$ one writes simply $E$ for the curve and $E(K)$ for its rational points.

Remark 10.6 (The Pasta curves are smooth).

For the Pasta curves $a=0$ and $b=5$ , so $4a^{3}+27b^{2}=27\cdot 25=675=3^{3}\cdot 5^{2}$ . The curve is therefore nonsingular whenever the characteristic does not divide $675$ , i.e. whenever the prime is neither $3$ nor $5$ ; the Pasta primes are enormous, so this is automatic. More generally, any curve $y^{2}=x^{3}+b$ with $b\neq 0$ is nonsingular away from characteristics $2$ and $3$ .

10.2 The point at infinity, geometrically

The extra point $\mathcal{O}$ is not decoration; it is the identity element of the group to come, and it has an honest geometric home. To see it, view the affine plane as sitting inside the projective plane. A point of the projective plane $\mathbb{P}^{2}(K)$ is an equivalence class $[X:Y:Z]$ of nonzero triples $(X,Y,Z)\in K^{3}\setminus\{0\}$ , where $(X,Y,Z)\sim(\lambda X,\lambda Y,\lambda Z)$ for every $\lambda\in K^{\times}$ . The affine points $(x,y)$ embed as $[x:y:1]$ ; the points with $Z=0$ form the line at infinity, the extra “directions”. Homogenising the Weierstrass equation (9) by setting $x=X/Z$ , $y=Y/Z$ and clearing denominators gives the projective Weierstrass equation

Y^{2}Z=X^{3}+aXZ^{2}+bZ^{3}.

(11)

Setting $Z=0$ in (11) forces $X^{3}=0$ , hence $X=0$ , leaving the single projective point $[0:1:0]$ . This is the point at infinity $\mathcal{O}$ . It lies infinitely far up in the vertical direction, and every vertical line $x=\text{const}$ passes through it. The reader may safely picture $\mathcal{O}$ as one point pinned at the top (and bottom) of the $y$ -axis, where all vertical lines meet; the projective equation above is the licence for that picture.

10.3 The chord-and-tangent group law: geometry

We now describe the procedure for “adding” two points of $E(K)$ . The construction is purely geometric, and it rests on a single fact: a line meets a cubic curve in exactly three points, counted with multiplicity. The point at infinity is engineered precisely so that the counting is always exact.

Definition 10.7 (The group law, geometric form).

Let $P,Q\in E(K)$ . Define $P+Q$ as follows.

•

If $P=\mathcal{O}$ , set $P+Q=Q$ ; if $Q=\mathcal{O}$ , set $P+Q=P$ .
•

Otherwise $P=(x_{1},y_{1})$ and $Q=(x_{2},y_{2})$ are affine. Draw the line $\ell$ through $P$ and $Q$ ; if $P=Q$ , let $\ell$ be the tangent line to the curve at $P$ . The line $\ell$ meets the curve in a third point $R^{\prime}$ , counted with multiplicity, where a vertical $\ell$ has third point $\mathcal{O}$ . Define $P+Q$ to be the reflection of $R^{\prime}$ across the $x$ -axis: if $R^{\prime}=(x_{3},-y_{3})$ then $P+Q=(x_{3},y_{3})$ , and if $R^{\prime}=\mathcal{O}$ then $P+Q=\mathcal{O}$ .

The reflection step deserves a comment, because it is what converts “the three intersection points of a line sum to a fixed thing” into a genuine group law with $\mathcal{O}$ as identity. The underlying rule is this: the three intersection points of any line with the curve add up to $\mathcal{O}$ . (Stated here as a guiding picture; every use of it below is discharged by an explicit computation with the formulas of §10.4.) Reflection across the $x$ -axis sends an affine point $(x,y)$ to $(x,-y)$ , which—as the next subsection confirms—is its additive inverse; and it sends $\mathcal{O}$ to $\mathcal{O}$ . To convert the geometry into formulas one must (i) find the third intersection point of a line with the cubic and (ii) handle the degenerate cases. The key algebraic device for (i) is Vieta’s relation between the roots of a cubic and its coefficients, already deployed in 10.3.

10.4 Explicit affine formulas

Fix an elliptic curve $E:y^{2}=x^{3}+ax+b$ over $K$ , and let $P=(x_{1},y_{1})$ and $Q=(x_{2},y_{2})$ denote affine points.

Definition 10.8 (Negation).

Define

-\mathcal{O}=\mathcal{O},\qquad-(x_{1},y_{1})=(x_{1},-y_{1}).

The reflected point $(x_{1},-y_{1})$ is again on the curve, since the curve equation depends on $y$ only through $y^{2}$ . Geometrically, the line through $P$ and $-P$ is the vertical line $x=x_{1}$ , which meets the curve at $P$ , $-P$ , and $\mathcal{O}$ .

Construction 10.9 (Chord addition).

Suppose $P,Q\neq\mathcal{O}$ and $x_{1}\neq x_{2}$ . The line through $P$ and $Q$ is $y=\lambda x+\mu$ with

\lambda=\frac{y_{2}-y_{1}}{x_{2}-x_{1}},\qquad\mu=y_{1}-\lambda x_{1}.

Substituting the line into the curve equation, $(\lambda x+\mu)^{2}=x^{3}+ax+b$ , and collecting terms gives

g(x):=x^{3}-\lambda^{2}x^{2}+(a-2\lambda\mu)\,x+(b-\mu^{2})=0.

Both $x_{1}$ and $x_{2}$ are roots of the monic cubic $g$ : each point lies on the line and on the curve, so $g(x_{i})=f(x_{i})-(\lambda x_{i}+\mu)^{2}=f(x_{i})-y_{i}^{2}=0$ . Since $x_{1}\neq x_{2}$ , factoring out $(x-x_{1})(x-x_{2})$ (5.17, applied twice) leaves a monic linear factor $x-x_{3}$ with $x_{3}\in K$ : the $x$ -coordinate of the third intersection point $R^{\prime}$ . By Vieta, the sum of the roots equals the negative of the $x^{2}$ -coefficient—so $x_{1}+x_{2}+x_{3}=\lambda^{2}$ , and the unknown root is read off with no factoring at all. Hence

x_{3}=\lambda^{2}-x_{1}-x_{2},\qquad y_{3}=\lambda\,(x_{1}-x_{3})-y_{1},

(12)

and $P+Q=(x_{3},y_{3})$ . The $y$ -formula already incorporates the reflection across the $x$ -axis: the third intersection point is $(x_{3},\lambda x_{3}+\mu)$ , and reflecting gives $y_{3}=-(\lambda x_{3}+\mu)=-(\lambda x_{3}+y_{1}-\lambda x_{1})=\lambda(x_{1}-% x_{3})-y_{1}$ .

Construction 10.10 (Tangent doubling).

Suppose $P=Q=(x_{1},y_{1})$ with $y_{1}\neq 0$ . Implicit differentiation of $y^{2}=x^{3}+ax+b$ yields the tangent slope: from $2y\,dy=(3x^{2}+a)\,dx$ ,

\lambda=\frac{3x_{1}^{2}+a}{2y_{1}}.

With $\mu=y_{1}-\lambda x_{1}$ , substituting $y=\lambda x+\mu$ into the curve equation produces the same monic cubic $g(x)=x^{3}+ax+b-(\lambda x+\mu)^{2}$ as in 10.9, and here $x_{1}$ is a double root. The slogan “tangency counts the intersection twice” is a one-line check: $g(x_{1})=f(x_{1})-y_{1}^{2}=0$ , and

g^{\prime}(x_{1})=3x_{1}^{2}+a-2\lambda\,(\lambda x_{1}+\mu)=3x_{1}^{2}+a-2% \lambda y_{1}=0

by the choice of $\lambda$ , so $x_{1}$ is a repeated root of $g$ (5.40(1)). Factoring $(x-x_{1})^{2}$ out of $g$ leaves a monic linear factor $x-x_{3}$ with $x_{3}\in K$ , and Vieta now reads $x_{1}+x_{1}+x_{3}=\lambda^{2}$ , hence

x_{3}=\lambda^{2}-2x_{1},\qquad y_{3}=\lambda\,(x_{1}-x_{3})-y_{1},\qquad[2]P=% (x_{3},y_{3}).

(13)

The remaining cases are exactly those in which the line is vertical.

•

If $P=\mathcal{O}$ , then $P+Q=Q$ ; symmetrically if $Q=\mathcal{O}$ .
•

If $x_{1}=x_{2}$ but $y_{1}=-y_{2}$ (so $Q=-P$ , including the subcase $y_{1}=y_{2}=0$ ), the line is vertical, the third point is $\mathcal{O}$ , and $P+Q=\mathcal{O}$ .
•

If $P=Q$ and $y_{1}=0$ , the tangent is vertical (the slope formula in 10.10 has zero denominator), so $[2]P=\mathcal{O}$ . These are exactly the points of order two, studied in 10.9.

Every case is covered: either an input is $\mathcal{O}$ ; or both inputs are affine with $x_{1}\neq x_{2}$ (use (12)); or both are affine with $x_{1}=x_{2}$ , in which case either $y_{1}=-y_{2}$ (result $\mathcal{O}$ ) or $y_{1}=y_{2}\neq 0$ (use (13)).

Proposition 10.11 (Closure).

For all $P,Q\in E(K)$ , the point $P+Q$ computed by the case analysis above lies in $E(K)$ . In particular $E(K)$ is closed under $+$ .

Proof.

If either input is $\mathcal{O}$ , the result is the other input, which lies in $E(K)$ by hypothesis; if the result is $\mathcal{O}$ , it lies in $E(K)$ by definition. Otherwise $(x_{3},y_{3})$ is produced by (12) or (13), and in both constructions $x_{3}$ was exhibited as a root of the cubic $g(x)=x^{3}+ax+b-(\lambda x+\mu)^{2}$ —as the third root beside $x_{1},x_{2}$ in 10.9, and beside the double root $x_{1}$ in 10.10. The equation $g(x_{3})=0$ states precisely that the third intersection point $(x_{3},\lambda x_{3}+\mu)=(x_{3},-y_{3})$ satisfies the curve equation; and since the curve equation is invariant under $y\mapsto-y$ , the reflected point $(x_{3},y_{3})$ is on the curve too, so $P+Q\in E^{\mathrm{aff}}(K)\subseteq E(K)$ . For rationality, observe that all coordinates are rational expressions in $x_{1},x_{2},y_{1},y_{2},a$ whose denominators are $x_{2}-x_{1}$ or $2y_{1}$ , nonzero in the cases where each formula is invoked; so $x_{3},y_{3}\in K$ . □

Remark 10.12 (Complete versus incomplete addition).

The chord formula (12) is incomplete: it fails whenever $x_{1}=x_{2}$ —the doubling and inverse cases—and an implementation must branch into the case analysis above. Complete addition formulas, valid for all input pairs including $P=Q$ and $P=-Q$ , exist for the curves used here, at the cost of more field operations per addition; 10.13 exhibits the deployed set and 10.14 proves it complete. The distinction is load-bearing in later volumes. Halo 2’s elliptic-curve gadgets provide complete addition and use incomplete gates only where their callers justify the exclusions; the Sinsemilla hash of Orchard deliberately uses the incomplete formulas nondeterministically—an exceptional case does not violate the constraints but leaves the affected output unconstrained (the prover may choose the intermediate slope freely), which the specification models by letting the hash return $\bot$ and weakening the proved statement accordingly; its Merkle path validity check is even permitted to pass on the resulting sentinel values. Safety rests not on the proof system but on Theorem 5.4.4 of the Zcash protocol specification: any input reaching an exceptional case of the incomplete addition immediately yields a nontrivial discrete-logarithm relation among the Sinsemilla generators, so under discrete-log hardness on Pallas (10.31) such inputs are infeasible to find, for honest and adversarial provers alike.

An implementation branches; a circuit cannot. In a proof system the group law is checked by a fixed list of polynomial identities in the input, output, and auxiliary cells of a row, evaluated on every row alike, so the case analysis of this subsection has to be folded into algebra: each branch must appear as a factor that vanishes exactly when the branch is not taken. The deployed gate achieves this with five auxiliary cells, four of them “inverse-or-zero” hints that let a polynomial test a field element for zero.

Construction 10.13 (Complete addition as deployed).

Let $E:y^{2}=x^{3}+b$ over $\mathbb{F}_{p}$ with $p>3$ , and encode the point at infinity as the pair $(0,0)$ , so that every element of $E(\mathbb{F}_{p})$ is a pair of field elements. For $z\in\mathbb{F}_{p}$ let $\operatorname{inv}_{0}(z)$ be $z^{-1}$ if $z\neq 0$ and $0$ if $z=0$ . For encoded inputs $P=(x_{p},y_{p})$ and $Q=(x_{q},y_{q})$ the prover fills five auxiliary cells,

	$\displaystyle\alpha=\operatorname{inv}_{0}(x_{q}-x_{p}),\qquad\beta=% \operatorname{inv}_{0}(x_{p}),\qquad\gamma=\operatorname{inv}_{0}(x_{q}),% \qquad\delta=\begin{cases}\operatorname{inv}_{0}(y_{q}+y_{p})&\text{if }x_{q}=% x_{p},\\ 0&\text{otherwise},\end{cases}$
	$\displaystyle\lambda=\begin{cases}(y_{q}-y_{p})\,\alpha&\text{if }x_{q}\neq x_% {p},\\ 3x_{p}^{2}\,(2y_{p})^{-1}&\text{if }x_{q}=x_{p}\text{ and }y_{p}\neq 0,\\ 0&\text{otherwise},\end{cases}$

and an output pair $(x_{r},y_{r})$ : it is $Q$ if $x_{p}=0$ ; else $P$ if $x_{q}=0$ ; else $(0,0)$ if $x_{q}=x_{p}$ and $y_{q}=-y_{p}$ ; else $x_{r}=\lambda^{2}-x_{p}-x_{q}$ and $y_{r}=\lambda(x_{p}-x_{r})-y_{p}$ . The verifier accepts the row iff the twelve identities

$\displaystyle(x_{q}-x_{p})\bigl{(}(x_{q}-x_{p})\lambda-(y_{q}-y_{p})\bigr{)}$	$\displaystyle=0,$	(C1)
$\displaystyle\bigl{(}1-(x_{q}-x_{p})\alpha\bigr{)}\bigl{(}2y_{p}\lambda-3x_{p}% ^{2}\bigr{)}$	$\displaystyle=0,$	(C2)
$\displaystyle x_{p}x_{q}(x_{q}-x_{p})\,(\lambda^{2}-x_{p}-x_{q}-x_{r})$	$\displaystyle=0,$	(C3a)
$\displaystyle x_{p}x_{q}(x_{q}-x_{p})\,\bigl{(}\lambda(x_{p}-x_{r})-y_{p}-y_{r% }\bigr{)}$	$\displaystyle=0,$	(C3b)
$\displaystyle x_{p}x_{q}(y_{q}+y_{p})\,(\lambda^{2}-x_{p}-x_{q}-x_{r})$	$\displaystyle=0,$	(C3c)
$\displaystyle x_{p}x_{q}(y_{q}+y_{p})\,\bigl{(}\lambda(x_{p}-x_{r})-y_{p}-y_{r% }\bigr{)}$	$\displaystyle=0,$	(C3d)
$\displaystyle(1-x_{p}\beta)\,(x_{r}-x_{q})$	$\displaystyle=0,$	(C4a)
$\displaystyle(1-x_{p}\beta)\,(y_{r}-y_{q})$	$\displaystyle=0,$	(C4b)
$\displaystyle(1-x_{q}\gamma)\,(x_{r}-x_{p})$	$\displaystyle=0,$	(C5a)
$\displaystyle(1-x_{q}\gamma)\,(y_{r}-y_{p})$	$\displaystyle=0,$	(C5b)
$\displaystyle\bigl{(}1-(x_{q}-x_{p})\alpha-(y_{q}+y_{p})\delta\bigr{)}\,x_{r}$	$\displaystyle=0,$	(C6a)
$\displaystyle\bigl{(}1-(x_{q}-x_{p})\alpha-(y_{q}+y_{p})\delta\bigr{)}\,y_{r}$	$\displaystyle=0$	(C6b)

hold in $\mathbb{F}_{p}$ . These are, in this order, the twelve constraints of the gate complete addition in the halo2_gadgets crate (src/ecc/chip/add.rs, create_gate), each carrying there one further factor, a per-row cell equal to $1$ on the rows where the gate applies and $0$ elsewhere, which switches the list on or off; the cell assignments are those of assign_region in the same file, and the circuit field is the Pallas base field $\mathbb{F}_{p}$ .

Proposition 10.14 (The gate is complete and sound).

Suppose no affine point of $E(\mathbb{F}_{p})$ has $x=0$ and none has $y=0$ —for $y^{2}=x^{3}+b$ , that $b$ is a non-square and $-b$ a non-cube in $\mathbb{F}_{p}$ . Then for all $P,Q\in E(\mathbb{F}_{p})$ , encoded as in 10.13:

1.

(completeness) the prover’s cells satisfy (C1)–(C6b), and the output pair encodes $P+Q$ ;
2.

(soundness) every $(\lambda,\alpha,\beta,\gamma,\delta,x_{r},y_{r})\in\mathbb{F}_{p}^{7}$ satisfying (C1)–(C6b) has $(x_{r},y_{r})$ equal to the encoding of $P+Q$ .

This is what complete means for a gate: the twelve identities are satisfiable for every input pair—doublings, inverse pairs, and the identity included—and the output they admit is unique, so they are the graph of the total function $+\colon E(\mathbb{F}_{p})\times E(\mathbb{F}_{p})\to E(\mathbb{F}_{p})$ , with no case left to a branch outside the constraint system.

Proof.

Under the hypothesis an encoded pair has $x=0$ iff it is $\mathcal{O}$ , and two affine points with the same $x$ -coordinate have $y_{q}=\pm y_{p}$ with $y_{p}\neq 0$ , so they are equal or inverse and not both. One observation drives every case: for $z\in\mathbb{F}_{p}$ and any cell value $h$ , the factor $1-zh$ equals $1$ when $z=0$ , whatever $h$ is, while for $z\neq 0$ the honest choice $h=z^{-1}$ makes it $0$ . A constraint of the shape $(1-zh)\,t=0$ therefore forces $t=0$ exactly when $z=0$ and is discharged by the honest hint otherwise. Five cases exhaust the input pairs.

Case $P=\mathcal{O}$ . Then $x_{p}=0$ , so (C4a)–(C4b) force $(x_{r},y_{r})=(x_{q},y_{q})$ , the encoding of $\mathcal{O}+Q=Q$ ; that is soundness. The prover outputs $Q$ by the first clause, and its cells satisfy the rest: (C1) reads $x_{q}(x_{q}\lambda-y_{q})=0$ and holds for $\lambda=y_{q}\,\operatorname{inv}_{0}(x_{q})$ ; (C2) and (C3a)–(C3d) carry a factor $x_{p}$ or $2y_{p}\lambda-3x_{p}^{2}$ , both zero; (C5a)–(C5b) are discharged by $\gamma=x_{q}^{-1}$ if $Q\neq\mathcal{O}$ , and read $(x_{r},y_{r})=(0,0)=(x_{p},y_{p})$ if $Q=\mathcal{O}$ ; and (C6a)–(C6b) have first factor $1-x_{q}\alpha-0$ , which is $0$ for $\alpha=x_{q}^{-1}$ when $Q\neq\mathcal{O}$ , while for $Q=\mathcal{O}$ the other factor $x_{r}=y_{r}=0$ vanishes.

Case $Q=\mathcal{O}$ , $P\neq\mathcal{O}$ . Now $x_{q}=0\neq x_{p}$ , so (C5a)–(C5b) force $(x_{r},y_{r})=(x_{p},y_{p})$ , the encoding of $P$ : soundness. The prover outputs $P$ by the second clause, with $\alpha=(-x_{p})^{-1}$ and $\lambda=(-y_{p})\alpha=y_{p}/x_{p}$ ; then (C1) reads $(-x_{p})(-x_{p}\lambda+y_{p})=0$ and holds; (C2) and (C6a)–(C6b) carry the factor $1-(x_{q}-x_{p})\alpha=0$ , the latter with $\delta=0$ ; (C3a)–(C3d) carry $x_{q}=0$ ; and (C4a)–(C4b) are discharged by $\beta=x_{p}^{-1}$ .

Case $P, Q$ affine with $x_{q}\neq x_{p}$ . Constraint (C1) forces $\lambda$ to be the chord slope $(y_{q}-y_{p})/(x_{q}-x_{p})$ , and since $x_{p}x_{q}(x_{q}-x_{p})\neq 0$ , (C3a)–(C3b) force $(x_{r},y_{r})$ to be the chord formula (12)—the encoding of $P+Q$ , which is affine because $x_{p}\neq x_{q}$ . That is soundness. The prover’s $\lambda$ is that slope and its output that formula, by the fourth clause; (C3c)–(C3d) contain the same two vanishing factors; (C2), (C4a)–(C4b), (C5a)–(C5b) are discharged by the honest $\alpha$ , $\beta$ , $\gamma$ ; and (C6a)–(C6b) have first factor $1-1-0=0$ , since $\delta=0$ .

Case $Q=-P$ , $P$ affine. Here $x_{q}=x_{p}$ and $y_{q}+y_{p}=0$ , so both hint-bearing products in (C6a)–(C6b) are $0$ whatever $\alpha$ and $\delta$ are, and the constraints force $x_{r}=y_{r}=0$ : the encoding of $P+(-P)=\mathcal{O}$ , which is soundness. The prover outputs $(0,0)$ by the third clause; (C1) and (C3a)–(C3b) carry $x_{q}-x_{p}=0$ , and (C3c)–(C3d) carry $y_{q}+y_{p}=0$ ; (C2), whose first factor is now $1$ , needs $2y_{p}\lambda=3x_{p}^{2}$ , which the honest $\lambda=3x_{p}^{2}(2y_{p})^{-1}$ supplies ( $y_{p}\neq 0$ ); and (C4a)–(C5b) are discharged by $\beta=\gamma=x_{p}^{-1}$ .

Case $Q=P$ affine. Again $x_{q}=x_{p}$ fixes $(x_{q}-x_{p})\alpha=0$ , so (C2) forces $\lambda$ to be the tangent slope $3x_{p}^{2}/(2y_{p})$ , and since $x_{p}x_{q}(y_{q}+y_{p})=2x_{p}^{2}y_{p}\neq 0$ , (C3c)–(C3d) force $(x_{r},y_{r})$ to be the doubling formula (13)—the encoding of $[2]P$ , affine because $y_{p}\neq 0$ . That is soundness. The prover’s $\lambda$ is that slope and its output that formula, by the fourth clause; (C1) and (C3a)–(C3b) carry $x_{q}-x_{p}=0$ ; (C4a)–(C5b) are discharged by $\beta=\gamma=x_{p}^{-1}$ ; and (C6a)–(C6b) have first factor $1-0-2y_{p}\delta=0$ for the honest $\delta=(2y_{p})^{-1}$ . □

Example 10.15 (The gate on the toy curve).

Pallas satisfies both hypotheses of 10.14: $5$ is a non-square in $\mathbb{F}_{p}$ (7.16) and $-5$ is not a cube (10.26). The toy curve $y^{2}=x^{3}+5$ over $\mathbb{F}_{11}$ of 10.38 satisfies neither— $5=4^{2}$ gives the points $(0,\pm 4)$ , and $(8,0)$ has order $2$ —which makes it the right place to watch the gate work and to see the hypotheses earn their keep. For each input pair considered below, a script determines every output pair $(x_{r},y_{r})$ that some assignment of the five auxiliary cells in $\mathbb{F}_{11}$ makes the twelve identities accept—the search over $\alpha,\beta,\gamma,\delta$ factored by which identities mention each: $\beta$ only (C4), $\gamma$ only (C5), $\alpha$ and $\delta$ only (C2) and (C6)—so soundness is checked against all provers, not only the honest one. On the nine points $\mathcal{O}$ , $(4,\pm 5)$ , $(5,\pm 3)$ , $(6,\pm 1)$ , $(10,\pm 2)$ with $x,y\neq 0$ , all $81$ ordered pairs—eight doublings, eight inverse pairs, seventeen involving $\mathcal{O}$ —admit exactly one output, the encoding of the true sum. Three of them, worked: for $[2](5,3)$ the honest cells are $\lambda=3\cdot 5^{2}\cdot 6^{-1}=9\cdot 2=7$ and $\delta=6^{-1}=2$ , giving $(x_{r},y_{r})=(49-10,\ 7(5-6)-3)=(6,1)$ , the value of (13); for the inverse pair $(5,3)+(5,8)$ the prover supplies the same $\lambda=7$ but $\delta=\operatorname{inv}_{0}(11)=0$ , and (C6a)–(C6b) force $(0,0)$ ; for $\mathcal{O}+(5,3)$ the cells are $\alpha=5^{-1}=9$ , $\lambda=3\cdot 9=5$ , $\beta=0$ , and (C4a)–(C4b) force $(5,3)$ . Off the admissible set the gate fails as the proof predicts. With $P=(0,4)$ and $Q=(5,3)$ the identities admit only the output $(5,3)$ —the coordinate $x_{p}=0$ is read as $\mathcal{O}$ —whereas $P+Q=(10,9)$ (10.38); the pair $(0,4)+(0,7)$ admits no output at all, (C4b) demanding $y_{r}=7$ and (C5b) $y_{r}=4$ ; and $(8,0)+(8,0)$ admits none either, since (C2) reduces to $3\cdot 8^{2}=0$ , false in $\mathbb{F}_{11}$ . On Pallas none of the three inputs exists, and the gate is complete.

10.5 Identity, inverses, commutativity, and associativity

The destination of the whole construction is the following theorem.

Theorem 10.16 (Group law).

Let $E$ be an elliptic curve over a field $K$ . The set $E(K)$ with the chord-and-tangent operation $+$ of 10.7 is an abelian group with identity $\mathcal{O}$ .

Closure is 10.11. The next proposition supplies every remaining axiom except one.

Proposition 10.17 (Identity, inverses, commutativity).

The operation $+$ on $E(K)$ has the following properties.

1.

The point $\mathcal{O}$ is a two-sided identity: $P+\mathcal{O}=\mathcal{O}+P=P$ for all $P$ .
2.

Every $P$ has the two-sided inverse $-P$ of 10.8: $P+(-P)=\mathcal{O}$ .
3.

The operation is commutative: $P+Q=Q+P$ .

Proof.

(1) is the first clause of 10.7. (2): for $P=(x,y)$ with $y\neq 0$ , the line through $P$ and $-P=(x,-y)$ is vertical, so its third point is $\mathcal{O}$ and $P+(-P)=\mathcal{O}$ by the vertical-line case; for $y=0$ one has $P=-P$ and $[2]P=\mathcal{O}$ directly by the vertical-tangent case; and $\mathcal{O}+(-\mathcal{O})=\mathcal{O}+\mathcal{O}=\mathcal{O}$ . (3): the chord through $P$ and $Q$ does not depend on the order in which the two points are named, and neither does the tangent in the doubling case; algebraically, the formulas (12) are symmetric under the swap $(x_{1},y_{1})\leftrightarrow(x_{2},y_{2})$ —the slope $\lambda$ is unchanged, and $x_{3}=\lambda^{2}-x_{1}-x_{2}$ is symmetric in $x_{1},x_{2}$ . □

The one axiom not yet established is associativity, $(P+Q)+R=P+(Q+R)$ , and it is the deep and surprising part of the theory: the definition gives no reason why reflecting third intersection points should be an associative operation, and a brute-force verification through the explicit formulas splinters into a large number of coordinate cases, each demanding lengthy rational-function identities. We sketch the conceptual proof, which exhibits the reason associativity holds.

Proof of associativity (sketch).

The key tool is the classical Cayley–Bacharach theorem for plane cubics: if two cubics with no common component meet in nine points counted with intersection multiplicity, then any third cubic passing through eight of them with the required multiplicities also passes through the ninth. To prove $(P+Q)+R=P+(Q+R)$ , one writes both sides via the chord-and-tangent construction and arranges the relevant intersections among the curve $E$ and two degenerate cubics, each a product of three suitably chosen lines. Cayley–Bacharach forces the two candidate sums to coincide; its intersection-multiplicity formulation includes tangencies and coincident points. Translating “reflect across the $x$ -axis” into “the three points of any line sum to $\mathcal{O}$ ” renders the bookkeeping uniform.

A complete, case-free treatment identifies $E(K)$ with the degree-zero part $\mathrm{Pic}^{0}(E)$ of the divisor class group of the curve via the map $P\mapsto[P]-[\mathcal{O}]$ , a bijection that intertwines the two operations; the group law on $\mathrm{Pic}^{0}(E)$ is manifestly associative, because it is inherited from addition of divisors modulo principal divisors. Either route yields a genuine proof; both lie beyond the elementary scope of this volume, so we take associativity as established. □

Remark 10.18 (The notation $[n]P$ ).

For $n\in\mathbb{Z}$ and $P\in E(K)$ , we write $[n]P$ for the $n$ -fold sum $P+\cdots+P$ , with $[0]P=\mathcal{O}$ and $[-n]P=-([n]P)$ . This makes the abelian group $E(K)$ a $\mathbb{Z}$ -module: integers act on points. The map $n\mapsto[n]P$ is the scalar multiplication of 10.20—not any coordinate-wise product.

10.6 Projective and Jacobian coordinates

The affine formulas (12) and (13) each require a field inversion, by $x_{2}-x_{1}$ or $2y_{1}$ . In a large prime field an inversion costs roughly as much as dozens of multiplications, whether computed by the extended Euclidean algorithm (6.1) or as $z^{p-2}$ by Fermat (6.4). When a long chain of group operations arises, as in the scalar multiplication of the next subsection, it pays to defer all inversions to the very end by carrying points in a redundant coordinate system whose group law uses only additions, subtractions, and multiplications.

Remark 10.19 (Inversion-free coordinate systems).

Two redundant systems serve this purpose. In (homogeneous) projective coordinates, a triple $[X:Y:Z]$ with $Z\neq 0$ represents the affine point $(X/Z,Y/Z)$ on the projective curve (11), with $\mathcal{O}=[0:1:0]$ . In Jacobian coordinates, a triple $(X:Y:Z)$ with $Z\neq 0$ represents $(X/Z^{2},Y/Z^{3})$ , under the equivalence $(X,Y,Z)\sim(\lambda^{2}X,\lambda^{3}Y,\lambda Z)$ ; the curve equation becomes $Y^{2}=X^{3}+aXZ^{4}+bZ^{6}$ . In either system the addition and doubling formulas can be rewritten with no divisions at all, at the cost of more multiplications per operation; a long chain of group operations then defers every inversion to a single final recovery of affine coordinates—compute $Z^{-1}$ once, then the needed powers of it by multiplication. Jacobian coordinates usually yield the faster doubling and are the standard choice in cryptographic libraries, including the implementation Halo 2 uses: the pasta_curves crate carries its curve points in Jacobian coordinates. For curves $y^{2}=x^{3}+b$ with $a=0$ , the term $aZ^{4}$ in the Jacobian doubling formulas vanishes, making doubling especially cheap—one reason the Pasta curves take $a=0$ .

10.7 Scalar multiplication and double-and-add

The fundamental operation of elliptic-curve cryptography is scalar multiplication: given a point $P$ and an integer $n\geq 0$ , compute

[n]P=\underbrace{P+P+\cdots+P}_{n\ \text{times}}.

Computing this by $n-1$ successive additions is infeasible when $n$ has hundreds of bits. Instead one uses the binary expansion of $n$ , exactly as in the square-and-multiply technique of 6.2; as 6.3 promised, the additive rendition of that algorithm is the following.

Definition 10.20 (Double-and-add).

If $n=0$ , return $\mathcal{O}$ . Otherwise write $n=\sum_{i=0}^{k-1}n_{i}2^{i}$ with digits $n_{i}\in\{0,1\}$ and top digit $n_{k-1}=1$ . The left-to-right double-and-add algorithm computes $[n]P$ as follows: set $R\leftarrow P$ ; for $i=k-2$ down to $0$ , set $R\leftarrow[2]R$ , and if $n_{i}=1$ set $R\leftarrow R+P$ ; return $R$ .

Proposition 10.21.

For $n\geq 1$ , double-and-add returns $[n]P$ using exactly $k-1$ doublings and at most $k-1$ additions, where $k=\lfloor\log_{2}n\rfloor+1$ is the bit length of $n$ . For $n=0$ , it returns $\mathcal{O}$ without a group operation.

Proof.

The case $n=0$ is immediate. Let $n\geq 1$ , and let $R_{j}$ denote the value of $R$ after bits $n_{k-1},\ldots,n_{j}$ have been incorporated. We claim $R_{j}=[\lfloor n/2^{j}\rfloor]P$ , by downward induction on $j$ . At initialization, $R_{k-1}=P=[\lfloor n/2^{k-1}\rfloor]P$ because the top bit is $1$ . Assuming $R_{j+1}=[\lfloor n/2^{j+1}\rfloor]P$ , the next iteration computes

[2]R_{j+1}+[n_{j}]P=[\,2\lfloor n/2^{j+1}\rfloor+n_{j}\,]P=[\lfloor n/2^{j}% \rfloor]P,

where the last step is the digit identity $2\lfloor n/2^{j+1}\rfloor+n_{j}=\lfloor n/2^{j}\rfloor$ : stripping the last bit of $\lfloor n/2^{j}\rfloor$ and re-appending it recovers the number. At $j=0$ the invariant reads $R_{0}=[n]P$ , which is what the algorithm returns. For the counts, the loop has exactly $k-1$ iterations, each performing one doubling and at most one addition. □

Scalar multiplication by an $n$ -bit scalar therefore costs $O(n)$ group operations— $O(n)$ field operations up to constant factors, or $O(n\log^{2}p)$ bit operations with schoolbook field arithmetic. This efficiency of the forward map, contrasted with the apparent hardness of the inverse problem (§10.11), is the foundation of the cryptography.

10.8 The group structure of $E(\mathbb{F}_{p})$

Now specialise $K=\mathbb{F}_{p}$ , the prime field with $p$ elements ( $p$ prime, $p>3$ ). Since $\mathbb{F}_{p}$ is finite, so is $E(\mathbb{F}_{p})$ : each of the $p$ values of $x$ admits at most two values of $y$ (5.18, applied to $y^{2}-f(x)$ as a polynomial in $y$ ), so with $\mathcal{O}$ there are at most $2p+1$ points. By 10.16, the set $E(\mathbb{F}_{p})$ is thus a finite abelian group. One of the central theorems of the subject governs its order.

Theorem 10.22 (Hasse).

Let $E$ be an elliptic curve over $\mathbb{F}_{p}$ . Write

\#E(\mathbb{F}_{p})=p+1-t,

which defines the integer $t$ , called the trace of Frobenius. Then

\lvert t\rvert\leq 2\sqrt{p};

equivalently, $\#E(\mathbb{F}_{p})$ lies in the Hasse interval $[\,p+1-2\sqrt{p},\;p+1+2\sqrt{p}\,]$ .

Proof (sketch).

The count has an exact character-sum expression. For fixed $x$ , the number of $y\in\mathbb{F}_{p}$ with $y^{2}=f(x)$ is $1+\left(\frac{f(x)}{p}\right)$ when $f(x)\neq 0$ —two solutions for a nonzero square, none for a non-square (7.12)—and exactly $1=1+\left(\frac{0}{p}\right)$ when $f(x)=0$ , using the Legendre symbol of 7.14 with the convention $\left(\frac{0}{p}\right)=0$ . Summing over $x$ ,

\#E^{\mathrm{aff}}(\mathbb{F}_{p})=\sum_{x\in\mathbb{F}_{p}}\left(1+\left(% \frac{x^{3}+ax+b}{p}\right)\right)=p+\sum_{x\in\mathbb{F}_{p}}\left(\frac{x^{3% }+ax+b}{p}\right),

so $t=-\sum_{x}\left(\frac{x^{3}+ax+b}{p}\right)$ . Heuristically, as $x$ ranges over $\mathbb{F}_{p}$ the value $f(x)$ is a nonzero square about half the time (two points), a non-square about half the time (none), and zero occasionally (one point); the $p$ summands $\pm 1$ behave like a random walk, and Hasse’s bound $\lvert t\rvert\leq 2\sqrt{p}$ is exactly square-root cancellation in this character sum.

The conceptual proof realises $t$ as the trace of the $p$ -power Frobenius endomorphism $\pi\colon(x,y)\mapsto(x^{p},y^{p})$ of the curve—the curve-level shadow of the field automorphism of 6.14. One shows that $\pi$ satisfies the characteristic equation $\pi^{2}-[t]\pi+[p]=0$ in the endomorphism ring of $E$ , and that the associated quadratic form (the degree) is positive definite; the discriminant condition $t^{2}-4p\leq 0$ for the complex roots of the characteristic polynomial then yields $\lvert t\rvert\leq 2\sqrt{p}$ . The full argument requires the theory of isogenies and the Weil pairing, beyond the present scope. □

Hasse’s theorem says the order of $E(\mathbb{F}_{p})$ is very close to $p$ : the deviation from $p+1$ is at most $2\sqrt{p}$ , a relative error of order $p^{-1/2}$ . For cryptography this is crucial twice over. It guarantees with no brute-force count that the group is large—about $p$ elements, so about $255$ bits for the Pasta curves—and it anchors the point-counting algorithms (Schoof–Elkies–Atkin) that compute the exact order in polynomial time, which is how curve designers certify their group orders.

For the cryptographic application one wants $E(\mathbb{F}_{p})$ to contain a large subgroup of prime order. The general structure theory of $E(\mathbb{F}_{p})$ as an abelian group is not needed in this series, because the Pasta curves are designed so that $\#E(\mathbb{F}_{p})$ is itself prime: a group of prime order is cyclic with no proper nontrivial subgroups (3.34), so $E(\mathbb{F}_{p})$ is cyclic of prime order—the optimal case.

10.9 Torsion, the cofactor, and prime-order subgroups

Definition 10.23 (Order of a point and torsion).

The order of a point $P\in E(\mathbb{F}_{p})$ is its order as a group element (3.11): the least integer $m\geq 1$ with $[m]P=\mathcal{O}$ . It exists and divides $\#E(\mathbb{F}_{p})$ , by Lagrange’s theorem (3.29 via 3.30). For an integer $m\geq 1$ , the $m$ -torsion subgroup is

E[m]=\{\,P\in E(\overline{\mathbb{F}_{p}}):[m]P=\mathcal{O}\,\},

the points over the algebraic closure killed by $m$ ; its rational part is $E(\mathbb{F}_{p})[m]=E[m]\cap E(\mathbb{F}_{p})$ .

Definition 10.24 (Cofactor).

Suppose $\#E(\mathbb{F}_{p})=h\cdot r$ , where $r$ is the (large) prime to be used and $h$ is the remaining factor. The integer $h$ is the cofactor, and $r$ is the order of the prime-order subgroup: a point $P$ of order $r$ generates a cyclic subgroup $\langle P\rangle\cong\mathbb{Z}/r\mathbb{Z}$ , and this subgroup is where the cryptography lives.

A nontrivial cofactor $h>1$ is undesirable: it admits small-subgroup points, of order dividing $h$ , which can leak information or break protocol assumptions—the small-subgroup attacks of 7.25. Implementations therefore either clear the cofactor, multiplying incoming points by $h$ , or use prime-order curves with $h=1$ . The Pasta curves have cofactor $1$ : the orders $\#E_{p}(\mathbb{F}_{p})=q$ and $\#E_{q}(\mathbb{F}_{q})=p$ are themselves prime, so $E_{p}(\mathbb{F}_{p})\cong\mathbb{Z}/q\mathbb{Z}$ and $E_{q}(\mathbb{F}_{q})\cong\mathbb{Z}/p\mathbb{Z}$ are cyclic of prime order and no cofactor clearing is ever needed. This is one of the principal design advantages of the Pasta cycle for proof systems.

Proposition 10.25 (Two-torsion).

The affine points of order $2$ in $E(\mathbb{F}_{p})$ are exactly the points $(x_{0},0)$ with $f(x_{0})=x_{0}^{3}+ax_{0}+b=0$ . Hence $E(\mathbb{F}_{p})$ has $0$ , $1$ , or $3$ points of order $2$ according as $f$ has $0$ , $1$ , or $3$ roots in $\mathbb{F}_{p}$ ; and $\#E(\mathbb{F}_{p})$ is even if and only if $f$ has a root in $\mathbb{F}_{p}$ .

Proof.

A point $P=(x,y)$ has order $2$ iff $P=-P$ and $P\neq\mathcal{O}$ , i.e. $y=-y$ , i.e. $y=0$ (since $\operatorname{char}(\mathbb{F}_{p})\neq 2$ ); the curve equation then forces $f(x)=0$ . Conversely each root $x_{0}$ of $f$ in $\mathbb{F}_{p}$ gives the order- $2$ point $(x_{0},0)$ .

Next, the number $N$ of roots of $f$ in $\mathbb{F}_{p}$ can only be $0$ , $1$ , or $3$ : two roots force a third. Suppose $f$ has distinct roots $r_{1}\neq r_{2}$ in $\mathbb{F}_{p}$ . The factor theorem (5.17) gives $f=(x-r_{1})h$ ; evaluating at $r_{2}$ yields $0=(r_{2}-r_{1})\,h(r_{2})$ , so $h(r_{2})=0$ , and a second application factors the monic cubic completely, $f=(x-r_{1})(x-r_{2})(x-r_{3})$ with $r_{3}\in\mathbb{F}_{p}$ —explicitly $r_{3}=-r_{1}-r_{2}$ by Vieta, the depressed cubic having no $x^{2}$ term. Nonsingularity says $f$ has no repeated root even over $\overline{\mathbb{F}_{p}}$ (10.4(2)), so $r_{3}\notin\{r_{1},r_{2}\}$ , and $f$ has exactly three roots (5.18 caps the count). Hence $N\in\{0,1,3\}$ , matching the trichotomy of the statement. Together with $\mathcal{O}$ the order- $2$ points form the rational $2$ -torsion subgroup $E(\mathbb{F}_{p})[2]$ , which is accordingly trivial, $\mathbb{Z}/2\mathbb{Z}$ , or $\mathbb{Z}/2\mathbb{Z}\times\mathbb{Z}/2\mathbb{Z}$ .

For the parity claim, consider negation $P\mapsto-P$ , an involution—a self-inverse map—of the finite set $E(\mathbb{F}_{p})$ . Its fixed points are exactly $\mathcal{O}$ and the points $(x_{0},0)$ ; every other point pairs off with its distinct negative into a $2$ -element orbit. Counting the set by orbits,

\#E(\mathbb{F}_{p})\equiv 1+N\pmod{2},

where $N\in\{0,1,3\}$ is the number of roots of $f$ in $\mathbb{F}_{p}$ . Hence $\#E(\mathbb{F}_{p})$ is even iff $N$ is odd, i.e. iff $N\geq 1$ , i.e. iff $f$ has a root in $\mathbb{F}_{p}$ . (The device is worth remembering: an involution reads off a group’s cardinality modulo $2$ from its fixed points alone.) □

Remark 10.26 (No two-torsion on the Pasta curves).

For $y^{2}=x^{3}+5$ over $\mathbb{F}_{p}$ , the curve has a point of order $2$ iff $x^{3}+5=0$ has a solution, i.e. iff $-5$ is a cube in $\mathbb{F}_{p}$ . For the Pasta primes the order $\#E_{p}(\mathbb{F}_{p})=q$ is odd (it is prime), so there are no rational $2$ -torsion points; consistently, $-5$ is not a cube in $\mathbb{F}_{p}$ .

10.10 Base fields, scalar fields, and the Pasta cycle

Step back from the geometry and ask what a machine actually does when it works on $E(\mathbb{F}_{p})$ . Every operation of the group law—the slope $\lambda=(y_{2}-y_{1})(x_{2}-x_{1})^{-1}$ , the squarings, and the inversions needed to add and to double—is arithmetic in $\mathbb{F}_{p}$ , performed with exactly the prime-field algorithms of 6.1 (extended-Euclid or Fermat inversion). The field $\mathbb{F}_{p}$ is called the base field (or coordinate field) of the curve: it is where the coordinates live.

Scalars live elsewhere. By 10.22 the group $E(\mathbb{F}_{p})$ is a finite abelian group of order $N=\#E(\mathbb{F}_{p})$ close to $p$ ; for cryptography one selects a curve whose order has a large prime factor $r$ , and keys and signatures reside in the subgroup of order $r$ (10.24). A scalar multiplication $P\mapsto[s]P$ on a point of order $r$ depends only on $s\bmod r$ , since $[r]P=\mathcal{O}$ (3.12); scalars therefore live modulo $r$ —and since $r$ is prime, they form a field (4.26).

Definition 10.27 (Base field and scalar field).

For an elliptic curve used in cryptography, with a prime-order subgroup of order $r$ :

•

the base field $\mathbb{F}_{p}$ is the field over which the curve is defined and in which point coordinates lie;
•

the scalar field $\mathbb{F}_{r}=\mathbb{Z}/r\mathbb{Z}$ is the field of scalars by which one multiplies points, i.e. the integers modulo the subgroup order $r$ .

Both are prime fields, but in general $p\neq r$ .

Remark 10.28 (Two fields at once, and the Pasta cycle).

A typical elliptic-curve operation manipulates two distinct prime fields simultaneously: the exponent arithmetic runs in $\mathbb{F}_{r}$ while the coordinate arithmetic runs in $\mathbb{F}_{p}$ . Halo 2’s Pallas and Vesta curves (the “Pasta” pair) exploit this deliberately. They form a cycle of curves: the base field of one is the scalar field of the other and vice versa,

\#E_{p}(\mathbb{F}_{p})=q,\qquad\#E_{q}(\mathbb{F}_{q})=p,

so the scalar field of Pallas is $\mathbb{F}_{q}$ , the base field of Vesta, and symmetrically (§5.4.9.6 of the Zcash protocol specification). This lets a proof system express the verifier of one curve’s arithmetic natively in the field of the other, enabling the recursive proof composition at the heart of Halo 2. Moreover both primes are chosen $\equiv 1\pmod{2^{32}}$ , so by 6.22 each field contains a multiplicative subgroup of order $2^{32}$ , furnishing the high-order roots of unity that the number-theoretic transform of 9 needs for fast polynomial multiplication.

10.11 The elliptic-curve discrete logarithm problem

The section’s opening problem now returns in its proper habitat. The discrete logarithm problem of 7.21 was stated for an abstract cyclic group; the elliptic-curve instance reads as follows, in additive notation.

Definition 10.29 (ECDLP).

Let $P\in E(\mathbb{F}_{p})$ be a point of large prime order $r$ , generating $G=\langle P\rangle$ . The elliptic-curve discrete logarithm problem (ECDLP) is: given $P$ and a point $Q\in G$ , find the unique integer $n\in\{0,1,\ldots,r-1\}$ with $Q=[n]P$ . One writes $n=\log_{P}Q$ .

The map $n\mapsto[n]P$ is a group isomorphism $\mathbb{Z}/r\mathbb{Z}\to G$ (3.43), so a discrete logarithm always exists and is unique; the entire content of the problem is computational. The forward map is fast by double-and-add (10.21); no efficient algorithm is known to invert it on a well-chosen curve. What is known is the generic pair of attacks, which transfer verbatim from 7.22 to the additive setting.

Proposition 10.30 (Square-root attacks).

Baby-step giant-step solves the ECDLP in a group of prime order $r$ in $O(\sqrt{r})$ group operations and $O(\sqrt{r})$ space. Pollard’s rho method matches the $O(\sqrt{r})$ bound in expectation with only $O(1)$ space, under a modelling assumption on its pseudo-random walk that is stated explicitly in the proof and is unproved for every concrete walk.

Proof.

For baby-step giant-step, set $m=\lceil\sqrt{r}\rceil$ and write the unknown logarithm as $n=im+j$ with $0\leq i,j<m$ ; since $m^{2}\geq r$ , every $n\in\{0,\ldots,r-1\}$ has such a decomposition. Tabulate the baby steps $[j]P$ for $j=0,\ldots,m-1$ (a table of $m$ points, built with $m-1$ additions), compute $S=[m]P$ once, and walk the giant steps $Q-[i]S$ for $i=0,1,2,\ldots$ , testing each against the table. At $i=\lfloor n/m\rfloor$ the walk hits $Q-[im]P=[n-im]P=[j]P$ , a table entry; the collision reveals $i$ and $j$ , hence $n=im+j$ . Both the table and the walk cost $O(m)=O(\sqrt{r})$ group operations, and the table holds $O(\sqrt{r})$ points.

Pollard’s rho eliminates the table, at the price of an explicitly heuristic analysis. The algorithm takes a pseudo-random walk on $G$ whose every position is maintained in the form $[a]P+[b]Q$ with known coefficients $a, b$ , started from such a combination with random coefficients; the walk’s next step depends only on the current point, so once the walk revisits a point it cycles forever. A repeat is therefore detected with $O(1)$ memory: run a second copy of the walk at double speed, and the two copies meet at a common point inside the cycle within a constant factor of the first repeat time. Modelling assumption: the successive positions of the walk behave like independent uniform samples from $G$ . No proof of this is known for any concrete walk—the assumption is what “well-designed” means, and experiment supports it—and the rest of the argument is conditional on it. Under the assumption, the first $k$ positions are pairwise distinct with probability at most $e^{-k(k-1)/(2r)}$ by the birthday bound—the forward reference 11.18 is quantitative machinery from the closing section—so the number $T$ of steps to the first repeat satisfies $\Pr[T>k]\leq e^{-k(k-1)/(2r)}$ . The tail-sum formula (11.33) converts the tail bound into an expectation bound: with $m=\lceil\sqrt{r}\rceil$ and $r\geq 4$ ,

\mathbb{E}[T]=\sum_{k\geq 1}\Pr[T\geq k]\leq m\sum_{j\geq 0}\Pr[T>jm]\leq m% \Bigl{(}1+\sum_{j\geq 1}e^{-j/4}\Bigr{)}=O(\sqrt{r}),

where the middle step groups the indices $k$ into blocks of length $m$ , bounding each block by its first term, and the last uses $jm(jm-1)\geq j^{2}\,m(m-1)\geq j^{2}(r-\sqrt{r})\geq j^{2}r/2$ for $j\geq 1$ , so that $\Pr[T>jm]\leq e^{-j^{2}/4}\leq e^{-j/4}$ , a convergent geometric tail. A repeat presents one group element with two representations, $[a]P+[b]Q=[a^{\prime}]P+[b^{\prime}]Q$ . If $b^{\prime}\not\equiv b\pmod{r}$ , this rearranges to $[a-a^{\prime}]P=[b^{\prime}-b]Q=[(b^{\prime}-b)\,n]P$ , whence

n\equiv(a-a^{\prime})(b^{\prime}-b)^{-1}\pmod{r},

the inverse existing because $r$ is prime. If instead $b^{\prime}\equiv b$ , then $[a]P=[a^{\prime}]P$ forces $a\equiv a^{\prime}$ : the two representations coincide, the collision reveals nothing, and the walk is restarted with fresh random starting coefficients; that such degenerate collisions are rare is a further part of the heuristic, borne out in practice. Both algorithms run in time exponential in the bit length $\log_{2}r$ . □

Remark 10.31 (Best known attacks on well-chosen curves).

For well-chosen curves, no unrestricted classical attack faster than $O(\sqrt{r})$ is known; this is not an unconditional lower bound for all classical algorithms. In the classical generic-group model, however, Shoup’s matching lower bound is proved (7.22). For $r\approx 2^{254}$ —the $255$ -bit Pasta orders—this is about $2^{127}$ operations, infeasible. Curves with special structure can be weaker, and the known weak classes are avoided by design. Anomalous curves, those with $\#E(\mathbb{F}_{p})=p$ , admit a polynomial-time attack through the formal group. The MOV/Frey–Rück attack transfers the ECDLP into a finite-field discrete logarithm when the embedding degree—the least $k\geq 1$ with $r\mid p^{k}-1$ , i.e. the degree (8.4; the dimension of the extension over its base) of the smallest extension of $\mathbb{F}_{p}$ whose multiplicative group contains a subgroup of order $r$ —is small, where index calculus applies. Cryptographically secure curves, the Pasta curves included, are chosen with a large prime subgroup order, a large embedding degree, and $\#E(\mathbb{F}_{p})\neq p$ , defeating every known subexponential attack.

Remark 10.32 (The index-calculus contrast).

The contrast with the multiplicative groups $\mathbb{F}_{p}^{\times}$ is the economic heart of the subject. In $\mathbb{F}_{p}^{\times}$ the index-calculus method solves the discrete logarithm in subexponential time $L_{p}[1/3]$ —shorthand for $2^{\Theta(\lambda^{1/3}(\log\lambda)^{2/3})}$ operations in the bit length $\lambda=\log_{2}p$ , a notation defined precisely in 11.60 of the closing section—exploiting the integer arithmetic behind the residues (7.22); those groups must therefore be made very large. On a well-chosen elliptic curve no index calculus is known—the points offer no analogue of “factoring into small primes”—so the generic $O(\sqrt{r})$ bound stands, and much smaller groups suffice: about $256$ bits for $128$ -bit security, versus thousands of bits for $\mathbb{F}_{p}^{\times}$ . Smaller groups mean faster arithmetic and shorter keys, which is why elliptic curves dominate modern protocols, including Halo 2.

10.12 The $j$ -invariant and the GLV endomorphism

Two final pieces of structure round out the theory: a single quantity that classifies curves up to isomorphism, and an “extra symmetry” available exactly when that quantity vanishes—which the Pasta curves arrange on purpose.

Definition 10.33 ( $j$ -invariant).

The $j$ -invariant of the curve $y^{2}=x^{3}+ax+b$ (with $4a^{3}+27b^{2}\neq 0$ ) is

j=1728\,\frac{4a^{3}}{4a^{3}+27b^{2}}\in K,

where $1728=12^{3}$ is a normalising constant of historical origin.

Proposition 10.34.

Two elliptic curves over $\overline{K}$ are isomorphic over $\overline{K}$ if and only if they have the same $j$ -invariant. The admissible coordinate changes preserving short Weierstrass form are $(x,y)\mapsto(u^{2}x,u^{3}y)$ for $u\in\overline{K}^{\times}$ , under which $(a,b)\mapsto(u^{4}a,u^{6}b)$ ; the combination $j$ is invariant.

Proof (sketch).

A direct computation shows that the only isomorphisms between short Weierstrass curves fixing $\mathcal{O}$ are the scalings $(x,y)\mapsto(u^{2}x,u^{3}y)$ . Substituting $x=u^{-2}x^{\prime}$ , $y=u^{-3}y^{\prime}$ into $y^{2}=x^{3}+ax+b$ and clearing $u^{6}$ gives $y^{\prime 2}=x^{\prime 3}+u^{4}a\,x^{\prime}+u^{6}b$ , which is the stated action on coefficients. Under it, numerator and denominator of $4a^{3}/(4a^{3}+27b^{2})$ both scale by $u^{12}$ , so $j$ is unchanged. Conversely, given two curves with equal $j$ -invariants one solves for a suitable $u$ transforming one coefficient pair into the other, with separate easy cases $j=0$ (both $a$ vanish) and $j=1728$ (both $b$ vanish). □

Remark 10.35 (The Pasta curves have $j=0$ ).

For $y^{2}=x^{3}+b$ one has $a=0$ , so $j=0$ ; both Pasta curves have $j=0$ . Curves with $j=0$ are special: they admit an extra automorphism of order $3$ , which underlies the efficient endomorphism described next. (At the other extreme, $b=0$ gives $j=1728$ and an order- $4$ automorphism.) The vanishing $j=0$ is deliberate in the Pasta design: it is what makes the Gallant–Lambert–Vanstone (GLV) speedup available, roughly halving the doubling count in scalar multiplication.

Proposition 10.36 (The GLV endomorphism for $y^{2}=x^{3}+b$ ).

Suppose $\mathbb{F}_{p}$ contains a primitive cube root of unity $\omega$ , i.e. $p\equiv 1\pmod{3}$ (6.22), so $\omega\in\mathbb{F}_{p}$ satisfies $\omega^{2}+\omega+1=0$ . On $E:y^{2}=x^{3}+b$ , the map

\phi(x,y)=(\omega x,\ y),\qquad\phi(\mathcal{O})=\mathcal{O},

is a group endomorphism of $E(\mathbb{F}_{p})$ . Let $G=\langle P\rangle$ be a subgroup of prime order $r$ with $r\equiv 1\pmod{3}$ and $\phi(G)\subseteq G$ . Then $\phi$ acts on $G$ as multiplication by a scalar: there is $\lambda\in\mathbb{Z}/r\mathbb{Z}$ with $\lambda^{2}+\lambda+1\equiv 0\pmod{r}$ and

\phi(Q)=[\lambda]\,Q\quad\text{for all }Q\in G.

For the Pasta curves the hypothesis $\phi(G)\subseteq G$ is automatic, since $E(\mathbb{F}_{p})$ itself is the prime-order group $G$ ; and $r\equiv 1\pmod{3}$ holds for both orders.

Proof.

The map lands on the curve. If $y^{2}=x^{3}+b$ then $y^{2}=(\omega x)^{3}+b$ , because $\omega^{3}=1$ ; so $(\omega x,y)\in E(\mathbb{F}_{p})$ .

The map is a homomorphism. We check $\phi(P_{1}+P_{2})=\phi(P_{1})+\phi(P_{2})$ against the case analysis of §10.4. The $\mathcal{O}$ cases are trivial, and $\phi(-P)=-\phi(P)$ since negation touches only $y$ ; in particular the inverse case $\phi(P)+\phi(-P)=\mathcal{O}=\phi(\mathcal{O})$ is respected, and $\phi$ preserves the case split, since it preserves equality of $x$ -coordinates. For a chord ( $x_{1}\neq x_{2}$ ), the slope transforms as

\lambda^{\prime}=\frac{y_{2}-y_{1}}{\omega x_{2}-\omega x_{1}}=\omega^{-1}% \lambda=\omega^{2}\lambda,

using $\omega^{-1}=\omega^{2}$ . Then, by (12) and $\omega^{4}=\omega$ ,

x_{3}^{\prime}=\lambda^{\prime 2}-\omega x_{1}-\omega x_{2}=\omega^{4}\lambda^% {2}-\omega x_{1}-\omega x_{2}=\omega\,(\lambda^{2}-x_{1}-x_{2})=\omega x_{3},

y_{3}^{\prime}=\lambda^{\prime}(\omega x_{1}-x_{3}^{\prime})-y_{1}=\omega^{2}% \lambda\cdot\omega(x_{1}-x_{3})-y_{1}=\lambda(x_{1}-x_{3})-y_{1}=y_{3},

so $\phi(P_{1})+\phi(P_{2})=(\omega x_{3},y_{3})=\phi(P_{1}+P_{2})$ . The tangent case runs identically with $\lambda^{\prime}=3(\omega x_{1})^{2}/(2y_{1})=\omega^{2}\lambda$ in (13).

The relation $\phi^{2}+\phi+\operatorname{id}=0$ . Let $P=(x,y)$ be affine; we show $P+\phi(P)+\phi^{2}(P)=\mathcal{O}$ directly from the formulas of §10.4.

First let $x\neq 0$ . The points $P=(x,y)$ , $\phi(P)=(\omega x,y)$ , $\phi^{2}(P)=(\omega^{2}x,y)$ share their $y$ -coordinate and have pairwise distinct $x$ -coordinates, since $1,\omega,\omega^{2}$ are distinct and $x\neq 0$ . The chord formula (12) applies to $P+\phi(P)$ , with slope $\lambda=(y-y)/(\omega x-x)=0$ :

x_{3}=0-x-\omega x=-(1+\omega)\,x=\omega^{2}x,\qquad y_{3}=0\cdot(x-x_{3})-y=-y,

using $1+\omega+\omega^{2}=0$ . Hence $P+\phi(P)=(\omega^{2}x,-y)=-\phi^{2}(P)$ (10.8), and $P+\phi(P)+\phi^{2}(P)=\mathcal{O}$ .

If instead $x=0$ , the three points coincide: $\phi(P)=\phi^{2}(P)=P$ . Here $y\neq 0$ , since $x=y=0$ on the curve would force $b=0$ , which nonsingularity $27b^{2}\neq 0$ forbids; so the doubling formula (13) applies, with $a=0$ :

\lambda=\frac{3\cdot 0^{2}+0}{2y}=0,\qquad x_{3}=0-2\cdot 0=0,\qquad y_{3}=0% \cdot(0-0)-y=-y,

so $[2]P=(0,-y)=-P$ , hence $P+\phi(P)+\phi^{2}(P)=[3]P=\mathcal{O}$ in this case too. (The three points $P$ , $\phi(P)$ , $\phi^{2}(P)$ are exactly the intersections of the horizontal line through $P$ with the curve, the roots of $X^{3}=y^{2}-b$ being $x$ , $\omega x$ , $\omega^{2}x$ ; the computation just performed is the “three points of a line sum to $\mathcal{O}$ ” picture made rigorous, including the triple intersection at $x=0$ .)

With $\phi(\mathcal{O})=\mathcal{O}$ the identity holds on all of $E(\mathbb{F}_{p})$ ; as an identity of endomorphisms, $\phi^{2}+\phi+\operatorname{id}=0$ . Incidentally $\phi^{3}=\operatorname{id}$ , since $\omega^{3}=1$ ; and whenever $\#E(\mathbb{F}_{p})>3$ —as always at cryptographic sizes, the Pasta curves included— $\phi$ has order exactly $3$ , because at most two affine points, $(0,\pm y_{0})$ with $y_{0}^{2}=b$ , share the coordinate $x=0$ , so some point of $E(\mathbb{F}_{p})$ has $x\neq 0$ and $\phi$ moves it. The proviso is not vacuous: $y^{2}=x^{3}+4$ over $\mathbb{F}_{7}$ has only the three points $\mathcal{O}$ , $(0,2)$ , $(0,5)$ , and there $\phi=\operatorname{id}$ .

Action on $G$ as a scalar. The subgroup $G\cong\mathbb{Z}/r\mathbb{Z}$ is cyclic with generator $P$ , and $\phi(G)\subseteq G$ by hypothesis, so $\phi(P)=[\lambda]P$ for some $\lambda\in\mathbb{Z}/r\mathbb{Z}$ ; then for any $Q=[m]P\in G$ , the homomorphism property gives $\phi(Q)=[m]\phi(P)=[m\lambda]P=[\lambda]Q$ . (This is the statement $\operatorname{Hom}(\mathbb{Z}/r\mathbb{Z},\mathbb{Z}/r\mathbb{Z})\cong\mathbb{% Z}/r\mathbb{Z}$ : an endomorphism of a cyclic group is determined by, and equal to multiplication by, the image of a generator.) Applying the endomorphism relation to $P$ ,

[\lambda^{2}+\lambda+1]P=\mathcal{O}\quad\Longrightarrow\quad\lambda^{2}+% \lambda+1\equiv 0\pmod{r},

since $P$ has order $r$ . Consistently, this congruence is solvable exactly when $\mathbb{F}_{r}$ contains a primitive cube root of unity, i.e. when $r\equiv 1\pmod{3}$ (6.22 again)—the hypothesis of the statement. □

Remark 10.37 (How GLV halves the doubling count).

Computing $\phi$ costs a single field multiplication $x\mapsto\omega x$ , negligible against a group operation. One therefore decomposes a scalar $n\in\mathbb{Z}/r\mathbb{Z}$ as

[n]P=[n_{1}]P+[n_{2}]\,\phi(P),\qquad n\equiv n_{1}+n_{2}\lambda\pmod{r},

where $n_{1},n_{2}$ can each be taken only about $\tfrac{1}{2}\log_{2}r$ bits long—such a pair is found by lattice reduction in the lattice of pairs $(c_{1},c_{2})$ with $c_{1}+c_{2}\lambda\equiv 0\pmod{r}$ . The two half-length scalar multiplications are then run simultaneously, sharing their doublings (Straus–Shamir’s trick): one double-and-add loop of half the length, adding $P$ , $\phi(P)$ , or both according to the bits of $n_{1}$ and $n_{2}$ . The result costs about half the doublings of a single full-length double-and-add—a substantial saving, and its availability is one reason the Pasta curves take the form $y^{2}=x^{3}+b$ over primes $p\equiv 1\pmod{3}$ .

10.13 A worked toy example

The entire machinery now runs on a curve small enough for hand computation.

Example 10.38 (The curve $y^{2}=x^{3}+5$ over $\mathbb{F}_{11}$ ).

Take $p=11$ : then $p>3$ , and $4\cdot 0+27\cdot 5^{2}=675\equiv 4\not\equiv 0\pmod{11}$ , so the curve $E:y^{2}=x^{3}+5$ is nonsingular over $\mathbb{F}_{11}$ (10.5). Squaring the residues $0,1,\ldots,10$ yields the squares $\{0,1,3,4,5,9\}$ , so the nonzero quadratic residues are $\{1,3,4,5,9\}$ . Tabulating $f(x)=x^{3}+5\bmod 11$ and reading off the $y$ -values:

\begin{array}[]{c|c|c|l}x&x^{3}\bmod 11&f(x)=x^{3}+5&y\text{ with }y^{2}=f(x)% \\ \hline\cr 0&0&5&\pm 4\ (4^{2}=16\equiv 5)\\ 1&1&6&\text{none}\ (6\notin\mathrm{QR})\\ 2&8&2&\text{none}\\ 3&5&10&\text{none}\\ 4&9&3&\pm 5\ (5^{2}=25\equiv 3)\\ 5&4&9&\pm 3\\ 6&7&1&\pm 1\\ 7&2&7&\text{none}\\ 8&6&0&0\\ 9&3&8&\text{none}\\ 10&10&4&\pm 2\\ \end{array}

Counting: the five values $x\in\{0,4,5,6,10\}$ contribute two points each ( $10$ points), $x=8$ contributes the single point $(8,0)$ , and $\mathcal{O}$ completes the census:

\#E(\mathbb{F}_{11})=10+1+1=12.

Hasse’s bound checks out: $p+1=12$ , so the trace is $t=0$ , and indeed $\lvert t\rvert=0\leq 2\sqrt{11}\approx 6.63$ . The point $(8,0)$ has order $2$ , consistent with 10.25 and the even order $12$ ; here $-5\equiv 6$ is a cube, namely $8^{3}=512\equiv 6$ .

An addition. Let $P=(0,4)$ and $Q=(5,3)$ . Since $x_{1}=0\neq 5=x_{2}$ , the chord formula (12) applies:

\lambda=\frac{3-4}{5-0}=(-1)\cdot 5^{-1}=(-1)\cdot 9=-9\equiv 2\pmod{11},

using $5^{-1}=9$ (check: $5\cdot 9=45\equiv 1$ ). Then

x_{3}=\lambda^{2}-x_{1}-x_{2}=4-0-5=-1\equiv 10,\qquad y_{3}=\lambda(x_{1}-x_{% 3})-y_{1}=2\,(0-10)-4=-24\equiv 9,

so $P+Q=(10,9)$ . The result is on the curve: $9^{2}=81\equiv 4$ and $10^{3}+5=1005\equiv 4\pmod{11}$ , as required.

A doubling. Take $P=(0,4)$ . With $a=0$ , formula (13) gives

\lambda=\frac{3x_{1}^{2}+a}{2y_{1}}=\frac{0}{8}=0,\qquad x_{3}=\lambda^{2}-2x_% {1}=0,\qquad y_{3}=\lambda(x_{1}-x_{3})-y_{1}=-4\equiv 7,

so $[2](0,4)=(0,7)=-(0,4)$ . Hence $[3](0,4)=\mathcal{O}$ : the point $(0,4)$ has order $3$ .

The GLV endomorphism. Since $11\equiv 2\pmod{3}$ , the field $\mathbb{F}_{11}$ contains no primitive cube root of unity (6.22 requires $3\mid p-1$ ), so the GLV map is not available over $\mathbb{F}_{11}$ . The Pasta primes do satisfy $p\equiv q\equiv 1\pmod{3}$ , so GLV applies there. For a small GLV-friendly illustration take instead $p=13\equiv 1\pmod{3}$ , where $\omega=3$ satisfies $3^{2}+3+1=13\equiv 0\pmod{13}$ ; then $\phi(x,y)=(3x,y)$ is a nontrivial endomorphism of $y^{2}=x^{3}+b$ over $\mathbb{F}_{13}$ .

10.14 Pallas and Vesta assembled

Every property developed in this section was chosen with the closing example in mind. Here the pieces assemble.

Example 10.39 (The Pasta curves).

For the running example $y^{2}=x^{3}+5$ , with $p$ and $q$ the $255$ -bit primes of the section opening:

•

Pallas, over $\mathbb{F}_{p}$ : the order is $\#E_{p}(\mathbb{F}_{p})=q$ , a prime, so the group is cyclic, $E_{p}(\mathbb{F}_{p})\cong\mathbb{Z}/q\mathbb{Z}$ (3.34), with cofactor $h=1$ (10.24). The trace is $t=p+1-q$ , an $87$ -bit (negative) integer, far inside the Hasse bound $2\sqrt{p}\approx 2^{128}$ of 10.22.
•

Vesta, over $\mathbb{F}_{q}$ : the order is $\#E_{q}(\mathbb{F}_{q})=p$ , a prime, so $E_{q}(\mathbb{F}_{q})\cong\mathbb{Z}/p\mathbb{Z}$ , again with cofactor $1$ .
•

Both curves have $j=0$ (10.35), and both primes satisfy $p\equiv q\equiv 1\pmod{3}$ , so each curve admits the order- $3$ endomorphism $\phi(x,y)=(\omega x,y)$ of 10.36 and supports the GLV speedup of 10.37.
•

Both fields have two-adicity $32$ in the sense of 9.10: $2^{32}$ divides $p-1$ and $q-1$ , so each field carries the multiplicative subgroups of order $2^{32}$ promised by 10.28—the evaluation domains of the fast polynomial arithmetic of 9.
•

The cycle property $\#E_{p}(\mathbb{F}_{p})=q$ and $\#E_{q}(\mathbb{F}_{q})=p$ means the scalar field of each curve is the base field of the other (10.27): the base field of Pallas is $\mathbb{F}_{p}$ and its scalar field is $\mathbb{F}_{q}$ , matching the base field of Vesta, and symmetrically. This is exactly what lets recursive proof systems chain proofs across the two curves without expensive non-native field arithmetic (10.28). The cycle is a deployed fact: the pasta_curves crate wires the scalar field of Pallas to be $\mathbb{F}_{q}$ and that of Vesta to be $\mathbb{F}_{p}$ , as specified in §5.4.9.6 of the Zcash protocol specification.

The discrete logarithm problem in $E_{p}(\mathbb{F}_{p})$ and $E_{q}(\mathbb{F}_{q})$ is believed to require about $2^{127}$ operations— $\sqrt{r}$ for the $255$ -bit orders $r\approx 2^{254}$ (10.30)—with no faster attack known (10.31), just below the $128$ -bit security level targeted by Halo 2 and Zcash Orchard.

The cheque from the section’s opening is hereby cashed. The demand was a roughly $255$ -bit group for which no attack faster than the square-root bound is known, and each Pasta curve supplies one: a cyclic group of prime $255$ -bit order (10.22 and 3.34), carrying a fast forward map (10.21, accelerated by 10.37) whose inversion—the ECDLP—resists everything known except the generic $O(\sqrt{r})$ attacks of 10.30. Where $\mathbb{F}_{p}^{\times}$ needs thousands of bits to outrun index calculus, the curve group needs $255$ ; and the two groups even interlock as a cycle, each one’s scalars living in the other’s coordinates. Later volumes build on precisely this pair.