The Zcash ArboretumI Math Guide
Contents
PDF
Theme

7 Number theory for cryptography

This section treats the number theory behind two requirements of elliptic-curve cryptography. A point (x,y) of a curve y2=x3+ax+b (10) is determined by x up to the sign of y, so wire formats send x with one bit selecting the sign, halving the transmission; decompression must decide whether x3+ax+b is a square modulo p and, if it is, compute a square root, in the time of a few modular exponentiations on numbers hundreds of bits long. Elliptic-curve cryptography also publishes powers gx of a known group element while the exponent x is a secret key, so exponentiation must be efficient and its inversion infeasible. The section proves the Chinese Remainder Theorem and Euler’s criterion, gives square-root algorithms for p≡3(mod4) (Proposition 7.17) and in general (Theorem 7.19), and proves the Pohlig–Hellman reduction of a discrete logarithm to discrete logarithms in subgroups of prime order, whence the prime group orders of Halo 2 and Orchard (Corollary 7.24).

Throughout, n and m denote positive integers and p denotes a prime. Statements proved in 2, 3 and 6 (the cyclicity theorem) reappear in arithmetic form, with proofs by citation.

7.1 Euler’s totient function and the Chinese Remainder Theorem

A class [a]n∈ℤ/nℤ is a unit if and only if gcd(a,n)=1 (Theorem 2.24), the units form a finite abelian group (ℤ/n⁢ℤ)× (Proposition 3.8), and Euler’s totient φ(n) counts them: φ(n)=|(ℤ/n⁢ℤ)×| (Definition 2.26). In particular φ(p)=p−1 for a prime p (Example 2.27), so 𝔽p× has order p−1. Through the orders of elliptic-curve groups, the totient enters the parameter choices of Halo 2 and Orchard. Since 2 computes φ(n) only by enumeration, this subsection derives a formula from its values on prime powers and its multiplicativity on coprime factors.

Proposition 7.1 (Totient of a prime power).

For a prime p and an integer k≥1,

φ⁢(pk)=pk−pk−1=pk⁢(1−1p).
Proof.

Among 1,…,pk, we claim the integers not coprime to pk are exactly the multiples of p. If p∣a then p∣gcd(a,pk), so the gcd exceeds 1. Conversely, if g=gcd(a,pk)>1, then g has a prime factor ℓ; from ℓ∣g∣pk and Euclid’s lemma for primes (Lemma 2.17) we get ℓ=p, and ℓ∣g∣a gives p∣a. The multiples of p in the range are p,2p,…,pk−1⋅p, of which there are pk−1; subtracting them from the pk integers in the range leaves φ(pk)=pk−pk−1. □

Multiplicativity follows from the Chinese Remainder Theorem, which the discrete-logarithm subsection uses again. The theorem is stated in the language of rings (4), for the product ring R×S with componentwise operations (Example 4.5); a bijective ring homomorphism (Definition 4.21) is a ring isomorphism, as for groups (Definition 3.41).

Theorem 7.2 (Chinese Remainder Theorem).

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

ℤ/m⁢n⁢ℤ⟶ℤ/m⁢ℤ×ℤ/n⁢ℤ,[a]m⁢n⟼([a]m,[a]n)

is a ring isomorphism. It restricts to a group isomorphism

(ℤ/m⁢n⁢ℤ)×≅(ℤ/m⁢ℤ)××(ℤ/n⁢ℤ)×.
Proof.

The map is well defined: if [a]m⁢n=[a′]m⁢n then mn∣a−a′, hence m∣a−a′ and n∣a−a′, 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∣a and n∣a. Since gcd(m,n)=1, Euclid’s lemma (Proposition 2.15(2)) gives mn∣a, i.e. [a]m⁢n=[0]m⁢n.

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

For the multiplicative statement, a ring isomorphism ϕ matches units with units: if uv=1 then ϕ(u)ϕ(v)=ϕ(1)=1, and the same applies to ϕ−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 ϕ to unit groups therefore gives a bijection (ℤ/m⁢n⁢ℤ)×→(ℤ/m⁢ℤ)××(ℤ/n⁢ℤ)× that respects multiplication: a group isomorphism. □

Corollary 7.3 (Multiplicativity and the product formula).

If gcd(m,n)=1 then φ(mn)=φ(m)φ(n). Hence if n=∏ipiki is the prime factorisation of n, then

φ⁢(n)=∏i(piki−piki−1)=n⁢∏p∣n(1−1p),

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 φ(mn)=φ(m)φ(n).

For the product formula, the prime powers piki 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 pi and pj. Moreover each piki 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 φ(n)=∏iφ(piki), and Proposition 7.1 evaluates each factor:

φ⁢(n)=∏i(piki−piki−1)=∏ipiki⁢(1−1pi)=n⁢∏p∣n(1−1p).∎

For example, the product formula gives φ(12)=12(1−12)(1−13)=4, in agreement with the direct enumeration {1,5,7,11} of Example 2.27. Gauss’s divisor-sum identity ∑d∣nφ(d)=n is Lemma 6.17.

7.2 Fermat’s little theorem and Euler’s theorem

Both congruences are Corollary 3.32, proved from Lagrange’s theorem.

Theorem 7.4 (Euler’s theorem).

If gcd(a,n)=1, then

aφ⁢(n)≡1(modn).
Proof.

The hypothesis says that [a]n is a unit (Theorem 2.24), i.e. an element of the finite group (ℤ/n⁢ℤ)×, whose order is φ(n) (Definition 2.26). By Corollary 3.31—every element g of a finite group of order N satisfies gN=e, a consequence of Lagrange’s theorem—we get [a]nφ⁢(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∤a, then ap−1≡1(modp). Moreover ap≡a(modp) for every integer a.

Proof.

For p∤a we have gcd(a,p)=1, so Theorem 7.4 with n=p and φ(p)=p−1 (Example 2.27) gives the first congruence; multiplying it by a gives ap≡a(modp). When p∣a both ap 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≡1(modφ(n)), say ed=1+kφ(n), then

(ae)d=a1+k⁢φ⁢(n)=a⋅(aφ⁢(n))k≡a(modn)

whenever gcd(a,n)=1, so e can serve as a public encryption exponent and d as its private inverse. Orchard’s elliptic-curve cryptography instead uses Fermat’s little theorem in the field 𝔽p: every nonzero x satisfies xp−1=1, so inversion is computable as x−1=xp−2 (6.4).

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 ordn(a), is the least positive integer k with ak≡1(modn). Such a k exists because aφ⁢(n)≡1 by Theorem 7.4.

The quantity ordn(a) is exactly the order of [a]n as an element of the group (ℤ/n⁢ℤ)×, so the order theory of 3 applies verbatim: am≡1(modn) if and only if ordn(a)∣m (Proposition 3.12(1))—in particular ordn(a)∣φ(n), by Euler’s theorem—and

ordn⁡(aj)=ordn⁡(a)gcd⁡(j,ordn⁡(a))

(Corollary 3.23).

Definition 7.8 (Primitive root).

A primitive root modulo n is an element g with ordn(g)=φ(n); equivalently, g generates (ℤ/n⁢ℤ)× as a cyclic group, so that {g0,g1,…,gφ⁢(n)−1} lists all the units.

Primitive roots need not exist for every modulus. The unit group (ℤ/8⁢ℤ)×={1,3,5,7} has order φ(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. The unit group is isomorphic to 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 case that cryptography requires is n=p prime, where the multiplicative group is always cyclic.

Corollary 7.9 (𝔽p× is cyclic).

For every prime p, the group 𝔽p×=(ℤ/p⁢ℤ)× is cyclic of order p−1. In particular primitive roots modulo p exist, and there are exactly φ(p−1) of them; Example 6.22 exhibits the two primitive roots 3 and 5 of 𝔽7.

Proof.

The group 𝔽p× is a finite subgroup, of order p−1, of the multiplicative group of the field 𝔽p, hence cyclic by Theorem 6.18. A generator g has order p−1, and the powers gk that again generate are those with gcd(k,p−1)=1 (Corollary 3.23), numbering φ(p−1). □

Remark 7.10 (Cyclicity and prime-order groups).

Cyclicity is the reason the prime-order groups of elliptic-curve cryptography behave exactly like ℤ/qℤ under addition once a generator is fixed: a cyclic group of order q is isomorphic to (ℤ/qℤ,+) via gk↔k (Theorem 3.43). The full classification, stated without proof and not used later, is that primitive roots modulo n exist exactly when n∈{1,2,4,pk,2pk} for an odd prime p.

7.4 Quadratic residues and the Euler criterion

The squares modulo a prime decide whether a curve point with a given x-coordinate exists, the first decompression task.

Definition 7.11 (Quadratic residue).

Let p be an odd prime and a an integer with p∤a. We say a is a quadratic residue modulo p (a QR) if the congruence x2≡a(modp) has a solution, and a quadratic non-residue (a QNR) otherwise.

Proposition 7.12 (Exactly half are residues).

For an odd prime p, exactly p−12 of the nonzero residues modulo p are quadratic residues and p−12 are non-residues. The squaring map x↦x2 is exactly two-to-one on 𝔽p×.

Proof.

Consider σ:𝔽p×→𝔽p×, σ(x)=x2; its image is exactly the set of quadratic residues. For x,y∈𝔽p×,

σ⁢(x)=σ⁢(y)⇔x2−y2=0⇔(x−y)⁢(x+y)=0⇔y=±x,

the middle equivalence because a field has no zero divisors (Proposition 4.28). Since p is odd, x≠−x for x≠0 (otherwise 2x=0 with 2 and x nonzero), so every fibre of σ over its image has exactly two elements. Counting, |imσ|=p−12, and the complement—the non-residues—has the same size. □

Theorem 7.13 (Euler’s criterion).

Let p be an odd prime and p∤a. Then

ap−12≡{1(modp)if ⁢a⁢ is a quadratic residue,−1(modp)if ⁢a⁢ is a quadratic non-residue.
Proof.

First, the value is always ±1. Fermat’s little theorem (Corollary 7.5) gives (a(p−1)/2)2=ap−1≡1, and the only square roots of 1 modulo a prime are ±1: from x2≡1 we get p∣(x−1)(x+1), so p∣x−1 or p∣x+1 by Euclid’s lemma for primes (Lemma 2.17), i.e. x≡±1. Hence a(p−1)/2≡±1(modp).

If a is a residue, say a≡x2 with p∤x, then a(p−1)/2≡xp−1≡1, again by Fermat. Thus every one of the p−12 quadratic residues (Proposition 7.12) is a root of the polynomial t(p−1)/2−1 over 𝔽p. That polynomial has degree p−12, so it has at most p−12 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≡±1; the remaining possibility is a(p−1)/2≡−1. □

Definition 7.14 (Legendre symbol).

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

(ap)={0if ⁢p∣a,1if ⁢a⁢ is a quadratic residue modulo ⁢p,−1if ⁢a⁢ is a quadratic non-residue modulo ⁢p.

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

(ap)≡ap−12(modp),

so the symbol is computable by a single modular exponentiation, at a cost of O(logp) modular multiplications by square-and-multiply (6.2). The criterion also shows that the symbol is completely multiplicative in a:

(a⁢bp)=(ap)⁢(bp),since(a⁢b)p−12=ap−12⁢bp−12.
Example 7.15 (13 is a non-square in both Pasta fields).

Orchard uses the Pasta hash-to-curve construction, a procedure, treated in later volumes, that maps arbitrary byte strings to curve points and requires a fixed constant in the base field that must, among other conditions, be a non-square. The construction 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≡q≡1(mod4). The verification below works modulo p; the computation modulo q is identical.

First, −1 is a square modulo any prime ≡1(mod4): the exponent p−12 is even, so Euler’s criterion gives

(−1p)≡(−1)p−12=1.

By complete multiplicativity,

(−13p)=(−1p)⁢(13p)=(13p),

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:

13p−12≡p−1≡−1(modp),13q−12≡q−1≡−1(modq),

whence (13p)=(13q)=−1. Thus 13, and with it Z=−13, is a quadratic non-residue modulo both Pasta primes. Non-squareness is the first of four conditions that the construction (RFC 9380, §6.6.2) imposes on Z; the others are Z≠−1 and two conditions on the equation of an auxiliary curve onto which the construction first maps, and the Zcash protocol specification records −13 as suitable for both auxiliary curves (§5.4.9.8).

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

The same test decides a second constant on which later volumes rely, in this case the constant term of the curve equation. Pallas is the curve y2=x3+5 over 𝔽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 y2=5 has no solution in 𝔽p: the question is whether 5 is a square in the base field 𝔽p of Pallas, not in its scalar field 𝔽q. Euler’s criterion decides it in one exponentiation:

5p−12≡p−1≡−1(modp),

so (5p)=−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≡−1(modq), so Vesta has no such point either.) That no point has y=0 is a different fact—−5 is not a cube in 𝔽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

Decompression must also produce an x with x2≡a for a residue a, recovering y from y2; the cost depends on pmod4.

Proposition 7.17 (The p≡3(mod4) shortcut).

Let p≡3(mod4) be prime and let a be a quadratic residue modulo p with p∤a. Then

x≡ap+14(modp)

is a square root of a, and the two square roots of a are ±x.

Proof.

Since p≡3(mod4), the quantity p+14 is a positive integer. Compute

x2=ap+12=ap−12⋅a≡(ap)⋅a=a(modp),

using Euler’s criterion (Theorem 7.13) and the hypothesis that a is a residue, so (ap)=1. The roots come in the pair ±x by the two-to-one property of squaring (Proposition 7.12). □

Remark 7.18 (Cost and the Pasta primes).

Primes p≡3(mod4) are often favoured for this single-exponentiation shortcut. For p≡5(mod8) a closed-form variant (Atkin’s formula) exists. In general the cost of square-root extraction grows with the 2-adic valuation s of p−1: writing p−1=2sd with d odd, the Tonelli–Shanks algorithm below performs up to s corrective iterations. The Pasta primes have s=32, chosen for FFT-friendliness (9.10), so neither shortcut applies: square roots in the Pasta fields need the Tonelli–Shanks algorithm below or a refinement of it, such as the table-based variant to which the Zcash protocol specification points (§5.4.9.8).

For p≡1(mod4), write p−1=2sd with d odd and s≥2. The algorithm works in the subgroup of 𝔽p× of order 2s, which contains the obstruction to the single-exponentiation shortcut, and removes that obstruction one power of two at a time. The subgroup is unique since 𝔽p× is cyclic (Corollary 7.9 and Theorem 3.24(3)).

Theorem 7.19 (Tonelli–Shanks).

Let p be an odd prime, p−1=2sd with d odd, and let a be a quadratic residue with p∤a. Given any quadratic non-residue z modulo p, one can compute a square root of a modulo p using O(s2+logp) modular multiplications.

Proof.

Write H≤𝔽p× for the unique cyclic subgroup of order 2s. Set c=zd. We claim c generates H. By Euler’s criterion (Theorem 7.13) z(p−1)/2≡−1, so

c 2s−1=z 2s−1⁢d=zp−12≡−1≠1,c 2s=zp−1≡1

by Fermat (Corollary 7.5); hence ordp(c) divides 2s but not 2s−1, forcing ordp(c)=2s and ⟨c⟩=H.

Initialise

x=ad+12,t=ad,m=s

(the exponent d+12 is an integer because d is odd). We maintain three invariants:

  1. 1.

    x2=at;

  2. 2.

    the current c has order exactly 2m;

  3. 3.

    the order of t divides 2m−1.

Initially (1) holds since x2=ad+1=a⋅ad; (2) was proved above; and (3) holds because t 2s−1=a(p−1)/2≡1 by Euler’s criterion (Theorem 7.13), a being a residue.

Each iteration proceeds as follows. If t=1, then x2=a by (1) and the algorithm terminates. Otherwise let 2i=ordp(t), found as the least i≥1 with t 2i=1 by repeatedly squaring t; invariant (3) gives 1≤i≤m−1. Set

b=c 2m−i−1,

and update

x←x⁢b,t←t⁢b2,c←b2,m←i.

The invariants are preserved. For (1), (x⁢b)2=x2b2=atb2, which is a times the new t. For (2), the old c has order 2m, so ordp(b)=2m/gcd(2m,2m−i−1)=2i+1 (Corollary 3.23), and the new c=b2 has order 2i—exactly 2 to the new m. For (3), both the old t and b2 have order exactly 2i, so t 2i−1 and (b2) 2i−1 each have order 2; the only element of order 2 in 𝔽p× is −1, because the square roots of 1 are ±1 (as in the proof of Theorem 7.13); hence

(t⁢b2)2i−1=t 2i−1⁢(b2)2i−1=(−1)⁢(−1)=1,

so the new t has order dividing 2i−1, which is 2m−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 20=1, i.e. t=1, and x is the desired root. For the cost: locating i and computing b each take at most m≤s squarings, so the loop costs O(s) multiplications per iteration and O(s2) in total; the three initial exponentiations, with exponents smaller than p, cost O(logp) multiplications each by square-and-multiply (6.2). □

Finding the non-residue z is the only randomised step in this section. A uniformly random element of 𝔽p× is a non-residue with probability exactly 12 (Proposition 7.12), and each candidate is checked by one Euler-criterion exponentiation (Definition 7.14), i.e. O(logp) modular multiplications, so a few random trials find z with high probability. In practice one non-residue per field is fixed and verified once: Example 7.16 shows that 5 is one in both Pasta fields. This volume uses no deterministic polynomial-time method for finding a non-residue.

Remark 7.20 (Which root, and detecting failure).

The square roots of a residue come in a pair ±x (Proposition 7.12), so a canonical root is fixed by 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. Both algorithms detect a non-residue a. The shortcut of Proposition 7.17 still outputs a candidate a(p+1)/4, which fails the check x2≡a at the cost of one squaring. The variable-time Tonelli–Shanks algorithm cannot complete its update: Euler’s criterion gives a(p−1)/2≡−1, so t=ad satisfies t2s−1≡−1 and has order exactly 2s, and the first search for the least i≥1 with t2i=1 already returns i=m, which invariant (3) of the proof of Theorem 7.19 forbids and for which the update exponent 2m−i−1 is undefined. The algorithm can therefore report “not a residue” as soon as i=m occurs, or verify a(p−1)/2≡1 up front, at the same O(logp) cost as the initial exponentiations.

7.6 The discrete logarithm problem

The statements below concern a cyclic group written multiplicatively. In Orchard the group is the group of points of an elliptic curve, of large prime order and written additively; every statement transfers by renaming the operation.

Definition 7.21 (Discrete logarithm problem).

Let G=⟨g⟩ be a finite cyclic group of order N with generator g. Given h∈G, the discrete logarithm of h to base g, written loggh, is the unique residue x∈ℤ/Nℤ with gx=h. The discrete logarithm problem (DLP) is to compute x from (G,g,h).

Existence and uniqueness of loggh are the content of the classification of cyclic groups: the map x↦gx is a group isomorphism (ℤ/Nℤ,+)→∼G (Theorem 3.43, whose map ϕ¯ this is), so it has a well-defined inverse, and logg is that inverse. Computing gx from x takes O(logN) group operations by square-and-multiply (6.2); computing x from gx is the DLP, for which no efficient algorithm is known in well-chosen groups. This asymmetry 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 only the group operation. Baby-step giant-step is deterministic: set m=⌈N⌉ and write the unknown as x=im+j with 0≤i,j<m; tabulate the “baby steps” gj for all j, then walk the “giant steps” h(g−m)i for i=0,1,2,… until one equals a tabulated gj, at which point hg−i⁢m=gj gives x=im+j. Both the table and the walk are O(N), so the cost is O(N) time and space. Pollard’s rho (not developed here) is a randomised alternative with the same O(N) expected running time—on a heuristic analysis, made explicit in 10—but only O(1) space, and is the algorithm used in practical attacks. Conversely, Shoup’s theorem shows that Ω(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 λ-bit security level—no attack cheaper than 2λ operations—therefore requires N≈22⁢λ. This is why the Pallas and Vesta scalar fields have prime order roughly 255 bits long, targeting roughly 128-bit security (10). These costs hold for generic algorithms: in (ℤ/p⁢ℤ)×, sub-exponential index-calculus attacks exploit the ring structure of the integers behind the group. No such attack is known for elliptic-curve groups, which therefore permit much smaller parameters than multiplicative groups of comparable security.

The next theorem makes “well-chosen” precise.

Theorem 7.23 (Pohlig–Hellman reduction).

Let G=⟨g⟩ be cyclic of order N=∏i=1rqiei, the qi distinct primes. The discrete logarithm in G is computable by solving discrete logarithms in subgroups of prime order qi—ei of them for each i—and combining the answers with the Chinese Remainder Theorem, at a total cost of

O⁢(∑i=1rei⁢(log⁡N+qi))

group operations. When N has a large prime factor qmax the qmax term dominates; when N is smooth—a product of primes bounded polynomially in logN—every term is polynomial in logN, and hence so is the cost of the DLP. Corollary 7.24 draws the design consequence.

Proof.

Let h=gx with x the unknown. The reduction has two stages.

Stage (a): splitting across coprime factors. For each i set Ni=N/qiei and project:

gi=gNi,hi=hNi.

By Corollary 3.23, ord(gi)=N/gcd(N,Ni)=N/Ni=qiei, so gi generates the unique subgroup of G of order qiei (Theorem 3.24(3)). Moreover hi=gx⁢Ni=gix, and since gi has order qiei, the exponent matters only modulo qiei (Proposition 3.12(2)): writing xi=xmodqiei,

loggi⁡hi=xi.

Solving the r smaller DLPs yields xmodqiei for every i; since the prime powers qiei 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(logN) operations by square-and-multiply.

Stage (b): lifting a prime power digit by digit. Fix one prime power qe (dropping the subscript i), with γ=gi of order qe and η=hi=γx′, x′=xi. Write x′ in base q:

x′≡x0+x1⁢q+⋯+xe−1⁢qe−1(modqe),0≤xj<q.

The element δ=γqe−1 has order q (Corollary 3.23 again). Raise η to the power qe−1: every digit beyond the first is multiplied by a multiple of qe in the exponent and vanishes, leaving

ηqe−1=γx′⁢qe−1=δx0,

a single DLP in the group ⟨δ⟩ of prime order q, which baby-step giant-step (Remark 7.22) solves in O(q) operations. Once x0,…,xj−1 are known, they are removed and the step is repeated: the element ηj=ηγ−(x0+x1⁢q+⋯+xj−1⁢qj−1) equals γ raised to xjqj+(multiples of qj+1), so

ηjqe−1−j=δxj,

and digit xj is again one order-q DLP. Each of the e digits costs one such DLP plus O(logN) operations for the exponentiations.

Summing over the digits of all the prime-power factors gives ∑iei order-qi DLPs at O(qi) apiece plus O(logN) 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(logN+q) group operations—O(logN) to project into the order-q subgroup and O(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 yields no smaller problem. For this reason the elliptic-curve groups used in Halo 2 and Orchard have large prime order.

Proof.

For the first claim, apply stage (a) of Theorem 7.23 to the single factor q: the projections gN/q, hN/q cost O(logN) operations, and the resulting DLP in a group of order q costs O(q) by baby-step giant-step—yielding xmodq. 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 Ω(N) lower bound of Remark 7.22 applies in full. □

Remark 7.25 (Cofactors and small-subgroup attacks).

In practice an elliptic curve over 𝔽p has group order h⋅q, where q is a large prime and h is a small cofactor, and cryptographic operations stay in the subgroup of prime order q. A protocol that does not check that incoming points lie in that subgroup (or clear the cofactor) admits a practical small-subgroup attack: an adversary supplies a point of low order and runs Pohlig–Hellman in the small factor to extract information about the secret modulo h. The Pasta curves of Halo 2 have cofactor h=1: their group orders are prime (the primes recorded in 10), which eliminates this class of attacks in the group itself rather than by protocol-level checks.

A group of large prime order q has the field ℤ/qℤ as its scalars. The curves, and the primes p and q taken as given here, are the subject of 10.