I Math Guide: Mathematical foundations for Halo 2 and Zcash Orchard 6 Finite fields 8 Linear algebra over a field

7 Number theory for cryptography

An implementation that transmits a point of an elliptic curve—a pair $(x,y)$ of field elements satisfying an equation $y^{2}=x^{3}+ax+b$ , as constructed in 10—need not send both coordinates. For a given $x$ the equation determines $y^{2}$ exactly, hence determines $y$ up to sign, so wire formats send $x$ together with a single bit selecting one of the two candidates, and the transmission halves in size. The receiver is then left with two number-theoretic tasks: decide whether $x^{3}+ax+b$ is a square modulo $p$ at all—if not, no point has this $x$ -coordinate—and, if it is, compute a square root of it. Both tasks must run in the time of a few modular exponentiations, on numbers hundreds of bits long. The same constructions make a complementary demand in the opposite direction: they publish powers $g^{x}$ of a known group element while the exponent $x$ is a secret key, so exponentiation must be easy to perform and yet infeasible to invert. This section assembles the classical number theory behind both demands: the totient and the Chinese Remainder Theorem, Fermat’s little theorem and Euler’s theorem in their role as workhorses of modular exponentiation, multiplicative orders and primitive roots, quadratic residues with the Euler criterion, square-root extraction modulo a prime, and finally the discrete logarithm problem together with the reason prime group order is so important for cryptographic hardness.

Throughout, $n$ and $m$ denote positive integers and $p$ denotes a prime. The section builds directly on the arithmetic of 2, the group theory of 3, and the cyclicity theorem of 6; several statements proved there reappear here, restated in the arithmetic language in which cryptography uses them, with proofs reduced to citations.

7.1 Euler’s totient function and the Chinese Remainder Theorem

Recall from 2 that a class $[a]_{n}\in\mathbb{Z}/n\mathbb{Z}$ is a unit if and only if $\gcd(a,n)=1$ (Theorem 2.24), that the units form a finite abelian group $(\mathbb{Z}/n\mathbb{Z})^{\times}$ (Proposition 3.8), and that Euler’s totient $\varphi(n)$ counts them: $\varphi(n)=\lvert(\mathbb{Z}/n\mathbb{Z})^{\times}\rvert$ (Definition 2.26). In particular $\varphi(p)=p-1$ for a prime $p$ (Example 2.27), so $\mathbb{F}_{p}^{\times}$ has order $p-1$ . These counts govern everything that follows: the totient is the exponent in Euler’s theorem, the order of the group whose cyclic structure the next subsections exploit, and—through the orders of elliptic-curve groups—a quantity that the parameter choices of Halo 2 and Orchard are built around. What 2 did not provide is a way to compute $\varphi(n)$ beyond direct enumeration. Two facts close the gap: the totient’s value on prime powers, and its behaviour on coprime factors.

Proposition 7.1 (Totient of a prime power).

For a prime $p$ and an integer $k\geq 1$ ,

\varphi(p^{k})=p^{k}-p^{k-1}=p^{k}\Bigl{(}1-\frac{1}{p}\Bigr{)}.

Proof.

Among $1,\dots,p^{k}$ , we claim the integers not coprime to $p^{k}$ are exactly the multiples of $p$ . If $p\mid a$ then $p\mid\gcd(a,p^{k})$ , so the gcd exceeds $1$ . Conversely, if $g=\gcd(a,p^{k})>1$ , then $g$ has a prime factor $\ell$ ; from $\ell\mid g\mid p^{k}$ and Euclid’s lemma for primes (Lemma 2.17) we get $\ell=p$ , and $\ell\mid g\mid a$ gives $p\mid a$ . The multiples of $p$ in the range are $p,2p,\dots,p^{k-1}\cdot p$ , of which there are $p^{k-1}$ ; subtracting them from the $p^{k}$ integers in the range leaves $\varphi(p^{k})=p^{k}-p^{k-1}$ . □

The behaviour on coprime factors is a consequence of a structural theorem that will be used again, in a quite different role, at the end of the section: a residue modulo a product of two coprime moduli carries exactly the same information as a pair of residues, one modulo each factor. The natural home for the statement is the language of rings (4): recall the product ring $R\times S$ with componentwise operations (Example 4.5), and call a bijective ring homomorphism (Definition 4.21) a ring isomorphism, mirroring Definition 3.41 for groups.

Theorem 7.2 (Chinese Remainder Theorem).

If $\gcd(m,n)=1$ , then the map

\mathbb{Z}/mn\mathbb{Z}\longrightarrow\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n% \mathbb{Z},\qquad[a]_{mn}\longmapsto\bigl{(}[a]_{m},\,[a]_{n}\bigr{)}

is a ring isomorphism. It restricts to a group isomorphism

(\mathbb{Z}/mn\mathbb{Z})^{\times}\;\cong\;(\mathbb{Z}/m\mathbb{Z})^{\times}% \times(\mathbb{Z}/n\mathbb{Z})^{\times}.

Proof.

The map is well defined: if $[a]_{mn}=[a^{\prime}]_{mn}$ then $mn\mid a-a^{\prime}$ , hence $m\mid a-a^{\prime}$ and $n\mid a-a^{\prime}$ , so the two components agree. It is a ring homomorphism because each component is: reduction modulo $m$ (and modulo $n$ ) sends sums to sums, products to products, and $1$ to $1$ (Theorem 4.6), and the product ring’s operations are componentwise.

For injectivity it suffices, since the map is in particular a homomorphism of additive groups, to check that the kernel is trivial (Proposition 3.40). Suppose $[a]_{m}=[0]_{m}$ and $[a]_{n}=[0]_{n}$ , that is, $m\mid a$ and $n\mid a$ . Since $\gcd(m,n)=1$ , Euclid’s lemma (Proposition 2.15(2)) gives $mn\mid a$ , i.e. $[a]_{mn}=[0]_{mn}$ .

Both sides have exactly $m n$ elements (Theorem 4.6 for each factor), and an injective map between finite sets of equal size is bijective: the $m n$ distinct inputs have $m n$ distinct images, which must exhaust the codomain. Hence the map is a ring isomorphism.

For the multiplicative statement, a ring isomorphism $\phi$ matches units with units: if $uv=1$ then $\phi(u)\phi(v)=\phi(1)=1$ , and the same applies to $\phi^{-1}$ . The units of the product ring are exactly the pairs of units, $(u,v)^{-1}=(u^{-1},v^{-1})$ existing precisely when both components are invertible. Restricting $\phi$ to unit groups therefore gives a bijection $(\mathbb{Z}/mn\mathbb{Z})^{\times}\to(\mathbb{Z}/m\mathbb{Z})^{\times}\times(% \mathbb{Z}/n\mathbb{Z})^{\times}$ that respects multiplication: a group isomorphism. □

Corollary 7.3 (Multiplicativity and the product formula).

If $\gcd(m,n)=1$ then $\varphi(mn)=\varphi(m)\,\varphi(n)$ . Hence if $n=\prod_{i}p_{i}^{k_{i}}$ is the prime factorisation of $n$ , then

\varphi(n)=\prod_{i}\bigl{(}p_{i}^{k_{i}}-p_{i}^{k_{i}-1}\bigr{)}=n\prod_{p% \mid n}\Bigl{(}1-\frac{1}{p}\Bigr{)},

the last product running over the distinct primes dividing $n$ .

Proof.

The unit-group isomorphism of Theorem 7.2 is in particular a bijection, and the cardinality of a product of two sets is the product of the cardinalities, so $\varphi(mn)=\varphi(m)\,\varphi(n)$ .

For the product formula, the prime powers $p_{i}^{k_{i}}$ are pairwise coprime: a common divisor exceeding $1$ of two of them would have a prime factor dividing both, which by Euclid’s lemma for primes (Lemma 2.17) would equal both $p_{i}$ and $p_{j}$ . Moreover each $p_{i}^{k_{i}}$ is coprime to the product of the others, by repeated application of Proposition 2.15(3). Induction on the number of factors therefore extends multiplicativity to $\varphi(n)=\prod_{i}\varphi\bigl{(}p_{i}^{k_{i}}\bigr{)}$ , and Proposition 7.1 evaluates each factor:

\varphi(n)=\prod_{i}\bigl{(}p_{i}^{k_{i}}-p_{i}^{k_{i}-1}\bigr{)}=\prod_{i}p_{% i}^{k_{i}}\Bigl{(}1-\frac{1}{p_{i}}\Bigr{)}=n\prod_{p\mid n}\Bigl{(}1-\frac{1}% {p}\Bigr{)}.\qed

As a sanity check, the product formula gives $\varphi(12)=12\bigl{(}1-\tfrac{1}{2}\bigr{)}\bigl{(}1-\tfrac{1}{3}\bigr{)}=4$ , agreeing with the direct enumeration $\{1,5,7,11\}$ of Example 2.27. Together with Gauss’s divisor-sum identity $\sum_{d\mid n}\varphi(d)=n$ , proved as Lemma 6.16, this completes the totient’s basic theory.

7.2 Fermat’s little theorem and Euler’s theorem

The congruences of this subsection were proved once, as Corollary 3.32, where they fell out of Lagrange’s theorem in three lines. We restate them here in the arithmetic form in which cryptography uses them; the proofs are citations, not repetitions.

Theorem 7.4 (Euler’s theorem).

If $\gcd(a,n)=1$ , then

a^{\varphi(n)}\equiv 1\pmod{n}.

Proof.

The hypothesis says that $[a]_{n}$ is a unit (Theorem 2.24), i.e. an element of the finite group $(\mathbb{Z}/n\mathbb{Z})^{\times}$ , whose order is $\varphi(n)$ (Definition 2.26). By Corollary 3.31—every element $g$ of a finite group of order $N$ satisfies $g^{N}=e$ , a consequence of Lagrange’s theorem—we get $[a]_{n}^{\varphi(n)}=[1]_{n}$ , which is the stated congruence. This is Corollary 3.32 verbatim. □

Corollary 7.5 (Fermat’s little theorem).

Let $p$ be prime. If $p\nmid a$ , then $a^{p-1}\equiv 1\pmod{p}$ . Moreover $a^{p}\equiv a\pmod{p}$ for every integer $a$ .

Proof.

For $p\nmid a$ we have $\gcd(a,p)=1$ , so Theorem 7.4 with $n=p$ and $\varphi(p)=p-1$ (Example 2.27) gives the first congruence; multiplying it by $a$ gives $a^{p}\equiv a\pmod{p}$ . When $p\mid a$ both $a^{p}$ and $a$ are congruent to $0$ , so the second congruence holds for all $a$ . □

Remark 7.6 (Cryptographic use of Euler and Fermat).

Euler’s theorem underlies RSA: if $ed\equiv 1\pmod{\varphi(n)}$ , say $ed=1+k\varphi(n)$ , then

(a^{e})^{d}=a^{1+k\varphi(n)}=a\cdot\bigl{(}a^{\varphi(n)}\bigr{)}^{k}\equiv a% \pmod{n}

whenever $\gcd(a,n)=1$ : raising to the $e$ -th power is undone by raising to the $d$ -th, which is what makes one exponent a public encryption key and the other its private inverse. The elliptic-curve cryptography of Orchard instead exploits Fermat’s little theorem in the field $\mathbb{F}_{p}$ : every nonzero $x$ satisfies $x^{p-1}=1$ , so inversion is computable as $x^{-1}=x^{p-2}$ (6.4), and Fermat is the engine of the Euler criterion for square roots developed below.

7.3 Multiplicative order and primitive roots

Definition 7.7 (Multiplicative order).

Let $\gcd(a,n)=1$ . The multiplicative order of $a$ modulo $n$ , written $\operatorname{ord}_{n}(a)$ , is the least positive integer $k$ with $a^{k}\equiv 1\pmod{n}$ . Such a $k$ exists because $a^{\varphi(n)}\equiv 1$ by Theorem 7.4.

The quantity $\operatorname{ord}_{n}(a)$ is exactly the order of $[a]_{n}$ as an element of the group $(\mathbb{Z}/n\mathbb{Z})^{\times}$ , so the order theory of 3 applies verbatim: $a^{m}\equiv 1\pmod{n}$ if and only if $\operatorname{ord}_{n}(a)\mid m$ (Proposition 3.12(1))—in particular $\operatorname{ord}_{n}(a)\mid\varphi(n)$ , by Euler’s theorem—and

\operatorname{ord}_{n}\bigl{(}a^{j}\bigr{)}=\frac{\operatorname{ord}_{n}(a)}{% \gcd\bigl{(}j,\operatorname{ord}_{n}(a)\bigr{)}}

(Corollary 3.23).

Definition 7.8 (Primitive root).

A primitive root modulo $n$ is an element $g$ with $\operatorname{ord}_{n}(g)=\varphi(n)$ ; equivalently, $g$ generates $(\mathbb{Z}/n\mathbb{Z})^{\times}$ as a cyclic group, so that $\{g^{0},g^{1},\dots,g^{\varphi(n)-1}\}$ lists all the units.

Primitive roots need not exist for every modulus. The unit group $(\mathbb{Z}/8\mathbb{Z})^{\times}=\{1,3,5,7\}$ has order $\varphi(8)=4$ , yet every one of its elements squares to $1$ (Example 3.22): the element orders are $1$ for the identity and $2$ for each of $3$ , $5$ , $7$ , so no element has order $4$ and no primitive root modulo $8$ exists. Indeed the unit group is a copy of the Klein four-group of Example 3.10: every element is its own inverse, and the product of two distinct non-identity elements $a$ and $b$ is neither $e$ (which would force $b=a^{-1}=a$ ) nor $a$ nor $b$ (which would force $b=e$ or $a=e$ ), so it is the third. The decisive case for cryptography is $n=p$ prime, where the multiplicative group is always cyclic.

Corollary 7.9 ( $\mathbb{F}_{p}^{\times}$ is cyclic).

For every prime $p$ , the group $\mathbb{F}_{p}^{\times}=(\mathbb{Z}/p\mathbb{Z})^{\times}$ is cyclic of order $p-1$ . In particular primitive roots modulo $p$ exist, and there are exactly $\varphi(p-1)$ of them; Example 6.21 exhibits the two primitive roots $3$ and $5$ of $\mathbb{F}_{7}$ .

Proof.

The group $\mathbb{F}_{p}^{\times}$ is a finite subgroup, of order $p-1$ , of the multiplicative group of the field $\mathbb{F}_{p}$ , hence cyclic by Theorem 6.17. A generator $g$ has order $p-1$ , and the powers $g^{k}$ that again generate are those with $\gcd(k,p-1)=1$ (Corollary 3.23), numbering $\varphi(p-1)$ . □

Remark 7.10 (Cyclicity and prime-order groups).

Cyclicity is why the prime-order groups of elliptic-curve cryptography behave exactly like $\mathbb{Z}/q\mathbb{Z}$ under addition once a generator is fixed: a cyclic group of order $q$ is isomorphic to $(\mathbb{Z}/q\mathbb{Z},+)$ via $g^{k}\leftrightarrow k$ (Theorem 3.43). For completeness we record, without proof and without needing it later, the full classification: primitive roots modulo $n$ exist exactly when $n\in\{1,2,4,p^{k},2p^{k}\}$ for an odd prime $p$ .

7.4 Quadratic residues and the Euler criterion

We turn to squares modulo a prime. They control whether a curve point with a given $x$ -coordinate exists—the first of the two tasks posed at the head of the section—and they are the objects from which square roots in $\mathbb{F}_{p}$ will be extracted.

Definition 7.11 (Quadratic residue).

Let $p$ be an odd prime and $a$ an integer with $p\nmid a$ . We say $a$ is a quadratic residue modulo $p$ (a QR) if the congruence $x^{2}\equiv a\pmod{p}$ has a solution, and a quadratic non-residue (a QNR) otherwise.

Proposition 7.12 (Exactly half are residues).

For an odd prime $p$ , exactly $\tfrac{p-1}{2}$ of the nonzero residues modulo $p$ are quadratic residues and $\tfrac{p-1}{2}$ are non-residues. The squaring map $x\mapsto x^{2}$ is exactly two-to-one on $\mathbb{F}_{p}^{\times}$ .

Proof.

Consider $\sigma\colon\mathbb{F}_{p}^{\times}\to\mathbb{F}_{p}^{\times}$ , $\sigma(x)=x^{2}$ ; its image is exactly the set of quadratic residues. For $x,y\in\mathbb{F}_{p}^{\times}$ ,

\sigma(x)=\sigma(y)\iff x^{2}-y^{2}=0\iff(x-y)(x+y)=0\iff y=\pm x,

the middle equivalence because a field has no zero divisors (Proposition 4.28). Since $p$ is odd, $x\neq-x$ for $x\neq 0$ (otherwise $2x=0$ with $2$ and $x$ nonzero), so every fibre of $\sigma$ over its image has exactly two elements. Counting, $\lvert\operatorname{im}\sigma\rvert=\tfrac{p-1}{2}$ , and the complement—the non-residues—has the same size. □

Theorem 7.13 (Euler’s criterion).

Let $p$ be an odd prime and $p\nmid a$ . Then

a^{\frac{p-1}{2}}\equiv\begin{cases}\phantom{-}1\pmod{p}&\text{if }a\text{ is % a quadratic residue,}\\[2.0pt] -1\pmod{p}&\text{if }a\text{ is a quadratic non-residue.}\end{cases}

Proof.

First, the value is always $\pm 1$ . Fermat’s little theorem (Corollary 7.5) gives $\bigl{(}a^{(p-1)/2}\bigr{)}^{2}=a^{p-1}\equiv 1$ , and the only square roots of $1$ modulo a prime are $\pm 1$ : from $x^{2}\equiv 1$ we get $p\mid(x-1)(x+1)$ , so $p\mid x-1$ or $p\mid x+1$ by Euclid’s lemma for primes (Lemma 2.17), i.e. $x\equiv\pm 1$ . Hence $a^{(p-1)/2}\equiv\pm 1\pmod{p}$ .

If $a$ is a residue, say $a\equiv x^{2}$ with $p\nmid x$ , then $a^{(p-1)/2}\equiv x^{p-1}\equiv 1$ , again by Fermat. Thus every one of the $\tfrac{p-1}{2}$ quadratic residues (Proposition 7.12) is a root of the polynomial $t^{(p-1)/2}-1$ over $\mathbb{F}_{p}$ . That polynomial has degree $\tfrac{p-1}{2}$ , so it has at most $\tfrac{p-1}{2}$ roots (Theorem 5.18); the residues therefore account for all of them. A non-residue $a$ is consequently not a root, yet still satisfies $a^{(p-1)/2}\equiv\pm 1$ ; the remaining possibility is $a^{(p-1)/2}\equiv-1$ . □

The standard notation for quadratic-residue status is the Legendre symbol.

Definition 7.14 (Legendre symbol).

For an odd prime $p$ and an integer $a$ , the Legendre symbol is

\left(\frac{a}{p}\right)=\begin{cases}\phantom{-}0&\text{if }p\mid a,\\ \phantom{-}1&\text{if }a\text{ is a quadratic residue modulo }p,\\ -1&\text{if }a\text{ is a quadratic non-residue modulo }p.\end{cases}

Euler’s criterion (Theorem 7.13) then reads, uniformly,

\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod{p},

so the symbol is computable by a single modular exponentiation—an $O(\log p)$ affair by square-and-multiply (6.2). The criterion also shows that the symbol is completely multiplicative in $a$ :

\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right),% \qquad\text{since}\qquad(ab)^{\frac{p-1}{2}}=a^{\frac{p-1}{2}}\,b^{\frac{p-1}{% 2}}.

Both observations carry weight in the worked example that follows, which verifies a constant deployed in Orchard.

Example 7.15 ( $13$ is a non-square in both Pasta fields).

The Pasta hash-to-curve construction used by Orchard—a procedure, taken up in later volumes, that maps arbitrary byte strings to curve points and requires a fixed non-square constant in the base field—fixes $Z=-13$ as a verifiably non-square constant in both base fields. Let $p$ and $q$ be the Pasta primes of 10; both satisfy $p\equiv q\equiv 1\pmod{4}$ . We verify the non-squareness here, working modulo $p$ ; the computation modulo $q$ is identical.

First, $-1$ is a square modulo any prime $\equiv 1\pmod{4}$ : the exponent $\tfrac{p-1}{2}$ is even, so Euler’s criterion gives

\left(\frac{-1}{p}\right)\equiv(-1)^{\frac{p-1}{2}}=1.

By complete multiplicativity,

\left(\frac{-13}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{13}{p}\right)=% \left(\frac{13}{p}\right),

so $-13$ is a non-square precisely when $13$ is. Whether $13$ is a square is settled by one Euler-criterion exponentiation in each field, a computation any computer-algebra system reproduces in milliseconds:

13^{\frac{p-1}{2}}\equiv p-1\equiv-1\pmod{p},\qquad 13^{\frac{q-1}{2}}\equiv q% -1\equiv-1\pmod{q},

whence $\left(\frac{13}{p}\right)=\left(\frac{13}{q}\right)=-1$ . Thus $13$ , and with it $Z=-13$ , is a quadratic non-residue modulo both Pasta primes, exactly as the hash-to-curve design requires.

Example 7.16 ( $5$ is a non-square in the Pallas base field).

The same one-line test settles a second constant on which later volumes lean, this time in the curve equation itself. Pallas is the curve $y^{2}=x^{3}+5$ over $\mathbb{F}_{p}$ (10), and the arithmetic circuits of Halo 2 encode its point at infinity as the coordinate pair $(0,0)$ (10.13). The encoding is unambiguous only if no genuine point has $x$ -coordinate $0$ , i.e. only if $y^{2}=5$ has no solution in $\mathbb{F}_{p}$ : the question is whether $5$ is a square in the base field $\mathbb{F}_{p}$ of Pallas, not in its scalar field $\mathbb{F}_{q}$ . Euler’s criterion decides it in one exponentiation:

5^{\frac{p-1}{2}}\equiv p-1\equiv-1\pmod{p},

so $\left(\frac{5}{p}\right)=-1$ . The constant $5$ is a quadratic non-residue modulo the Pallas base-field prime, and no point of Pallas has $x=0$ . (The same computation modulo $q$ gives $5^{(q-1)/2}\equiv-1\pmod{q}$ , so Vesta has no such point either.) That no point has $y=0$ is a different fact— $-5$ is not a cube in $\mathbb{F}_{p}$ —which 10.26 reads off from the oddness of the group order; the two together are the hypotheses of 10.14.

7.5 Square roots modulo a prime

Deciding that $a$ is a residue is one matter; producing an $x$ with $x^{2}\equiv a$ is another, and the point decompression of the section’s opening needs the production, not just the decision: the receiver must reconstruct the coordinate $y$ from $y^{2}$ . How hard this is depends on $p\bmod 4$ .

Proposition 7.17 (The $p\equiv 3\pmod{4}$ shortcut).

Let $p\equiv 3\pmod{4}$ be prime and let $a$ be a quadratic residue modulo $p$ with $p\nmid a$ . Then

x\equiv a^{\frac{p+1}{4}}\pmod{p}

is a square root of $a$ , and the two square roots of $a$ are $\pm x$ .

Proof.

Since $p\equiv 3\pmod{4}$ , the quantity $\tfrac{p+1}{4}$ is a positive integer. Compute

x^{2}=a^{\frac{p+1}{2}}=a^{\frac{p-1}{2}}\cdot a\equiv\left(\frac{a}{p}\right)% \cdot a=a\pmod{p},

using Euler’s criterion (Theorem 7.13) and the hypothesis that $a$ is a residue, so $\left(\frac{a}{p}\right)=1$ . The roots come in the pair $\pm x$ by the two-to-one property of squaring (Proposition 7.12). □

Remark 7.18 (Cost and the Pasta primes).

The single-exponentiation shortcut requires $p\equiv 3\pmod{4}$ , which is one reason cryptographers often favour such primes. For $p\equiv 5\pmod{8}$ a closed-form variant (Atkin’s formula) still exists. In general the cost of square-root extraction grows with the $2$ -adic valuation $s$ of $p-1$ : writing $p-1=2^{s}d$ with $d$ odd, the Tonelli–Shanks algorithm below performs up to $s$ corrective iterations. The Pasta primes have $s=32$ , a value chosen deliberately for FFT-friendliness (9.10), so their implementations use Tonelli–Shanks.

When $p\equiv 1\pmod{4}$ one writes $p-1=2^{s}d$ with $d$ odd and $s\geq 2$ . The algorithm operates inside the subgroup of $\mathbb{F}_{p}^{\times}$ of order $2^{s}$ —the unique such subgroup, since $\mathbb{F}_{p}^{\times}$ is cyclic (Corollary 7.9 and Theorem 3.24(3))—where the obstruction to the naive exponentiation trick lives, and clears that obstruction one power of two at a time.

Theorem 7.19 (Tonelli–Shanks).

Let $p$ be an odd prime, $p-1=2^{s}d$ with $d$ odd, and let $a$ be a quadratic residue with $p\nmid a$ . Given any quadratic non-residue $z$ modulo $p$ , one can compute a square root of $a$ modulo $p$ using $O(s^{2}+\log p)$ modular multiplications.

Proof.

Write $H\leq\mathbb{F}_{p}^{\times}$ for the unique cyclic subgroup of order $2^{s}$ . Set $c=z^{d}$ . We claim $c$ generates $H$ . By Euler’s criterion (Theorem 7.13) $z^{(p-1)/2}\equiv-1$ , so

c^{\,2^{s-1}}=z^{\,2^{s-1}d}=z^{\frac{p-1}{2}}\equiv-1\neq 1,\qquad c^{\,2^{s}% }=z^{\,p-1}\equiv 1

by Fermat (Corollary 7.5); hence $\operatorname{ord}_{p}(c)$ divides $2^{s}$ but not $2^{s-1}$ , forcing $\operatorname{ord}_{p}(c)=2^{s}$ and $\langle c\rangle=H$ .

Initialise

x=a^{\frac{d+1}{2}},\qquad t=a^{d},\qquad m=s

(the exponent $\tfrac{d+1}{2}$ is an integer because $d$ is odd). We maintain three invariants:

1.

$x^{2}=a\,t$ ;
2.

the current $c$ has order exactly $2^{m}$ ;
3.

the order of $t$ divides $2^{m-1}$ .

Initially (1) holds since $x^{2}=a^{d+1}=a\cdot a^{d}$ ; (2) was just proved; and (3) holds because $t^{\,2^{s-1}}=a^{(p-1)/2}\equiv 1$ by Euler’s criterion (Theorem 7.13), $a$ being a residue.

Now iterate. If $t=1$ , then $x^{2}=a$ by (1) and we are done. Otherwise let $2^{i}=\operatorname{ord}_{p}(t)$ , found as the least $i\geq 1$ with $t^{\,2^{i}}=1$ by repeatedly squaring $t$ ; invariant (3) gives $1\leq i\leq m-1$ . Set

b=c^{\,2^{m-i-1}},

and update

x\leftarrow xb,\qquad t\leftarrow tb^{2},\qquad c\leftarrow b^{2},\qquad m% \leftarrow i.

The invariants survive. For (1), $(xb)^{2}=x^{2}b^{2}=a\,t\,b^{2}$ , which is $a$ times the new $t$ . For (2), the old $c$ has order $2^{m}$ , so $\operatorname{ord}_{p}(b)=2^{m}/\gcd\bigl{(}2^{m},2^{m-i-1}\bigr{)}=2^{i+1}$ (Corollary 3.23), and the new $c=b^{2}$ has order $2^{i}$ —exactly $2$ to the new $m$ . For (3), both the old $t$ and $b^{2}$ have order exactly $2^{i}$ , so $t^{\,2^{i-1}}$ and $(b^{2})^{\,2^{i-1}}$ each have order $2$ ; the only element of order $2$ in $\mathbb{F}_{p}^{\times}$ is $-1$ , because the square roots of $1$ are $\pm 1$ (as in the proof of Theorem 7.13); hence

\bigl{(}t\,b^{2}\bigr{)}^{2^{i-1}}=t^{\,2^{i-1}}\bigl{(}b^{2}\bigr{)}^{2^{i-1}% }=(-1)(-1)=1,

so the new $t$ has order dividing $2^{i-1}$ , which is $2^{m-1}$ for the new $m$ .

Each iteration strictly decreases $m$ , from $s$ through a descending chain of nonnegative integers, so after at most $s$ iterations the order of $t$ reaches $2^{0}=1$ , i.e. $t=1$ , and $x$ is the desired root. For the cost: locating $i$ and computing $b$ each take at most $m\leq s$ squarings, so the loop costs $O(s)$ multiplications per iteration and $O(s^{2})$ in total; the three initial exponentiations, with exponents smaller than $p$ , cost $O(\log p)$ multiplications each by square-and-multiply (6.2). □

The one ingredient the theorem presupposes is a quadratic non-residue $z$ , and here—for the only time in this section—randomness enters. A uniformly random element of $\mathbb{F}_{p}^{\times}$ is a non-residue with probability exactly $\tfrac{1}{2}$ , since precisely half the elements qualify (Proposition 7.12), and each candidate is checked by one Euler-criterion exponentiation (Definition 7.14), i.e. $O(\log p)$ modular multiplications. A handful of random trials therefore finds $z$ almost immediately, and implementations simply hard-code one non-residue per field, verified once—as the constant $Z=-13$ of Example 7.15 is. No deterministic polynomial-time method for finding a non-residue is invoked anywhere in this volume.

Remark 7.20 (Which root, and detecting failure).

In every case the square roots of a residue come in a pair $\pm x$ (Proposition 7.12), so a canonical root must be pinned down by a convention—for instance “choose the root whose least nonnegative representative is even”, as elliptic-curve point encodings do; the compressed point’s extra bit selects between the two. If $a$ is not a residue, both algorithms above detect the failure, in different ways. The shortcut of Proposition 7.17 still outputs a candidate $a^{(p+1)/4}$ , and that candidate fails the final check $x^{2}\equiv a$ —one squaring suffices to detect failure. The variable-time Tonelli–Shanks algorithm just given cannot complete its update on a non-residue: Euler’s criterion gives $a^{(p-1)/2}\equiv-1$ , so $t=a^{d}$ satisfies $t^{2^{s-1}}\equiv-1$ and has order exactly $2^{s}$ , and already the first search for the least $i\geq 1$ with $t^{2^{i}}=1$ returns $i=m$ , which invariant (3) of the proof of Theorem 7.19 forbids and for which the update exponent $2^{m-i-1}$ is undefined. This variant can report “not a residue” the moment $i=m$ occurs; equivalently it may verify $a^{(p-1)/2}\equiv 1$ up front, at the same $O(\log p)$ cost as the initial exponentiations.

7.6 The discrete logarithm problem

The second demand of the section’s opening—exponentiation easy forward, infeasible backward—now takes centre stage. We phrase it for a generic cyclic group, written multiplicatively, because in Orchard the group in question is the group of points of an elliptic curve, written additively, of large prime order; every statement below transfers by renaming the operation.

Definition 7.21 (Discrete logarithm problem).

Let $G=\langle g\rangle$ be a finite cyclic group of order $N$ with generator $g$ . Given $h\in G$ , the discrete logarithm of $h$ to base $g$ , written $\log_{g}h$ , is the unique residue $x\in\mathbb{Z}/N\mathbb{Z}$ with $g^{x}=h$ . The discrete logarithm problem (DLP) is to compute $x$ from $(G,g,h)$ .

Existence and uniqueness of $\log_{g}h$ are the content of the classification of cyclic groups: the map $x\mapsto g^{x}$ is a group isomorphism $(\mathbb{Z}/N\mathbb{Z},+)\xrightarrow{\;\sim\;}G$ (Theorem 3.43, whose map $\bar{\phi}$ this is), so it has a well-defined inverse, and $\log_{g}$ is that inverse. The two directions could not differ more in cost. Computing $g^{x}$ from $x$ takes $O(\log N)$ group operations by square-and-multiply (6.2); computing $x$ from $g^{x}$ is the DLP, for which no efficient algorithm is known in well-chosen groups. This asymmetry—a bijection cheap in one direction and expensive in the other—is the one-wayness on which elliptic-curve cryptography rests.

Remark 7.22 (Generic complexity and group choice).

Two generic algorithms solve the DLP in any group of order $N$ , using nothing but the group operation. Baby-step giant-step is deterministic: set $m=\lceil\sqrt{N}\rceil$ and write the unknown as $x=im+j$ with $0\leq i,j<m$ ; tabulate the “baby steps” $g^{j}$ for all $j$ , then walk the “giant steps” $h(g^{-m})^{i}$ for $i=0,1,2,\dots$ until one equals a tabulated $g^{j}$ , at which point $hg^{-im}=g^{j}$ gives $x=im+j$ . Both the table and the walk are $O(\sqrt{N})$ , so the cost is $O(\sqrt{N})$ time and space. Pollard’s rho (not developed here) is a randomised alternative with the same $O(\sqrt{N})$ expected running time—on a heuristic analysis, made explicit in 10—but only $O(1)$ space, and is what attackers would run in practice. In the other direction, Shoup’s theorem shows that $\Omega(\sqrt{N})$ group operations are necessary for any generic algorithm when $N$ is prime, so for generic attacks the square-root cost is exact. Reaching a $\lambda$ -bit security level—no attack cheaper than $2^{\lambda}$ operations—therefore requires $N\approx 2^{2\lambda}$ . This is why the Pallas and Vesta scalar fields have prime order roughly $255$ bits long, targeting roughly $128$ -bit security (10). The qualifier generic matters: in $(\mathbb{Z}/p\mathbb{Z})^{\times}$ sub-exponential index-calculus attacks exist, which exploit the ring structure of the integers behind the group, and this is why elliptic-curve groups—where no such attack is known—permit much smaller parameters than multiplicative groups of comparable security.

The next theorem makes the phrase “well-chosen” precise: if the group order $N$ is composite with small prime factors, the DLP falls apart into small pieces, and the Chinese Remainder Theorem—proved in this section for a purely arithmetic purpose—reassembles the pieces into the secret.

Theorem 7.23 (Pohlig–Hellman reduction).

Let $G=\langle g\rangle$ be cyclic of order $N=\prod_{i=1}^{r}q_{i}^{e_{i}}$ , the $q_{i}$ distinct primes. The discrete logarithm in $G$ is computable by solving discrete logarithms in subgroups of prime order $q_{i}$ — $e_{i}$ of them for each $i$ —and combining the answers with the Chinese Remainder Theorem, at a total cost of

O\Bigl{(}\,\sum_{i=1}^{r}e_{i}\bigl{(}\log N+\sqrt{q_{i}}\,\bigr{)}\Bigr{)}

group operations. When $N$ has a large prime factor $q_{\max}$ the $\sqrt{q_{\max}}$ term dominates; when $N$ is smooth—a product of primes bounded polynomially in $\log N$ —every term is polynomial in $\log N$ and the DLP is easy. Corollary 7.24 draws the design consequence.

Proof.

Let $h=g^{x}$ with $x$ the unknown. The reduction has two stages.

Stage (a): splitting across coprime factors. For each $i$ set $N_{i}=N/q_{i}^{e_{i}}$ and project:

g_{i}=g^{N_{i}},\qquad h_{i}=h^{N_{i}}.

By Corollary 3.23, $\operatorname{ord}(g_{i})=N/\gcd(N,N_{i})=N/N_{i}=q_{i}^{e_{i}}$ , so $g_{i}$ generates the unique subgroup of $G$ of order $q_{i}^{e_{i}}$ (Theorem 3.24(3)). Moreover $h_{i}=g^{xN_{i}}=g_{i}^{\,x}$ , and since $g_{i}$ has order $q_{i}^{e_{i}}$ , the exponent matters only modulo $q_{i}^{e_{i}}$ (Proposition 3.12(2)): writing $x_{i}=x\bmod q_{i}^{e_{i}}$ ,

\log_{g_{i}}h_{i}=x_{i}.

Solving the $r$ smaller DLPs yields $x\bmod q_{i}^{e_{i}}$ for every $i$ ; since the prime powers $q_{i}^{e_{i}}$ are pairwise coprime, the Chinese Remainder Theorem (Theorem 7.2, iterated across the factors as in the proof of Corollary 7.3) determines $x$ modulo $N$ uniquely. Each projection costs $O(\log N)$ operations by square-and-multiply.

Stage (b): lifting a prime power digit by digit. Fix one prime power $q^{e}$ (dropping the subscript $i$ ), with $\gamma=g_{i}$ of order $q^{e}$ and $\eta=h_{i}=\gamma^{x^{\prime}}$ , $x^{\prime}=x_{i}$ . Write $x^{\prime}$ in base $q$ :

x^{\prime}\equiv x_{0}+x_{1}q+\dots+x_{e-1}q^{e-1}\pmod{q^{e}},\qquad 0\leq x_% {j}<q.

The element $\delta=\gamma^{\,q^{e-1}}$ has order $q$ (Corollary 3.23 again). Raise $\eta$ to the power $q^{e-1}$ : every digit beyond the first is multiplied by a multiple of $q^{e}$ in the exponent and vanishes, leaving

\eta^{\,q^{e-1}}=\gamma^{\,x^{\prime}q^{e-1}}=\delta^{\,x_{0}},

a single DLP in the group $\langle\delta\rangle$ of prime order $q$ , which baby-step giant-step (Remark 7.22) solves in $O(\sqrt{q})$ operations. With $x_{0},\dots,x_{j-1}$ in hand, strip them off and repeat: the element $\eta_{j}=\eta\,\gamma^{-(x_{0}+x_{1}q+\dots+x_{j-1}q^{j-1})}$ equals $\gamma$ raised to $x_{j}q^{j}+(\text{multiples of }q^{j+1})$ , so

\eta_{j}^{\,q^{\,e-1-j}}=\delta^{\,x_{j}},

and digit $x_{j}$ is again one order- $q$ DLP. Each of the $e$ digits costs one such DLP plus $O(\log N)$ operations for the exponentiations.

Summing over the digits of all the prime-power factors gives $\sum_{i}e_{i}$ order- $q_{i}$ DLPs at $O(\sqrt{q_{i}})$ apiece plus $O(\log N)$ bookkeeping for each, which is the stated bound. □

Corollary 7.24 (Why prime order matters).

If $N$ has a small prime factor $q$ , an attacker can recover the discrete logarithm modulo $q$ in $O(\log N+\sqrt{q})$ group operations— $O(\log N)$ to project into the order- $q$ subgroup and $O(\sqrt{q})$ for the small DLP there—leaking part of the secret $x$ . Security therefore requires $N$ to have a large prime factor; the safest and simplest choice is to make $N$ itself a large prime, so that $G$ has no proper nontrivial subgroups and the Pohlig–Hellman reduction offers no purchase at all. This is precisely why the elliptic-curve groups used in Halo 2 and Orchard have large prime order.

Proof.

For the first claim, run stage (a) of Theorem 7.23 for the single factor $q$ : the projections $g^{N/q}$ , $h^{N/q}$ cost $O(\log N)$ operations, and the resulting DLP in a group of order $q$ costs $O(\sqrt{q})$ by baby-step giant-step—yielding $x\bmod q$ . For the second, if $N$ is prime then $G$ has no subgroups besides $\{e\}$ and $G$ (Corollary 3.34), so the reduction’s only output is the original problem, and the generic $\Omega(\sqrt{N})$ floor of Remark 7.22 stands at full height. □

Remark 7.25 (Cofactors and small-subgroup attacks).

In practice an elliptic curve over $\mathbb{F}_{p}$ has group order $h\cdot q$ , where $q$ is a large prime and $h$ is a small cofactor, and cryptographic operations stay confined to the subgroup of prime order $q$ . If a protocol neglects to check that incoming points lie in that subgroup (or fails to clear the cofactor), an adversary can supply a point of low order and run Pohlig–Hellman in the small factor to extract information about the secret modulo $h$ —a real-world small-subgroup attack. The Pasta curves of Halo 2 have cofactor $h=1$ : their group orders are themselves prime (the primes recorded in 10), which eliminates this class of attacks at the level of the group itself rather than by protocol-level checks.

The two demands with which the section opened are now both met. A receiver handed a compressed point $(x,\text{bit})$ decides in one modular exponentiation whether $x^{3}+ax+b$ is a square—Euler’s criterion—and, when it is, extracts a root by Proposition 7.17 or by Tonelli–Shanks (Theorem 7.19), the transmitted bit selecting between the pair $\pm y$ (Remark 7.20); for the Pasta fields, with their deliberately large $2$ -adic valuation $s=32$ , Tonelli–Shanks is the deployed route. On the security side, exponentiation runs in $O(\log N)$ operations while its inverse, the discrete logarithm, costs any generic attacker $\Omega(\sqrt{N})$ —a floor that composite group orders would undermine through Pohlig–Hellman, and that the prime, roughly $255$ -bit orders of the Pasta groups preserve in full, with no small subgroup left to attack. The structure of $\mathbb{Z}/q\mathbb{Z}$ for a large prime $q$ thus supplies both the functionality—a field of scalars acting on the group—and the security of the constructions built on it. The curves themselves, and the primes $p$ and $q$ that this section has treated as black boxes, are the business of 10.