1 Introduction↩︎

The Richelot \((2,2)\)-isogeny is the canonical gateway to explicit genus-2 isogenies: starting from a square-free sextic \(f=uvw\) with monic quadratics \(u,v,w\in\mathbb{F}_p[x]\), one obtains a codomain \(C':y^2=UVW\) by algebraic relations among the factors. The classical route forms the Wronskian minors \[U=v'w-vw',\qquad V=w'u-wu',\qquad W=u'v-uv',\] a construction that is elegant and well understood over odd characteristic. Yet it relies on polynomial differentiation and offers no intrinsic mechanism to certify that the output triple \((U,V,W)\) satisfies the admissibility conditions guaranteeing a smooth, separable codomain.

These limitations become relevant in settings that demand deterministic, certifiable implementations of the \((2,2)\)-step, such as hash functions built from Richelot isogeny chains [1] and related isogeny-based protocols [2], [3]. This motivates two design goals: first, to remove differentiation from the critical path while preserving the exact algebraic output of the classical step; second, to provide a local, lightweight certificate enforcing the standard soundness criterion (pairwise coprime quadratics with nonzero discriminants), rather than assuming it or detecting failure only downstream.

1.0.0.1 Approach

We work within the subresultant framework and interpret the Richelot step in terms of the \(2\times2\) minors: in degree \(2\), the three Plücker coordinates of the coefficient matrix encode the Wronskian output polynomial directly, and the first subresultant delivers two of the three coordinates via a single pseudo-remainder. This viewpoint naturally suggests a derivative-free reconstruction and an explicit way to check admissibility locally.

1.0.0.2 Contributions

Our contribution is primarily algebraic and algorithmic in nature: we provide a subresultant-based reinterpretation of the Richelot step over finite fields, together with a certified evaluator enforcing the classical admissibility conditions.

1. Algebraic equality without derivatives. We recast the Richelot \((2,2)\) step via the \(2\times2\) minors (Plücker coordinates) of the coefficient matrix. The first subresultant encodes two of the three minors, and a linear syzygy relation recovers the third; assembling them yields the remainder-polynomial route (RPR), which is proven equal in \(\mathbb{F}_p[x]\) to the classical Wronskian output (Sect. 3). To our knowledge, this is the first completely derivative-free Richelot construction via subresultants.

2. A guarded route with local certification. We introduce the Guarded Subresultant Route (GSR), which inserts constant-size algebraic guards (discriminants, resultants, and subresultant degree) and a lightweight post-check; a single bounded affine retry is allowed. The route either returns a certified \((U,V,W)\) or explicitly rejects non-admissible instances, with a fixed and verifiable control flow (Sect. 4).

3. Empirical behavior and scaling. A Python prototype over \(10^6\) matched trials per prime demonstrates a \(4.75\)–\(6\times\) kernel speedup for the derivative-free RPRover the classical Wronskian formula, while the full GSRpipeline with certification remains \(1.4\)–\(3\times\) faster. Degeneracy is concentrated at very small primes; at larger primes the route behaves reliably (Sect. 5).

1.0.0.3 Positioning

The classical soundness statement (see, e.g., Cassels–Flynn [4] and Gaudry et al. [5]) asserts that under pairwise coprimality and nonzero discriminants, any triple of pairwise coprime quadratics yields a smooth genus-2 codomain \((2,2)\)-isogenous to the source. Our contribution is complementary: we show how to construct that triple without derivatives and how to enforce the hypothesis by a local, explicit certificate within the same asymptotic cost.

1.0.0.4 Scope and terminology

All algebraic equalities and guards are established for \(p>2\). Throughout we use “route” to denote an algorithmic realization of the Richelot step; thus WRO(Wronskian Route), RPR(Remainder-Polynomial Route), and GSR (Guarded Subresultant Route) refer to concrete, interchangeable procedures that implement the same algebraic map under a shared normalization.

1.0.0.5 Paper organization

Section 2 recalls the relevant background. Section 3 develops the subresultant framework and proves equality to the Wronskian formulation. Section 4 formalizes the guarded evaluator, its certification policy, and correctness. Section 5 reports experimental verification, and Section 6 concludes.

2 Background and Degree-2 Specialization↩︎

Throughout, we work over a finite field \(\mathbb{F}_q\) of odd characteristic \(p>2\), and restrict to prime fields \(\mathbb{F}_p\) in all algorithmic and experimental settings; characteristic \(2\) is excluded since the middle coefficients in the Wronskian polynomials vanish identically (cf.Remark 2). Equalities between polynomials are understood up to a nonzero unit in \(\mathbb{F}_p^\times\) unless stated otherwise.

2.0.0.1 Notation

For \(P\in\mathbb{F}_p[x]\), write \(\deg P\) for its degree, \(\mathop{\mathrm{lc}}(P)\) for its leading coefficient, and \(\mathop{\mathrm{ct}}(P)\) for its constant term. For a quadratic \(q(x)=q_2x^2+q_1x+q_0\) we set \(\mathop{\mathrm{Disc}}(q)=q_1^2-4q_2q_0\). We use \(\mathop{\mathrm{Res}}(f,g)\) for the resultant and \(\mathop{\mathrm{Sres}}_1(f,g)\) for the first subresultant of \((f,g)\); see §2.3. When the greatest common divisor is computed via a pseudo-remainder sequence (PRS) and compared modulo units, we write \(\gcd^\ast(\cdot,\cdot)\). We reserve \(\Delta\) for discriminants, e.g.\(\Delta_u=\mathop{\mathrm{Disc}}(u)\) and \(\Delta_f=\mathop{\mathrm{Disc}}(f)\). Vectors of coefficients of a quadratic \(q\) are denoted \((q_2,q_1,q_0)\).

2.1 Genus-2 curves and Richelot’s classical step↩︎

A genus-\(2\) curve over \(\mathbb{F}_p\) admits an affine model \[C:\; y^2 = f(x),\qquad f\in\mathbb{F}_p[x],\quad \deg f=6,\quad f \text{ square-free}.\] We focus on the widely used situation where \(f\) factors as a product of three pairwise coprime quadratics: \[\label{eq:uvw} \begin{align} &f = u\,v\,w, \quad u,v,w\in\mathbb{F}_p[x],\quad \deg u=\deg v=\deg w=2,\\ &\gcd(u,v)=\gcd(v,w)=\gcd(w,u)=1, \end{align}\tag{1}\] with all three taken as monic for a consistent normalization. Given 1 , the classical Richelot step constructs \[\label{eq:wronskians} U = v'w - v w', \qquad V = w'u - w u', \qquad W = u'v - u v',\tag{2}\] where derivatives are with respect to \(x\), and defines the codomain curve \(C':y^2=UVW\).

2.2 Discriminants, resultants, and coprimality tests↩︎

For a quadratic \(q(x)=q_2x^2+q_1x+q_0\), its discriminant is \(\mathop{\mathrm{Disc}}(q)=q_1^2-4q_2q_0\); it vanishes iff \(q\) has a double root. For \(f,g\in\mathbb{F}_p[x]\), the resultant \(\mathop{\mathrm{Res}}(f,g)\) is nonzero iff \(\gcd(f,g)=1\) and can be computed as the determinant of the Sylvester matrix. In degree \(2\), both \(\mathop{\mathrm{Res}}\) and the first subresultant \(\mathop{\mathrm{Sres}}_1\) admit constant-cost formulas in terms of \(2\times2\) minors (see §2.3). We will use the following well-known implications for quadratics:

• \(\mathop{\mathrm{Disc}}(q)=0 \iff q\) has a double root;

• \(\mathop{\mathrm{Res}}(f,g)=0 \iff \gcd(f,g)\ne1\);

• \(\deg \mathop{\mathrm{Sres}}_1(f,g)=1\) if and only if \(M_2=a_2b_1-a_1b_2\neq0\). In particular, for generic coprime quadratics this holds; it can fail only in the aligned case \(M_2=0\) (see Lemma 2).

These facts underlie the lightweight guard predicates employed later in Sect. 4.

2.3 Polynomial remainder sequences and first subresultants↩︎

Let \(f,g\in\mathbb{F}_p[x]\) with \(\deg f\ge \deg g\ge 1\). The (pseudo-)polynomial remainder sequence (PRS) is defined by \(r_{-1}=f\), \(r_0=g\), and \[\label{eq:PRS} r_{i+1} \;=\; -\,\operatorname{prem}(r_{i-1}, r_i),\qquad i\ge0,\tag{3}\] where \(\operatorname{prem}\) is the pseudo-remainder (it avoids coefficient division by clearing leading coefficients). The \(k\)-th subresultant \(\mathop{\mathrm{Sres}}_k(f,g)\) can be defined as a signed minor of the Sylvester matrix, and it is well-known to coincide (up to a unit in \(\mathbb{F}_p^\times\)) with the unique nonzero \(r_i\) of degree \(k\) in the PRS [6]–[11].

When \(f\) and \(g\) are quadratics, the first subresultant \(\mathop{\mathrm{Sres}}_1(f,g)\) has degree at most \(1\). By direct computation (see Lemma 1), \(\deg \mathop{\mathrm{Sres}}_1(f,g)=1\) if and only if the leading minor \(M_2=a_2b_1-a_1b_2\) is nonzero; this holds generically for coprime inputs, though it can fail in the “aligned” case when \(M_2=0\) (Lemma 2). Moreover, there exist (uniquely determined) cofactors \(C_f,C_g\in\mathbb{F}_p[x]\) with \(\deg C_f,\deg C_g\le1\) such that \[\label{eq:sres-identity-prelim} \mathop{\mathrm{Sres}}_1(f,g) \;=\; C_f(x)\,f(x)\;+\;C_g(x)\,g(x),\tag{4}\] and, up to a unit (\(\sim_{\text{unit}}\)), \(\mathop{\mathrm{Sres}}_1\) equals the linear minor \[\label{eq:sres-minor-prelim} \mathop{\mathrm{Sres}}_1(v,w)\sim_{\text{unit}}(a_2b_1-a_1b_2)\,x \;+\; (a_2b_0-a_0b_2),\tag{5}\] for \(v=a_2x^2+a_1x+a_0\) and \(w=b_2x^2+b_1x+b_0\). We will frequently exploit 4 –5 in Sect. 3 to relate subresultants to Wronskian images.

All operations above are constant-time in the field: a single pseudo-division suffices to extract \(M_2\) and \(M_1\), and the minor syzygy recovers \(M_0\); normalization to monic outputs can be done via a single batched inversion of the three leading coefficients of \((U,V,W)\) (see Sect. 4). These constant-factor considerations will be reflected in our experimental comparisons.

2.4 Normalization and equality up to units↩︎

Because the Richelot step is defined only up to nonzero scalars, we systematically make image quadratics \((U,V,W)\) monic. To avoid redundant inversions, we multiply the three nonzero leading coefficients, invert once, and distribute the inverse (batched inversion). When comparing formulas (Wronskian vs.subresultant), “equality” always means equality up to a nonzero scalar in \(\mathbb{F}_p^\times\); we write \(A \mathrel{\sim_{\mathrm{unit}}}B\) when \(A=c\,B\) for some \(c\in\mathbb{F}_p^\times\). Normalizations are chosen consistently across all methods.

3 Algebraic Equivalence and Derivative-Free Formulation↩︎

We show that the classical Wronskian description of a Richelot \((2,2)\) step is algebraically equivalent to a derivative-free construction based on the \(2\times 2\) minors of the coefficient matrix. The first subresultant \(\mathop{\mathrm{Sres}}_1\) encodes two of the three Plücker coordinates of the input pair, and the third is recovered via the minor syzygy a linear relation among \(2\times 2\) minors that holds for any \(2\times 3\) matrix over a field. This yields a canonical, derivative-free realization of the Richelot step over odd characteristic.

3.1 Explicit minors for degree-2 inputs↩︎

We fix two quadratics and spell out the three \(2\times3\) minors that will serve as building blocks throughout the paper.

Observe that \(U=M_2x^2+2M_1x+M_0\) depends on the coefficients of \(v\) and \(w\) only through the three Plücker coordinates \((M_2,M_1,M_0)\), and two of these are already given by the pseudo-remainder. The following identity recovers the third from the other two.

3.2 Derivative-free reconstruction via subresultant minors↩︎

We now give the construction at the heart of this paper: a reconstruction of the Wronskian output \(U\) that uses only the pseudo-remainder and the minor syzygy, avoiding all polynomial derivatives.

The preceding example illustrates a single pair; the following theorem establishes the identity in full generality.

3.3 Residue characterization via Bézout cofactors↩︎

For additional algebraic insight beyond the main proof chain, we record a residue characterization of \(U_{\ifmmode\mathrm{WRO}\else\textrm{\mathrm{\small WRO}}\fi}\) modulo \(\mathop{\mathrm{Sres}}_1\).

Identity ?? involves derivatives \(v',w'\) on the right-hand side; the derivative-free character of RPRrests instead on the minor-syzygy approach of Theorem 7. The cofactor-residue formula links the PRS to the tangent structure of the inputs in the quotient \(K\), providing geometric context for the algebraic identity.

3.4 Structured degree drop via aligned monic pairs↩︎

Beyond the characteristic-2 collapse of the Wronskian middle coefficient, there is a distinct algebraic locus present also in odd characteristic where \(\deg \mathop{\mathrm{Sres}}_1\) drops to 0 despite coprimality, namely when two inputs share their middle coefficient. The following lemma captures this case.

3.5 Operation counts↩︎

We give a precise field-operation count for each route per single \((2,2)\)-step on a monic quadratic triple \((u,v,w)\). Let \(\mathbf{M}\) denote a multiplication in \(\mathbb{F}_p\), \(\mathbf{S}\) a squaring, \(\mathbf{A}\) an addition or subtraction, and \(\mathbf{I}\) an inversion. Following standard practice in isogeny-based cryptography, we write \(\mathbf{S}\approx 0.8\,\mathbf{M}\) and treat \(\mathbf{A}\) as negligible relative to \(\mathbf{M}\). For a single pair \((v,w)\), the per-pair costs are:

Over three cyclic pairs, the totals are:

For each pair \((v,w)\), computing \(U=v'w-vw'\) via polynomial products of \(v'\) (degree 1) with \(w\) (degree 2) and vice versa costs \(6\,\mathbf{M}+9\,\mathbf{A}\) per pair. Over three cyclic pairs: \[\label{eq:wro-cost} C_{\ifmmode\mathrm{WRO}\else\textrm{\mathrm{\small WRO}}\fi} = 18\,\mathbf{M} + 27\,\mathbf{A} + 0\,\mathbf{I}.\tag{9}\]

Computing the three boundary minors \((M_2,M_1,M_0)\) from the \(2\times 3\) coefficient matrix and reconstructing the quadratic lift via \(U_1=2M_1\) costs \(6\,\mathbf{M}+4\,\mathbf{A}\) per pair. Over three pairs: \[\label{eq:rpr-cost} C_{\ifmmode\mathrm{RPR}\else\textrm{\mathrm{\small RPR}}\fi} = 18\,\mathbf{M} + 12\,\mathbf{A} + 0\,\mathbf{I}.\tag{10}\] The multiplication count matches WRO; the saving of \(15\,\mathbf{A}\) per step contributes to a measured \(4.75\)–\(6\times\) kernel speedup (Sect. 5), which exceeds the \(15/27\approx 56\%\) reduction in additions because the classical WROroute also requires constructing intermediate degree-\(3\) products \(v'w\) and \(vw'\) (each involving a polynomial multiplication loop) and an explicit derivative computation that the closed-form RPRbypasses entirely.

The guard layer evaluates: three discriminants \(\mathop{\mathrm{Disc}}(q)=q_1^2-4q_2q_0\), each costing \(1\,\mathbf{S}+1\,\mathbf{M}+1\,\mathbf{A}\) (subtotal \(3\,\mathbf{S}+3\,\mathbf{M}+3\,\mathbf{A}\)); three pairwise resultants of monic quadratics via minor expansion, each costing \(6\,\mathbf{M}+2\,\mathbf{S}+5\,\mathbf{A}\) (subtotal \(18\,\mathbf{M}+6\,\mathbf{S}+15\,\mathbf{A}\)); and three subresultant degree checks (free, reusing minors \(M_2\)). The post-check re-evaluates three resultants for coprimality and three discriminants on the output triple, totaling \(23\,\mathbf{M}+12\,\mathbf{S}+20\,\mathbf{A}\). Combined with the RPRcore: \[\label{eq:gsr-cost} C_{\ifmmode\mathrm{GSR}\else\textrm{\mathrm{\small GSR}}\fi} = 62\,\mathbf{M} + 21\,\mathbf{S} + 50\,\mathbf{A} \;\approx\; 79\,\mathbf{M}.\tag{11}\] With a retry (probability \(\le 3/(p{-}1)\) for \(p>10^3\); see Sect. 4.5), the worst case is \(\le 2\,C_{\ifmmode\mathrm{GSR}\else\textrm{\mathrm{\small GSR}}\fi}\approx 158\,\mathbf{M}\). No inversions or square roots are required in any route.

All routes store at most \(15\) intermediate field elements (minors, guard predicates) in addition to the \(6\) input coefficients: \(O(1)\) elements, i.e.\(O(\log p)\) bits.

3.5.0.1 Summary

Table 1 collects the per-step operation counts for the three routes.

5pt

The core step (WRO/RPR) uses \(18\,\mathbf{M}\) with no inversions or square roots, and the GSRprovides certified individual Richelot steps at \({\sim}79\,\mathbf{M}\) including full guard evaluation.

3.5.0.2 Relation to prior work

Castryck, Decru, and Smith [1] employ the same sextic-model Richelot step in a CGL hash function over \(\mathbb{F}_{p^2}\), but do not provide a detailed field-operation breakdown; their cost analysis focuses on square-root extractions (\(3\) per \(3\)-bit block), which dominate the per-step cost in their setting. Dartois et al. [3] compute \((2,2)\)-isogenies in the theta model on products of elliptic curves a fundamentally different algebraic representation that precludes direct numerical comparison with the sextic model. Our contribution is orthogonal to both: we provide a derivative-free reformulation and certified evaluator for the classical sextic-model step, rather than proposing an alternative representation.

3.5.0.3 Asymptotic complexity

All three routes execute \(O(1)\) field operations per \((2,2)\)-step. For an \(n\)-step isogeny chain, the total cost is \(O(n)\) multiplications in \(\mathbb{F}_p\).

4 Guarded Evaluation and Correctness↩︎

This section formalizes the Guarded Subresultant Evaluator (GSR) for the Richelot \((2,2)\) step, building on the algebraic foundations of Sect. 3. The evaluator enforces smoothness and separability through explicit algebraic guards and a single bounded affine retry, with proofs of correctness, algebraic consistency, and deterministic runtime behavior. All statements hold over finite fields \(\mathbb{F}_p\) for \(p>2\).

4.1 Design objectives and guiding principles↩︎

Let \(u,v,w\in\mathbb{F}_p[x]\) be monic, pairwise coprime quadratics and write \(f=uvw\). The goal of the evaluator is to compute \((U,V,W)\) such that \(C':y^2=UVW\) is \((2,2)\)-isogenous to \(C:y^2=uvw\), while guaranteeing correctness for every admissible input. Its design is guided by four principles:

1. Soundness. The output \(C'\) must be smooth of genus 2 and \((2,2)\)-isogenous to \(C\).

2. Determinism. The control flow follows a fixed pattern with at most one affine retry drawn from a deterministic schedule.

3. Local certification. A lightweight post-check validates degrees, coprimality, and discriminants.

4. Implementation independence. Algebraic guarantees hold independently of the arithmetic implementation; empirical constants appear in Sect. 5.

The evaluator therefore acts as a deterministic safeguard around the classical Wronskian route, combining algebraic equivalence (Sect. 3) with explicit runtime certification.

4.2 Guard system and preconditions↩︎

For \(q(x)=q_2x^2+q_1x+q_0\), set \(\mathop{\mathrm{Disc}}(q)=q_1^2-4q_2q_0\). We define seven algebraic predicates, each computed from fixed polynomial patterns: \[\setlength{\jot}{0.25ex} \begin{alignedat}{2} G_1:&\;\mathop{\mathrm{Disc}}(u)\neq 0, &\qquad G_2:&\;\mathop{\mathrm{Disc}}(v)\neq 0,\\ G_3:&\;\mathop{\mathrm{Disc}}(w)\neq 0, &\qquad G_4:&\;\mathop{\mathrm{Res}}(u,v)\neq 0,\\ G_5:&\;\mathop{\mathrm{Res}}(v,w)\neq 0, &\qquad G_6:&\;\mathop{\mathrm{Res}}(w,u)\neq 0,\\ \multicolumn{4}{l}{ G_7:\;\deg \mathop{\mathrm{Sres}}_1(u,v)=\deg \mathop{\mathrm{Sres}}_1(v,w)=\deg \mathop{\mathrm{Sres}}_1(w,u)=1. } \end{alignedat}\] Guards \(G_1\)–\(G_6\) ensure smoothness and pairwise coprimality, while \(G_7\) excludes the degree-drop locus \(\deg\mathop{\mathrm{Sres}}_1=0\) characterized in Sect. 3. Each guard is deterministic, input-independent, and evaluated in constant time. Table 2 summarizes the complete guard map.

4.2.0.1 Affine retry

If any pre-guard or post-check fails, an affine translation \(x \mapsto x+\delta\) is applied to avoid mid-coefficient cancellations in the Wronskian factors. This retry step does not alter the degree of \(\mathop{\mathrm{Sres}}_1\); its sole purpose is to skip the finite set of \(\delta\) values that cause degenerate middle coefficients in \(U,V,W\). When \(\deg \mathop{\mathrm{Sres}}_1 = 0\) for a quadratic pair (the aligned case of Lemma 2), the RPR reconstruction produces a degenerate output, which the post-check detects; since affine retry cannot restore \(\deg\mathop{\mathrm{Sres}}_1=1\) (Lemma 3), the evaluator reports FAIL.

4.2.0.2 Retry set \(B\)

The retry set \(B \subset \mathbb{F}_p\) collects the at most three affine shifts that nullify the mid-coefficients of the Wronskian quadratics (Proposition 13). Affine translation does not change \(\deg\mathop{\mathrm{Sres}}_1\) (Lemma 3), so the retry addresses only mid-coefficient vanishing, not the aligned-pair degeneracy.

4.3 Derivative-free reconstruction↩︎

The guarded evaluator rests on the equivalence between the derivative-based and minor-based Richelot constructions. Recall from Sect. 3.2 that the RPR construction extracts \((M_2,M_1)\) from the pseudo-remainder \(\mathop{\mathrm{prem}}(v,w)\), recovers \(M_0\) via the Plücker syzygy (Proposition 4), and assembles \(U_{\ifmmode\mathrm{RPR}\else\textrm{\mathrm{\small RPR}}\fi}=M_2x^2+2M_1x+M_0\) (Definition 1). By Theorem 7, this equals \(U_{\ifmmode\mathrm{WRO}\else\textrm{\mathrm{\small WRO}}\fi}=v'w-vw'\) in \(\mathbb{F}_p[x]\).

The guarded evaluator below relies on this identity.

4.4 Algorithm↩︎

The guarded evaluator wraps the RPRcore with pre-guards, a single bounded affine retry, and a post-check certifying the output triple. The following pseudocode (Algorithm 1) summarizes the control flow. Guards \(G_1\)–\(G_7\) are detailed in Table 2; the retry policy in Sect. 4.5.

4.5 Affine retry and fallback↩︎

The affine retry mechanism handles rare degree collapses in the middle coefficients of \((U,V,W)\) rather than correcting \(\deg\mathop{\mathrm{Sres}}_1\), contrary to what is sometimes assumed in informal descriptions.

We now bound the set of shifts that can cause mid-coefficient vanishing.

Affine retry is a deterministic, bounded mechanism. It does not alter \(\deg\mathop{\mathrm{Sres}}_1\) (Lemma 3), so it cannot resolve the aligned-pair degeneracy (\(M_2=0\)); however, when \(M_2\neq0\), it avoids the finitely many shifts at which mid-coefficients vanish. Combined with the guard system, this ensures that GSRbehaves as a Las–Vegas process with expected cost within a constant factor of the fast path.

A retry is triggered whenever any pre-guard (\(G_1\)–\(G_7\)) fails or a post-check (\(P_1\)–\(P_3\)) reports invalid output. At most one affine retry is permitted (maxRetries\({}=1\)). For small primes (\(p<10^3\)), the empirical retry rate slightly exceeds the theoretical bound \(3/(p{-}1)\) because the broader degeneracy window activates the retry on any guard failure, not only mid-coefficient vanishing. All benchmarks in Sect. 5 use this unified retry policy.

4.6 Certification and classical soundness↩︎

We formalize what it means for an output triple to be admissible.

Certification suffices to guarantee that the codomain is smooth and the isogeny is separable.

4.7 Correctness and determinism↩︎

4.8 Resultant identity and codomain equality↩︎

4.9 Cost model↩︎

Let \(\alpha\) denote a base-field multiplication and \(\beta\) a linear operation. Each route executes \(O(1)\) work per quadratic step: the WROfast path uses closed-form minors, the RPRpath performs a constant-size minor-syzygy reconstruction, and GSRadds seven predicates, one normalization, and a post-check, with at most one retry. Concrete constant factors are verified experimentally in Sect. 5.

5 Experimental Verification↩︎

We verified both the algebraic equivalence (Theorem 7) and the practical performance of the three evaluators through a prototype implementation in Python 3.13. All experiments were executed on a single core with \(10^6\) matched trials per prime per configuration, using five independent seeds and round-robin scheduling to eliminate ordering and cache bias.

5.1 Correctness verification↩︎

Beyond the formal proof of Theorem 7, the implementation was subjected to two independent empirical tests over \(2.5\times10^5\) random monic quadratic triples across five primes (\(p=101\), \(65\,537\), \(10^6{+}3\), \(2^{31}{-}1\), \(2^{61}{-}1\)):

1. For each trial, the RPRoutput was compared coefficient-wise against the classical WROoutput computed via explicit polynomial derivative and multiplication. All \(248\,537\) coprime trials produced exact agreement (after discarding \(1\,463\) non-coprime inputs), confirming Theorem 7 empirically.

2. Applying the Wronskian construction twice \((u,v,w)\mapsto(U,V,W) \mapsto(U',V',W')\) must yield \(U'V'W'=\lambda\cdot uvw\) for some \(\lambda\in\mathbb{F}_p^\times\) (Richelot self-duality). This was verified for all \(245\,248\) admissible trials; the remaining \(3\,289\) were degenerate (non-admissible output, overwhelmingly at \(p=101\)) and were skipped. This test is strictly stronger than (1), as any implementation error in the Richelot step would be amplified by the second application.

A SageMath cross-validation script is also provided in the supplementary materials.

5.2 Benchmark design↩︎

Five benchmark configurations were executed, each over three representative primes: \(p_1=65\,537\) (\(17\) bits), \(p_2=10^6{+}3\) (\(20\) bits), and \(p_3=2^{255}{-}19\) (\(255\) bits, the Curve25519 prime). An additional multi-prime scaling experiment included \(p=101\) and \(p=2^{127}{-}1\).

1. Kernel-only: WRO, RPR, and GSR-strict with guards and post-check disabled, measuring pure kernel computation time.

2. GSR-strict: RPRkernel with full post-check (\(P_1\)–\(P_3\)) and at most one affine retry.

3. GSR-full: Full guards (\(G_1\)–\(G_7\)) dispatch to WRO(closed-form) or RPR, with full post-check and retry.

4. GSR-light: Light guards (\(G_1\)–\(G_3\), two subresultant degree checks) with minimal post-check (\(P_1\)–\(P_2\) only).

5. Multi-prime scaling: Kernel-only across five primes (\(7\)–\(255\) bits) to assess speedup stability.

We note that all benchmarks use an interpreted language (Python) with arbitrary-precision integers; absolute timings reflect interpreter overhead rather than optimized finite-field arithmetic. The relative comparisons between routes are nonetheless meaningful, as all share the same runtime environment and data representation; the observed ratios are consistent with the theoretical operation counts.

5.3 Kernel speedup↩︎

Table 3 reports kernel-only timings.

The RPRkernel is \(4.75\)–\(6.0\times\) faster than the classical WROroute. This exceeds the theoretical prediction from the \(15\,\mathbf{A}\) saving alone (Eq. 10 ), because the traditional WROimplementation requires constructing intermediate degree-\(3\) products \(v'w\) and \(vw'\) via polynomial multiplication and computing explicit derivatives, all of which the closed-form RPRbypasses. The speedup is largest at small primes, where these intermediate operations are comparable in cost to field multiplications; it decreases to \(4.75\times\) at \(p=2^{255}{-}19\), where big-integer arithmetic dominates.

5.4 Full pipeline: GSR modes↩︎

Table 4 reports full pipeline timings with certification enabled.

Even with full certification, GSR-strict remains \(2.1\)–\(3.0\times\) faster than the classical WRO, because the cheap RPRkernel more than compensates for the post-check overhead (Eq. 11 : \(62\,\mathbf{M}+21\,\mathbf{S}\) total vs.\(18\,\mathbf{M}+27\,\mathbf{A}\) for WROalone).

The GSR-full variant, which evaluates the complete guard set (\(G_1\)–\(G_7\)) before dispatching, is \(1.4\)–\(1.9\times\) faster than WRO; the guard evaluation adds measurable overhead, particularly at the \(255\)-bit prime where big-integer arithmetic dominates. When guards pass which occurs in \(99.99\)–\(100\%\) of trials (Table 5) the WROclosed-form fast-path is used, so the overhead is limited to the guard predicates themselves.

The GSR-light variant nearly matches the raw RPRspeed, reaching \(2.1\)–\(2.8\times\) the speed of WRO, by evaluating only discriminants and two subresultant degree checks in the guard phase and omitting discriminant checks in the post-check.

5.5 Guard dispatch and retry statistics↩︎

For fields of practical interest (\(p\ge 65\,537\)), the full guard set passes in at least \(99.99\%\) of trials, confirming that the RPR fallback path is rarely exercised. The retry rate is \(0.011\%\) at \(p=65\,537\), consistent with the theoretical bound \(3/(p{-}1)\approx 0.005\%\) from Corollary 1 (the modest excess accounts for guard failures discriminant or resultant vanishing that also trigger retries but lie outside the mid-coefficient analysis). At \(p=10^6{+}3\) the retry rate drops to \(0.001\%\), and at \(p=2^{255}{-}19\) no retry was triggered in \(10^6\) trials, confirming that the retry mechanism is algebraically negligible for fields of cryptographic interest.

5.6 Prime-size scaling↩︎

To assess whether the speedup is stable across field sizes, we measured kernel-only timings over five primes spanning \(7\) to \(255\) bits (Table 6).

The speedup remains consistent: \(4.75\)–\(6.5\times\) across five orders of magnitude in prime size. (The slight discrepancy with the \(4.75\times\) figure for \(p=2^{255}{-}19\) reported in Table 3 reflects different trial counts and the distinction between paired per-trial median ratios and ratios of aggregate medians.) The slight decrease at large primes reflects the dominance of big-integer multiplication cost, which is shared by both routes; in a compiled implementation with fixed-width field arithmetic, the relative advantage of RPRwould be even more pronounced.

6 Conclusion↩︎

We have presented an algebraic reinterpretation of the Richelot \((2,2)\)-isogeny step for genus–\(2\) curves over finite fields of odd characteristic. By expressing the classical Wronskian construction in terms of first subresultants and Plücker minors of the coefficient matrix, we obtained a completely derivative-free formulation that produces the same output polynomials in \(\mathbb{F}_p[x]\) under a natural normalization. The resulting Remainder–Polynomial Route (RPR) is shown to be algebraically identical to the classical Wronskian route, not merely up to units, but as an explicit identity in the polynomial ring.

Building on this equivalence, we introduced the Guarded Subresultant Route (GSR), a deterministic evaluator that augments the derivative-free core with a constant-size system of algebraic guards and a lightweight post-check. These guards enforce the classical admissibility conditions nonvanishing discriminants, pairwise coprimality, and correct degree behavior and ensure that the evaluator either returns a certified quadratic triple or explicitly rejects non-admissible inputs. The control flow is fixed, verifiable, and allows at most one bounded affine retry, whose algebraic role and failure modes are fully characterized.

All three routes run in constant time per step in degree \(2\). RPR matches WRO in multiplication count but avoids the intermediate degree-\(3\) products and explicit derivatives, which accounts for the measured \(4.75\)–\(6\times\) kernel speedup. Adding the guard layer and post-check costs roughly \(79\,\mathbf{M}\) per step; the GSR-light variant keeps most of this certification at nearly the raw RPRspeed.

The subresultant viewpoint replaces derivatives by Plücker minors, the minor syzygy closes the reconstruction, and the guard layer certifies the output at bounded cost. Over \(10^6\) matched trials per prime, RPRruns \(4.75\)–\(6\times\) faster than the classical Wronskian kernel, and the full GSRpipeline stays \(1.4\)–\(3\times\) ahead of WROeven with certification enabled; retry rates fall below \(0.01\%\) for every prime \(p\ge 65\,537\). A double-Richelot involution test on \(2.5\times10^5\) triples across five primes independently confirms correctness.

6.0.0.1 Limitations

All results are established for odd characteristic; a systematic treatment of characteristic two, where the classical Wronskian construction degenerates and alternative notions of differentiation (e.g., Hasse derivatives) are required, remains open. The current framework is restricted to degree-\(2\) inputs; extensions to higher-degree or higher-genus settings would require generalizing the minor-syzygy framework. While the GSR control flow is deterministic and the branch structure depends only on boolean guard outcomes (Proposition 16), a fully constant-time implementation suitable for cryptographic deployment would require additional engineering (e.g., conditional moves to eliminate all data-dependent branches), which we do not address here. Our experimental validation uses a Python prototype; performance comparisons in optimized low-level implementations remain to be carried out.

6.0.0.2 Future work

The minor-syzygy framework should extend to higher-degree factors, though the number of Plücker coordinates grows and the syzygy relations become more involved. On the implementation side, a constant-time realization of GSR (replacing all branches by conditional moves) would be needed before deployment in isogeny-based protocols; combining it with tree-based chain algorithms is another natural direction.

Acknowledgements↩︎

The authors thank colleagues at University of Phuong Dong for helpful discussions during the preparation of this work.

CRediT authorship contribution statement↩︎

Hung T. Dang: Conceptualization, Methodology, Formal analysis, Investigation, Writing – original draft.

Diep V. Nguyen: Software implementation, Computational experiments, Validation, Writing – review & editing.

Declaration of competing interest↩︎

The authors declare that there is no conflict of interest.

Data availability↩︎

The Python source code for all experiments including the benchmark runner, the correctness verification script with double-Richelot involution test, and a SageMath cross-validation script is provided as supplementary material accompanying this submission. A public repository will be made available upon acceptance.

References↩︎