This section treats the number theory behind two requirements of
elliptic-curve cryptography. A point of a curve
Throughout, and denote positive integers and 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 and an integer
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
is a ring isomorphism. It restricts to a group isomorphism
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 elements (Theorem 4.6 for each factor), and an injective map between finite sets of equal size is bijective: the distinct inputs have 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
the last product running over the distinct primes dividing .
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 are pairwise
coprime: a common divisor exceeding of two of them would have a
prime factor dividing both, which by Euclid’s lemma for primes
(Lemma 2.17) would equal both and
. Moreover each 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
Both congruences are Corollary 3.32, proved from Lagrange’s theorem.
If
The hypothesis says that is a unit
(Theorem 2.24), i.e. an element of the finite group
, whose order is
(Definition 2.26). By
Corollary 3.31—every element of a finite group
of order satisfies
Let be prime. If
Euler’s theorem underlies RSA: if
whenever
Let
The quantity is exactly the order of as an
element of the group , so the order theory of
3 applies verbatim:
(Corollary 3.23).
A primitive root modulo is an element with
Primitive roots need not exist for every modulus. The unit group
For every prime , the group
Cyclicity is the reason the prime-order groups of elliptic-curve
cryptography behave exactly like under addition once a
generator is fixed: a cyclic group of order is isomorphic to
The squares modulo a prime decide whether a curve point with a given -coordinate exists, the first decompression task.
Let be an odd prime and an integer with
For an odd prime , exactly of the nonzero
residues modulo are quadratic residues and are
non-residues. The squaring map
Consider
the middle equivalence because a field has no zero divisors
(Proposition 4.28). Since is odd,
Let be an odd prime and
First, the value is always . Fermat’s little theorem
(Corollary 7.5) gives
If is a residue, say
For an odd prime and an integer , the Legendre symbol is
Euler’s criterion (Theorem 7.13) then reads, uniformly,
so the symbol is computable by a single modular exponentiation, at a cost of modular multiplications by square-and-multiply (6.2). The criterion also shows that the symbol is completely multiplicative in :
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, is a square modulo any prime
By complete multiplicativity,
so is a non-square precisely when is. Whether is a square is settled by one Euler-criterion exponentiation in each field, a computation any computer-algebra system reproduces in milliseconds:
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
so
Decompression must also produce an with
Let
is a square root of , and the two square roots of are .
Primes
For
Let be an odd prime,
Write
by Fermat (Corollary 7.5); hence
divides but not , forcing
Initialise
(the exponent is an integer because is odd). We maintain three invariants:
the current has order exactly ;
the order of divides .
Initially (1) holds since
Each iteration proceeds as follows. If
and update
The invariants are preserved. For (1),
so the new has order dividing , which is for the new .
Each iteration strictly decreases , from through a
descending chain of nonnegative integers, so after at most
iterations the order of reaches
Finding the non-residue is the only randomised step in this section. A uniformly random element of is a non-residue with probability exactly (Proposition 7.12), and each candidate is checked by one Euler-criterion exponentiation (Definition 7.14), i.e. modular multiplications, so a few random trials find with high probability. In practice one non-residue per field is fixed and verified once: Example 7.16 shows that 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
(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 .
The shortcut of Proposition 7.17 still
outputs a candidate , 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 are the content of the
classification of cyclic groups: the map
Two generic algorithms solve the DLP in any group of order
, using only the group operation. Baby-step
giant-step is deterministic: set
The next theorem makes “well-chosen” precise.
Let
group operations. When has a large prime factor the term dominates; when is smooth—a product of primes bounded polynomially in —every term is polynomial in , 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 set
By Corollary 3.23,
Solving the smaller DLPs yields
Stage (b): lifting a prime power digit by digit. Fix one prime
power (dropping the subscript ), with
The element
a single DLP in the group of prime order
, which baby-step giant-step
(Remark 7.22) solves in
operations. Once
and digit is again one order- DLP. Each of the digits costs one such DLP plus operations for the exponentiations.
Summing over the digits of all the prime-power factors gives order- DLPs at apiece plus bookkeeping for each, which is the stated bound. □
If has a small prime factor , an attacker can recover the
discrete logarithm modulo in
For the first claim, apply stage (a) of
Theorem 7.23 to the single factor
: the projections , cost
operations, and the resulting DLP in a group of order costs
by baby-step giant-step—yielding
In practice an elliptic curve over has group order
A group of large prime order has the field as its scalars. The curves, and the primes and taken as given here, are the subject of 10.