This section treats the number theory behind two requirements of
elliptic-curve cryptography. A point (x, y) of a curve
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.
A class
For a prime p and an integer
| φ (p k) = p k − p k − 1 = p k (1 − 1 p) . |
Among
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
If
| Z / m n Z ⟶ Z / m Z × Z / n Z, [a] m n ⟼ ([a] m, [a] n) |
is a ring isomorphism. It restricts to a group isomorphism
| (Z / m n Z) × ≅ (Z / m Z) × × (Z / n Z) × . |
The map is well defined: if
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
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 φ matches
units with units: if
If
| φ (n) = ∏ i (p i k i − p i k i − 1) = n ∏ p ∣ n (1 − 1 p), |
the last product running over the distinct primes dividing n .
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
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
| φ (n) = ∏ i (p i k i − p i k i − 1) = ∏ i p i k i (1 − 1 p i) = n ∏ p ∣ n (1 − 1 p) . ∎ |
Both congruences are Corollary 3.32, proved from Lagrange’s theorem.
If
| a φ (n) ≡ 1 (mod n) . |
The hypothesis says that [a] n is a unit
(Theorem 2.24), i.e. an element of the finite group
(Z / n Z) × , whose order is φ (n)
(Definition 2.26). By
Corollary 3.31—every element g of a finite group
of order N satisfies
Let p be prime. If
Euler’s theorem underlies RSA: if
| (a e) d = a 1 + k φ (n) = a ⋅ (a φ (n)) k ≡ a (mod n) |
whenever
Let
The quantity ord n (a) is exactly the order of [a] n as an
element of the group (Z / n Z) × , so the order theory of
3 applies verbatim:
| ord n (a j) = ord n (a) gcd (j, ord n (a)) |
(Corollary 3.23).
A primitive root modulo n is an element g with
Primitive roots need not exist for every modulus. The unit group
For every prime p , the group
Cyclicity is the reason the prime-order groups of elliptic-curve
cryptography behave exactly like Z / q Z under addition once a
generator is fixed: a cyclic group of order q is isomorphic to
The squares modulo a prime decide whether a curve point with a given x -coordinate exists, the first decompression task.
Let p be an odd prime and a an integer with
For an odd prime p , exactly p − 1 2 of the nonzero
residues modulo p are quadratic residues and p − 1 2 are
non-residues. The squaring map
Consider
| σ (x) = σ (y) ⇔ x 2 − y 2 = 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,
Let p be an odd prime and
| a p − 1 2 ≡ { 1 (mod p) if a is a quadratic residue, − 1 (mod p) if a is a quadratic non-residue. |
First, the value is always ± 1 . Fermat’s little theorem
(Corollary 7.5) gives
If a is a residue, say
For an odd prime p and an integer a , the Legendre symbol is
| (a p) = { 0 if p ∣ a, 1 if a is a quadratic residue modulo p, − 1 if a is a quadratic non-residue modulo p . |
Euler’s criterion (Theorem 7.13) then reads, uniformly,
| (a p) ≡ a p − 1 2 (mod p), |
so the symbol is computable by a single modular exponentiation, at a cost of O (log p) modular multiplications by square-and-multiply (6.2). The criterion also shows that the symbol is completely multiplicative in a :
| (a b p) = (a p) (b p), since (a b) p − 1 2 = a p − 1 2 b p − 1 2 . |
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
First, − 1 is a square modulo any prime
| (− 1 p) ≡ (− 1) p − 1 2 = 1 . |
By complete multiplicativity,
| (− 13 p) = (− 1 p) (13 p) = (13 p), |
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 p − 1 2 ≡ p − 1 ≡ − 1 (mod p), 13 q − 1 2 ≡ q − 1 ≡ − 1 (mod q), |
whence
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
| 5 p − 1 2 ≡ p − 1 ≡ − 1 (mod p), |
so
Decompression must also produce an x with
Let
| x ≡ a p + 1 4 (mod p) |
is a square root of a , and the two square roots of a are ± x .
Since
| x 2 = a p + 1 2 = a p − 1 2 ⋅ a ≡ (a p) ⋅ a = a (mod p), |
using Euler’s criterion
(Theorem 7.13) and the hypothesis that
a is a residue, so
Primes
For
Let p be an odd prime,
Write
| c 2 s − 1 = z 2 s − 1 d = z p − 1 2 ≡ − 1 ≠ 1, c 2 s = z p − 1 ≡ 1 |
by Fermat (Corollary 7.5); hence
ord p (c) divides 2 s but not 2 s − 1 , forcing
Initialise
| x = a d + 1 2, t = a d, m = s |
(the exponent d + 1 2 is an integer because d is odd). We maintain three invariants:
the current c has order exactly 2 m ;
the order of t divides 2 m − 1 .
Initially (1) holds since
Each iteration proceeds as follows. If
| b = c 2 m − i − 1, |
and update
| x ← x b, t ← t b 2, c ← b 2, m ← i . |
The invariants are preserved. For (1),
| (t b 2) 2 i − 1 = t 2 i − 1 (b 2) 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
Finding the non-residue z is the only randomised step in this section. A uniformly random element of F p × is a non-residue with probability exactly 1 2 (Proposition 7.12), and each candidate is checked by one Euler-criterion exponentiation (Definition 7.14), i.e. O (log p) 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.
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
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.
Let
Existence and uniqueness of log g h are the content of the
classification of cyclic groups: the map
Two generic algorithms solve the DLP in any group of order
N , using only the group operation. Baby-step
giant-step is deterministic: set
The next theorem makes “well-chosen” precise.
Let
| O (∑ i = 1 r e i (log N + q i)) |
group operations. When N has a large prime factor q max the 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 hence so is the cost of the DLP. Corollary 7.24 draws the design consequence.
Let
Stage (a): splitting across coprime factors. For each i set
| g i = g N i, h i = h N i . |
By Corollary 3.23,
| log g i h i = x i . |
Solving the r smaller DLPs yields
Stage (b): lifting a prime power digit by digit. Fix one prime
power q e (dropping the subscript i ), with
| x ′ ≡ x 0 + x 1 q + ⋯ + x e − 1 q e − 1 (mod q e), 0 ≤ x j < q . |
The element
| η q e − 1 = γ x ′ q e − 1 = δ x 0, |
a single DLP in the group ⟨ δ ⟩ of prime order
q , which baby-step giant-step
(Remark 7.22) solves in O (q)
operations. Once
| η j q e − 1 − j = δ 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 ∑ i e i order- q i DLPs at O (q i) apiece plus O (log N) bookkeeping for each, which is the stated bound. □
If N has a small prime factor q , an attacker can recover the
discrete logarithm modulo q in
For the first claim, apply stage (a) of
Theorem 7.23 to 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 (q) by baby-step giant-step—yielding
In practice an elliptic curve over F p has group order
A group of large prime order q has the field Z / q Z as its scalars. The curves, and the primes p and q taken as given here, are the subject of 10.