Deterministic Root-Finding over Finite Fields with Elliptic Curves

1.1 Problem statement

• Deterministic polynomial-time root-finding over general finite fields remains open, despite its central role in polynomial factorization and other algebraic algorithms.Factorization reduces to root-finding in deterministic polynomial time, and higher-level algebra algorithms use factorization as an oracle.Source: §1.1 · p. 3

1.2 Main contributions

• A deterministic online algorithm takes a split, separable polynomial and an elliptic preprocessing datum, then outputs all roots in the field.The method separates field-dependent offline preprocessing from processing the input polynomial.Source: §1.2 · p. 4
• Preprocessing data can be verified deterministically and unconditionally in time polynomial in log q and Ξ(D).This permits validity checking independently of constructing the datum.Source: §1.2 · p. 4
• Under Conjecture 1.5, sufficiently large-characteristic finite fields admit data with Ξ(D) bounded by a power of log q.The conjecture asks for paired smooth integers q + 1 − U and q + 1 + U; Proposition 1.4 connects such pairs to elliptic preprocessing data.Source: §1.2 · p. 5
• Deterministically constructing a datum with polylogarithmic Ξ(D) remains open, and a positive solution would yield polynomial-time root-finding in log q and deg(f).The paper frames its main result as reducing root-finding to constructing an elliptic curve whose group and twist both have smooth order.Source: §1.2 · p. 5

1.3 Comparison with prior work

• Replacing cyclotomic groups with elliptic-curve groups trades smoothness conditions on q − 1 for smoothness of rational-point group orders.The paper places this exchange alongside other elliptic-curve methods in computational number theory.Source: §1.3 · p. 6
• Unlike the Rónyai precursor, this algorithm computes over finite fields, avoids GRH, and gives an explicit complexity bound.The precursor uses Galois computations over number fields and has a polynomial bound whose degree is unspecified; classical transform methods require q − 1 to be smooth.Source: §1.3 · pp. 6–7

2.1 From cyclotomy to elliptic curves

• The method replaces the multiplicative group with the rational-point groups of E and its quadratic twist, whose group orders offer a less rigid smoothness parameter than q − 1.The overview notes that curve-and-twist order pairs range over almost the Hasse–Weil interval.Source: §2.1 · pp. 8–9

2.2 Lifting the roots onto the curves

• Roots are split by the quadratic character of h(x), then lifted to E or its twist using polynomial interpolants that encode square roots.The Mignotte–Schnorr recursion for ℓ = 2 separates the values h(x); the resulting interpolants are recombined by the Chinese Remainder Theorem.Source: §2.2 · p. 10

2.3 Representing sets of points

• A simple divisor is encoded by polynomials (u, v), where u records point x-coordinates and v interpolates their y-coordinates; general divisors are sums of simple ones.This representation lets the algorithms handle point collections using polynomial arithmetic.Source: §2.3 · pp. 10–11

2.4 Translating a split divisor

• Translation applies the elliptic-curve group law to the generic point, then recovers divisor coordinates; collisions are split off so the output remains a sum of simple divisors.The procedure costs eO(deg(D) log^2 q + deg(D)^ω) operations in Fq.Source: §2.4 · p. 11

2.5 The elliptic Mignotte–Schnorr recursion

• The elliptic Mignotte–Schnorr recursion separates support points by torsion classes, using division-polynomial tests and translations between levels.Algorithm 5 decomposes a divisor along an entire ℓ-Sylow subgroup; rank-two torsion accounts for the ℓ^2 factor, while cyclic torsion reduces it to ℓ.Source: §2.5 · pp. 11–12

2.6 Assembling the complexity bound

• The online phase costs eO(Ξ^2 n log^2 q + n^ω log q + n log^3 q), with linear rather than quadratic dependence on Ξ when both groups are cyclic.The bound combines runs on the curve and its twist with the lifting cost.Source: §2.6 · p. 12

2.7 The offline phase

• A preprocessing datum is verifiable deterministically and unconditionally in time polynomial in log q and Ξ, without point counting for q ≥ 37.The checks include independence of the basis points and that their orders multiply to the claimed group order.Source: §2.7 · p. 13

Elliptic curves and their quadratic twists

• For p > 3, elliptic curves are represented in short Weierstrass form, and a nonsquare β defines the quadratic twist used in the paper.The twist is a curve over Fq obtained by replacing Y^2 = X^3 + aX + b with βY^2 = X^3 + aX + b.Source: §3 · p. 14

Rational points on elliptic curves

• The trace U = q + 1 − |E(Fq)| satisfies |U| ≤ 2√q, and the twist has trace −U, so the two group orders sum to 2(q + 1).The groups of rational points have rank at most two, and their ℓ-torsion quotients have at most ℓ^2 classes.Source: §3 · p. 15

General notation

• The parameter Ξ(E) is the largest prime factor of |E(Fq)|·|eE(Fq)|; the paper assumes p > 3 and explicitly flags any use of GRH.The notation also defines eO bounds and ω as a feasible matrix-multiplication exponent.Source: §3 · pp. 14–15

4 Encoding the roots as rational points on an elliptic curve

• When h(α) is a square at every root α of f, an interpolant v satisfies v^2 ≡ h mod f and lifts each root to (α, v(α)) on E; the nonsquare case lifts to the twist.Such interpolants exist by choosing square roots at the roots and interpolating.Source: §4 · pp. 15–16

4.1 2-adic factorization via evaluation

• The 2-adic recursion factors f by evaluating h(α)β^(−j) until its order is odd, after which even and odd indices identify roots lifting to E and its twist, respectively.This procedure performs at most eO(m(deg(f) log q + deg(h))) operations in Fq.Source: §4.1 · p. 16
• At the first split, h(α)^((q−1)/2) is ±1 according to whether h(α) is a square, so exponentiation and GCDs separate the two root classes.The recursion halves the relevant exponent at each level and has depth at most val2(q − 1).Source: §4.1 · p. 16

10 end

• The recursive factorization costs at most eO(m(deg(f) log q + deg(h))) operations in Fq.At each recursion depth, the degrees of the factor polynomials sum to at most deg(f).Source: §10 · p. 18

4.2 Lifting split polynomials to split divisors

• A simple divisor is encoded by u, whose roots are point x-coordinates, and v, the degree-bounded interpolant of their y-coordinates satisfying v^2 ≡ X^3 + aX + b mod u.General split divisors are represented as sums of simple divisors, with a flag for the point at infinity.Source: §4.2 · p. 19
• FiniteFieldEmbedding lifts a split polynomial to divisors on E and its twist, and terminates correctly in at most eO(log(q)(deg(f) log q + deg(h))) operations.The construction splits roots according to whether h(α) is a square and combines the interpolants using the Chinese Remainder Theorem.Source: §4.2 · pp. 19–21

5 Factoring with elliptic curves

• Cyclotomic factoring uses GCDs with X^r − 1 and substitutions γX, while the elliptic setting uses division-polynomial evaluations for torsion tests.The next step in the elliptic framework is translation by a rational point.Source: §5 · p. 21

5.1 Translating split divisors

• ECTranslation applies the elliptic-curve group law to each simple divisor’s (u, v) representation and recovers the translated divisor via characteristic polynomials.The input point Q must avoid the divisor’s support, as must −Q.Source: §5.1 · pp. 22–23
• The interpolation step requires φ to be injective on the roots of u; without known roots, its coefficient system costs O~(deg(u)^2) to set up and O(deg(u)^ω) to solve.Under injectivity, the interpolating polynomial exists uniquely.Source: §5.1 · p. 22
• O~(deg(D) log^2 q + deg(D)^ω) operations suffice for ECTranslation on a split divisor D.The algorithm processes simple components separately and reconstructs translated divisors using characteristic polynomials.Source: §5.1 · p. 22

14 end

• Translated points can collide when distinct points become opposites, yielding a shared x-coordinate and preventing the translate from being simple.The algorithm separates these collision pairs from non-colliding points using multiplicities in the characteristic polynomial.Source: §14 · p. 24

5.2 Deterministic decomposition of split divisors on elliptic curves

• Algorithm 4 separates a divisor according to classes in E(Fq)[ℓ^m]/E(Fq)[ℓ^(m−1)] by testing whether [R − P] lies in E(Fq)[N_ℓ·ℓ^(m−1)].Its representatives J have cardinality ℓ or ℓ².Source: §5.2 · pp. 25–26
• One level separates points whose projections differ modulo E(Fq)[ℓ^(m−1)]; iterating the levels separates their full projections onto E(Fq)[ℓ∞].The partial step outputs subdivisors rather than the translated divisors used for its tests.Source: §5.2 · p. 25

16 end

• Division-polynomial values at generic points can be computed without expanding ψ_r, in O~(log r · deg(u)) operations.The recurrence is normalized to avoid division by 2Y, which may be a zero divisor modulo u.Source: §16 · p. 27
• Algorithm 5 chains decomposition levels from m down to 1, translating intermediate divisors into the subgroup required for the next recursive level and then translating outputs back.Points meeting the representative set J or its opposites are set aside before recursion.Source: §16 · p. 28
• The top-level algorithm uses m = val_ℓ(exponent(E(Fq))) to ensure the required input condition holds.Source: §16 · p. 28
• O~(m(ℓ² deg(D) log q + deg(D) log² q + deg(D)^ω)) operations suffice for ECPrimaryFacto; the bound improves to O~(m(ℓ deg(D) log q + deg(D) log² q + deg(D)^ω)) when E(Fq)[ℓ^m] is cyclic.Source: §16 · p. 28

• The excerpt lists “16 SP” and “(Q, eD(Q” without explaining either notation.Source: §10 · p. 29

• At each level, a recursive chain removes distinct torsion points and costs at most K T(d′) log(exp(1) + T(d′))^κ operations.The chain makes at most min(d′, 2ℓ²) removal calls; its recursive divisor has degree at most d′.Source: §23 · p. 30
• The online phase lifts roots to divisors on E and its twist, recursively decomposes them through ℓ-Sylow projections, then recovers roots from linear factors.The input also includes an elliptic preprocessing datum D.Source: §23 · pp. 30–31
• At most eO(Ξ(D)^2 deg(f) log^2 q + deg(f)^ω log q + deg(f) log^3 q) operations in Fq suffice for correct, terminating root-finding.The algorithm is unconditional: its loops and subroutines terminate.Source: §23 · p. 31
• The algorithm separates roots into the E and twist branches, whose polynomial factors are maintained through ECPrimaryFacto until their degrees are one.The branch products track u0(X) and the transformed u1(X), respectively.Source: §23 · p. 31
• The proof rules out a remaining factor of degree above one by showing two distinct roots would be separated by an ℓ-primary decomposition.For distinct points P and P′, some prime ℓ dividing N distinguishes their difference; they therefore cannot remain in the same final polynomial.Source: §23 · p. 31

• The algorithm sets the twist’s ℓ-adic level from the maximum valuations of the two supplied generator orders.Source: §12 · p. 32
• For each twist factor, the algorithm forms a simple divisor using its u-coordinate and v1(βX)/β reduced modulo that factor.Source: §12 · p. 32
• ECPrimaryFacto decomposes each twist divisor, and the algorithm replaces the factor set with the u-coordinates of the resulting simple divisors.Source: §12 · p. 32

• FiniteFieldEmbedding and ECPrimaryFacto dominate the total cost; the remaining operations are negligible.Source: §22 · p. 33
• FiniteFieldEmbedding requires eO(log^2 q deg(f)) operations.Source: §22 · p. 33
• The bound improves when both E(Fq) and its twist are cyclic and generators for both groups are supplied.The improvement follows from the cyclic-case bound for Proposition 5.6.Source: §22 · p. 33

6 Computing and verifying elliptic preprocessing data

• For even e, a nonsquare in Fq can be constructed deterministically and unconditionally in polynomial time.The construction starts with θ outside F_(√q) and sets δ = θ − θ^(√q).Source: §6 · pp. 33–34

6.1 Constructing the curve: the CM method and its limitations

• The CM method constructs a curve from a prescribed trace, but its small-discriminant requirement is unlikely to yield sufficiently smooth orders for every prime field.In this setting, both q + 1 − U and q + 1 + U are sought without large prime factors.Source: §6.1 · p. 34

6.2 Distribution of elliptic curves with smooth group orders

• The heuristic predicts that simultaneous smoothness of the curve and twist orders requires a larger threshold than smoothness of a single order.Under the stated equidistribution and independence heuristics, the expected count grows for α > 4 for pairs, versus α > 2 for single orders.Source: §6.2 · p. 35
• A datum with Ξ(D) ≤ (log q)^O(1) would give polynomial-time online root-finding, but the conjecture asserting such data does not explain how to construct them.Source: §6.2 · p. 36

6.3 Computing the group orders, their factorizations, and the bases

• The group orders can be computed deterministically, while deterministic generator construction is available under GRH for prime fields and depends on the largest prime factor.The order of the twist is 2(q + 1) − N; a basis can be assembled from generators of the Sylow subgroups.Source: §6.3 · pp. 36–37

6.4 Verifying a preprocessing datum

• A supplied preprocessing datum can be checked deterministically and unconditionally in eO(log^3 q + Ξ(D) log^2 q) bit operations.The checks include the curve equations, group orders, listed factorizations, and generator independence.Source: §6.4 · p. 37

7.1 Experimental evidence for Conjecture 1.5

• Across tested prime fields and quadratic extensions, the observed exponent stays within a narrow band and grows slowly with q.The tested range is too small to support an estimate of the conjectured exponent c.Source: §7.1 · p. 38
• The predicted threshold exponent rises from 1.38 to 1.64 for prime q and from 1.47 to 1.70 for q = p^2 over the sampled ranges.For each q, the threshold is where the heuristic expected count of admissible traces reaches one.Source: §7.1 · p. 38
• The observed exponent follows the heuristic threshold closely, lying slightly below it on average.The threshold's expected-count criterion ignores count fluctuations and the o(1) term in the Dickman estimate.Source: §7.1 · p. 38

7.2 Proof-of-concept implementation in Magma

• The selected elliptic curve and its twist yield Ξ(D) = 2693 ≈ log(p)^2.091, which controls the online phase complexity.The datum was certified by Proposition 6.4 in negligible time.Source: §7.2 · p. 39
• The curve search tested a few million j-invariants out of approximately 2^63, only a tiny fraction of the possibilities.Source: §7.2 · p. 39
• A Magma prototype computed all 3000 roots in about 3 minutes when given the preprocessing datum.The polynomial was generated from 3000 uniformly sampled distinct elements of F_p.Source: §7.2 · p. 39
• The classical Mignotte–Schnorr algorithm would require about 262 GCD computations because the largest prime factor of p−1 is (p−1)/2 ≈ 262.Source: §7.2 · p. 39

8.1 Improving the complexity bound

• Replacing explicit matrices with power projections may lower the complexity exponent from ω to (ω + 1)/2, but adapting recent randomized techniques to deterministic algorithms remains open.The two current deg(f)^ω steps are implicit interpolation and characteristic-polynomial computation.Source: §8.1 · p. 40

8.2 Using more general curves

• Hyperelliptic curves could provide more flexibility in constructing smooth-order groups, but their genus-g Jacobians have approximately q^g points, making smoothness less likely.The approach would use rational points on the Jacobian and Cantor analogues of division polynomials.Source: §8.2 · p. 40

8.3 Using other algebraic groups

• Other commutative algebraic groups, including algebraic tori, may offer another direction, though known deterministic algorithms for smooth cyclotomic values are mainly theoretical.Adapting the Mignotte–Schnorr framework to tori could yield more explicit and practical complexity bounds.Source: §8.3 · p. 40

8.4 Polynomial-time deterministic precomputation

• For prime q, polynomial-time deterministic preprocessing under GRH reduces to finding a realizable trace whose paired orders are (log q)^O(1)-smooth; no deterministic way to find one is known.The CM method reaches only small-discriminant traces, exhaustive j-invariant scanning is not polynomial, and the existence conjecture gives no density estimate.Source: §8.4 · p. 41

A Pseudo-code for the Mignotte–Schnorr algorithm

• The polynomials Hβ,ℓ,j isolate roots according to their projection onto the ℓ-Sylow subgroup, and their roots form a coset of a subgroup of F_q^×.They are binomials, allowing modular reductions through binary exponentiation.Source: A Pseudo-code for the Mignotte–Schnorr… · p. 41
• Hβ,ℓ,j1 and Hβ,ℓ,j2 have identical root sets when j1 ≡ j2 mod ℓ^m and no common root otherwise.Source: A Pseudo-code for the Mignotte–Schnorr… · pp. 41–42
• A GCD with Hβ,ℓ,j can be computed in eO(log q deg f) operations in F_q.The procedure reduces Hβ,ℓ,j modulo f by binary exponentiation, then computes the GCD using fast GCD algorithms.Source: A Pseudo-code for the Mignotte–Schnorr… · p. 42
• Given a primitive element of F_q^×, the algorithm deterministically separates roots using the Hβ,ℓ,j polynomials.The appendix presents the classical Mignotte–Schnorr method, not new results.Source: A Pseudo-code for the Mignotte–Schnorr… · pp. 41–42

18 end

• Algorithm 7 terminates and is correct by induction on m, with recursive calls decreasing m and preserving the required input conditions.Source: A Pseudo-code for the Mignotte–Schnorr… · p. 42, §18 · p. 44