Motivation
A BCH construction asks for an element of a specified multiplicative order. A cryptographic construction asks whether an exponent remains difficult to recover. These are different computational questions. Finding a suitable root of unity can be easy even when recovering an exponent in its cyclic group is much more expensive.
We will construct the required roots and then solve discrete logarithms by two general methods. Baby-step giant-step trades storage for a square-root search. Prime-power digit recovery uses a factorization of the group order to split the task into smaller logarithms. Together they explain why the order and its prime factors matter, rather than field size alone.
These are algorithms and upper bounds, not proofs of cryptographic hardness. An algorithm exponential in the binary length of an order does not disprove a polynomial-time hardness assumption; conversely, a large field does not by itself establish that assumption. Our computations use the verified field representation from the preceding units.
Definitions
Let be a field with elements and cyclic multiplicative group of size . Fix dividing , with its prime factorization supplied. For coding applications with an explicit length- word, trial division to obtain that factorization is polynomial in ; no claim of polynomial cost in is being made for arbitrary factorization.
Definition 14.3.1
(Order and discrete logarithm)
An element has order if and no smaller positive power is one. Its powers form the subgroup . A discrete logarithm of is the unique residue satisfying . Zero is not a multiplicative-group element.
For an element of order , the order of is : the equation is equivalent to , whose smallest positive solution is that quotient. We use exact field multiplication, inversion and exponentiation, with canonical coefficient-list encodings for comparing elements.
Theorem/proposition
Theorem 14.3.2
(Construct a root of the requested order)
Given the supplied factorization of and rational , one can find an element of order exactly with probability at least , or report failure, using polynomial time in , and the encoding length of with exact field arithmetic. Every returned element is deterministically verified. The procedure does not require factoring or solving a discrete logarithm.
Theorem 14.3.3
(Baby-step giant-step)
Given an element of known order and a nonzero target , one can test membership in and, when it holds, recover the logarithm using group operations and stored elements. Deterministic table sorting and lookup add encoding comparisons.
Theorem 14.3.4
(Prime-power digit recovery)
If is factored, a logarithm can be recovered by solving logarithms in order- groups for each factor and combining the answers by CRT. With baby-step giant-step for those small logarithms, the group-operation cost is
apart from table comparisons and supplied integer/field arithmetic. The factorization cost is excluded explicitly.
Proof sketch or proof idea
Project uniform elements onto the desired subgroup
Proof
(Projection, an exact order test and a fixed failure budget)
The map from has image the unique subgroup of order . To see this, write elements as powers of some abstract generator of the cyclic group. Multiplication of its exponent by produces exactly the multiples of modulo , each with preimages. Thus a uniform nonzero field element maps to a uniform element of that subgroup, even though the algorithm does not know the abstract generator.
A candidate has order exactly when and for every prime . If its order were a proper divisor, a prime dividing the quotient would fail one test. The projection already ensures the first condition, but verifying it is harmless.
There are generators in a cyclic order- group, by the order-of-a-power formula. Inclusion–exclusion over primes gives . In increasing order the distinct primes satisfy , so this product is at least . Since , it is at least for .
Choose an integer with , and try independently projected candidates. With ideal uniform nonzero draws, the probability all fail is at most . Return the first candidate passing the exact order tests.
To implement a nonzero draw, use fair bits for an integer label and accept labels from one through . Interpret accepted labels as base- coefficient lists, a bijection with nonzero field elements. Each attempt succeeds with probability at least . Cap each draw at attempts, where . Coupling with uncapped draws on the same bits bounds the probability that any cap changes the search by at most . Combined failure is at most , and all budgets are fixed and polynomial. Labels are used only for sampling, never as a substitute for field arithmetic.
The order test must be run at every prime divisor of ; one test is not enough.
Counterexample mode
Testing only one prime divisor accepts a wrong order
Claim: if and for the largest prime , then has order . Take and , with largest prime divisor three, and . Then
The candidate passes the test at three but has order three, not six; the test at two detects this. The repaired statement is the one used above: has order exactly when and for every prime dividing .
Match a baby step with a giant step
Proof
(Collision search and its cost)
Membership first has a simple exact test: if and only if . The subgroup already contains distinct roots of , so the field root bound permits no others. Reject zero and any failed membership test.
Put . Store baby steps for . Compute giant steps for until one equals a stored value. A collision gives , so return that exponent reduced modulo and verify it.
Every exponent has a decomposition with , since . Hence a collision must occur for a valid target. Consecutive baby steps use multiplication by ; consecutive giant steps use multiplication by , so their number is . Negative powers use the field inverse, not a discrete-log computation. Sorting canonical encodings and doing binary searches gives the stated deterministic comparison cost and storage bound.
The group-operation count is not the entire bit cost. An element represented by prime-field coefficients occupies bits, so the baby table uses bits apart from indices. The preceding arithmetic algorithms give polynomial bit cost in for each group operation. Comparing two canonical coefficient lists also has a cost proportional to their length in the worst case.
Sorting those lists is merely a way to index exact encodings; it does not put a field-compatible numerical order on the elements. The encoded labels can be compared lexicographically even though the field itself is not an ordered field. A hash-table implementation could offer a different expected lookup bound, but would need its own data-structure assumptions. The deterministic sorting-and-search estimate above avoids relying on that expectation. Finally, a matching exponent can lie above because may exceed . Reducing it modulo changes neither the group value nor the unique logarithm residue, and the final equality check makes the returned answer directly verifiable.
The table improves exhaustive search through exponents to roughly group operations. If is about , that is still about operations, exponential in the bit parameter: the algorithm supplies an upper bound and no matching hardness theorem.
Recover prime-power digits from low to high
Proof
(Digit induction and CRT recombination)
For a factor , project to and . The order of is , and the unknown exponent is . Let , which has order .
Suppose the first digits have given , represented from zero through . Write . Then
The higher digits disappear because their exponent is a multiple of . Solve this order- logarithm, set , and repeat through . Starting with proves the induction and recovers the whole prime-power residue.
The moduli are pairwise coprime. Set and choose with by Bézout. Then has all the recovered residues. Two solutions differ by a multiple of every coprime , hence by a multiple of their product , proving uniqueness.
Each digit uses ordinary exponentiation with group operations and an order- baby-step giant-step search. Processing prime powers sequentially permits reuse of storage. A group whose order has only small prime factors can therefore have easy logarithms despite a large order. The theorem does not assume that the factorization can always be found efficiently.
Proof X-ray
Which exponent removes which digits
Three hypotheses enter at separate places. The projection uses that has order exactly : only then does have order exactly and order exactly . With a smaller true order, could equal one and every digit would look like zero.
The key move is a two-sided cancellation. Multiplying by removes the digits already known; raising to turns the unknown high part into a multiple of , which vanishes, while the current digit survives as . Since and has order , the small logarithm fixes uniquely, so the induction from closes after steps. Uniqueness modulo then comes from the pairwise coprimality of the in the CRT step, not from the digit recovery itself.
Worked examples
Worked example 14.3.5
(A five-element root subgroup in a sixteen-element field)
In the element has order fifteen: the only prime-factor tests are and , both following from the irreducible quartic relation. Thus has order five. Its five powers are distinct roots of , suitable for a length-five cyclic construction.
The randomized projection can start from any uniform nonzero element, not necessarily this known primitive one. Cubing maps the fifteen elements uniformly onto that subgroup of five, with three preimages per output. Four of its five elements generate it, so one projected trial succeeds with probability .
Worked example 14.3.6
(A baby-step giant-step collision)
Modulo twenty-three, has order eleven. Let and . The baby steps are . The inverse giant multiplier is . The first giant value is thirteen, not in the table; the next is , matching baby exponent three. Hence , and verifies the result. The table never required an inverse of the integer four modulo eleven; it used a group inverse of .
Worked example 14.3.7
(Four binary digits of a smooth-order logarithm)
Modulo seventeen, has order sixteen because . Take and . At , , so the first digit is one and . At , the residual is , whose fourth power is sixteen; the next digit is one and .
At , the residual is , whose square is one, giving digit zero. At , the residual is still sixteen and no further power is needed, giving digit one. Thus . Direct multiplication gives . Each small logarithm had only two possibilities; the large-order search was unnecessary because the order is a power of two.
Concept lensStructural
A logarithm is an isomorphism onto residues
Because has order , the map , , is a group isomorphism, and the discrete logarithm is its inverse: it turns multiplication in into addition of residues. Digit recovery is this isomorphism read through CRT. Under , raising to maps onto its subgroup of order and sends to , which records exactly . The cost bound is accordingly governed by the largest prime .
Common mistakes
Common mistake
(An element with need not have order )
The identity satisfies that equation for every . Projection into the order- subgroup therefore needs a generator test before its output can serve as the requested element. The tests at exclude every proper order, rather than merely checking one convenient exponent.
Common mistake
(An efficient construction is not a hardness proof)
Neither a verified field nor a primitive element proves a cryptographic assumption. A logarithm solver yields a shared-secret solver and a decisional test in the familiar easy directions, but hardness converses require separate justification. The algorithms here show particular ways an assumption can fail on a selected group; they do not prove security of groups that resist these particular methods.
Summary
Projection and a verified order test construct roots needed by cyclic codes with an explicit bounded failure budget. Baby-step giant-step recovers any subgroup logarithm with square-root storage and group work. Factored group orders allow prime-power digit recovery and CRT recombination, exposing the importance of small factors while keeping the factorization assumption explicit.
Exercises
Quick check
(Why is projection by not enough without the final order tests?)
Ask which subgroups the projected element can lie in.
Solution · Answer
Projection lands in the correct subgroup but can land in a proper subgroup, including its identity. The tests exclude all proper divisors of , guaranteeing the exact order needed for distinct coordinate powers.
Quick check
(Why does characterize membership in the subgroup generated by an order- field element?)
Count the roots of already present in that subgroup.
Solution · Answer
That subgroup contains distinct roots of . A degree- polynomial over a field has no additional roots. The nonzero membership test therefore identifies exactly those powers.
Quick check
(In digit recovery, why are the unknown higher digits killed by the chosen exponent?)
Track the power of dividing the exponent of the unknown remainder.
Solution
The unknown remainder has exponent divisible by . Multiplying by makes it divisible by , the projected generator's order. The current digit instead remains as a power of the order- element .
Quick check
(Why does the prime-power algorithm not prove a polynomial-time algorithm for factoring arbitrary group orders?)
Check what the algorithm receives as input.
Solution
Its prime-power decomposition is supplied at the start. Efficiently exploiting a known factorization does not compute that factorization. Trial division is polynomial in an explicit coding length , but can be exponential in the binary length used in cryptographic complexity.
Quick check
(Projected logarithms give and . Recover .)
Use the CRT formula with and .
Solution
The CRT formula uses and . It gives . Directly, seven has residue one modulo three and two modulo five, and these residues determine it uniquely modulo fifteen.