Skip to main content

logicaffeine_proof/
hyperelliptic.rs

1//! # Genus-2 curves and the Richelot (2,2)-isogeny — the abelian-surface mechanism
2//!
3//! When an elliptic-curve pair is *glued* into an abelian surface (a genus-2 Jacobian), the Castryck–Decru
4//! break walks **(2,2)-isogenies** of that surface and watches for the codomain to **split** back into a
5//! product of elliptic curves — each split reveals a step of the secret isogeny.
6//!
7//! A genus-2 curve is `y² = f(x)` with `f` a sextic, and its 2-torsion is the six Weierstrass points (the
8//! roots of `f`). A **(2,2)-subgroup** is a partition of those six roots into three pairs — equivalently a
9//! factorisation `f = G₁·G₂·G₃` into three quadratics; there are exactly 15 of them, the neighbours in the
10//! (2,2)-isogeny graph. **Richelot's isogeny** sends `f` to the dual sextic `H₁·H₂·H₃`, where
11//! `Hᵢ = Gⱼ·Gₖ' − Gⱼ'·Gₖ` (`'` = `d/dx`, `{i,j,k}` cyclic), scaled by the **Richelot determinant**
12//! `δ = det[coeffs of G₁,G₂,G₃]`. When `δ = 0` the three quadratics are dependent, the correspondence
13//! degenerates, and the abelian surface is **reducible** — the split condition, in its cleanest form.
14//!
15//! This module builds that mechanism over `𝔽_p` and the chain-walk across the (2,2)-graph. The honest
16//! boundary: the *full* Castryck–Decru secret recovery, and Damien Robert's higher-dimensional (dimension
17//! 4/8, theta-coordinate) generalisation, are genuine research-grade machinery built ON this core — the
18//! chain-walk framework here is the shape they generalise, not a claim to have implemented dimension 8.
19
20use crate::factor::{mod_inverse, modpow};
21use logicaffeine_base::BigInt;
22
23#[inline]
24fn ib(x: i64) -> BigInt {
25    BigInt::from_i64(x)
26}
27#[inline]
28fn rp(a: &BigInt, p: &BigInt) -> BigInt {
29    let r = a.div_rem(p).map(|(_, r)| r).unwrap_or_else(|| a.clone());
30    if r.is_negative() {
31        r.add(p)
32    } else {
33        r
34    }
35}
36#[inline]
37fn mm(a: &BigInt, b: &BigInt, p: &BigInt) -> BigInt {
38    rp(&a.mul(b), p)
39}
40#[inline]
41fn am(a: &BigInt, b: &BigInt, p: &BigInt) -> BigInt {
42    rp(&a.add(b), p)
43}
44#[inline]
45fn sm(a: &BigInt, b: &BigInt, p: &BigInt) -> BigInt {
46    rp(&a.sub(b), p)
47}
48
49/// A quadratic `g₀ + g₁·x + g₂·x²`, coefficients low-to-high.
50pub type Quad = [BigInt; 3];
51
52/// Polynomial product mod `p` (coefficients low-to-high).
53pub fn poly_mul(a: &[BigInt], b: &[BigInt], p: &BigInt) -> Vec<BigInt> {
54    if a.is_empty() || b.is_empty() {
55        return Vec::new();
56    }
57    let mut r = vec![ib(0); a.len() + b.len() - 1];
58    for (i, ai) in a.iter().enumerate() {
59        for (j, bj) in b.iter().enumerate() {
60            r[i + j] = am(&r[i + j], &mm(ai, bj, p), p);
61        }
62    }
63    r
64}
65
66/// Formal derivative of a polynomial mod `p`.
67pub fn poly_deriv(a: &[BigInt], p: &BigInt) -> Vec<BigInt> {
68    (1..a.len()).map(|i| mm(&ib(i as i64), &a[i], p)).collect()
69}
70
71fn poly_sub(a: &[BigInt], b: &[BigInt], p: &BigInt) -> Vec<BigInt> {
72    let n = a.len().max(b.len());
73    (0..n)
74        .map(|i| sm(a.get(i).unwrap_or(&ib(0)), b.get(i).unwrap_or(&ib(0)), p))
75        .collect()
76}
77
78/// Drop trailing zero coefficients (so a polynomial's length reflects its true degree + 1).
79fn poly_trim(mut a: Vec<BigInt>) -> Vec<BigInt> {
80    while a.len() > 1 && a.last().is_some_and(|c| c.is_zero()) {
81        a.pop();
82    }
83    a
84}
85
86/// The result of a Richelot (2,2)-isogeny from a quadratic splitting `f = G₁·G₂·G₃`.
87#[derive(Clone, Debug)]
88pub struct Richelot {
89    /// The Richelot determinant `δ`. `δ = 0` ⟺ the surface is reducible (a product of elliptic curves).
90    pub delta: BigInt,
91    /// The domain sextic `G₁·G₂·G₃`.
92    pub domain: Vec<BigInt>,
93    /// The codomain sextic `H₁·H₂·H₃`.
94    pub codomain: Vec<BigInt>,
95    /// The three dual quadratics `Hᵢ`.
96    pub dual: [Vec<BigInt>; 3],
97}
98
99impl Richelot {
100    /// Whether the codomain abelian surface is **reducible** — splits as a product of elliptic curves. This
101    /// is the split condition the Castryck–Decru chain-walk searches for.
102    pub fn is_split(&self) -> bool {
103        self.delta.is_zero()
104    }
105}
106
107/// The Richelot (2,2)-isogeny from a quadratic splitting `G = (G₁, G₂, G₃)` over `𝔽_p`.
108pub fn richelot(g: &[Quad; 3], p: &BigInt) -> Richelot {
109    // δ = det of the coefficient matrix (rows = quadratics, columns = [g₂, g₁, g₀]).
110    let m = |i: usize, j: usize| &g[i][2 - j]; // column 0 = x² coeff
111    let det = {
112        let t1 = mm(
113            m(0, 0),
114            &sm(&mm(m(1, 1), m(2, 2), p), &mm(m(1, 2), m(2, 1), p), p),
115            p,
116        );
117        let t2 = mm(
118            m(0, 1),
119            &sm(&mm(m(1, 0), m(2, 2), p), &mm(m(1, 2), m(2, 0), p), p),
120            p,
121        );
122        let t3 = mm(
123            m(0, 2),
124            &sm(&mm(m(1, 0), m(2, 1), p), &mm(m(1, 1), m(2, 0), p), p),
125            p,
126        );
127        am(&sm(&t1, &t2, p), &t3, p)
128    };
129
130    // Hᵢ = Gⱼ·Gₖ' − Gⱼ'·Gₖ for {i,j,k} cyclic.
131    let quad = |q: &Quad| vec![q[0].clone(), q[1].clone(), q[2].clone()];
132    let dual_of = |j: usize, k: usize| {
133        let (gj, gk) = (quad(&g[j]), quad(&g[k]));
134        let (dj, dk) = (poly_deriv(&gj, p), poly_deriv(&gk, p));
135        poly_trim(poly_sub(&poly_mul(&gj, &dk, p), &poly_mul(&dj, &gk, p), p))
136    };
137    let dual = [dual_of(1, 2), dual_of(2, 0), dual_of(0, 1)];
138
139    let domain = poly_mul(&poly_mul(&quad(&g[0]), &quad(&g[1]), p), &quad(&g[2]), p);
140    let codomain = poly_mul(&poly_mul(&dual[0], &dual[1], p), &dual[2], p);
141
142    Richelot {
143        delta: det,
144        domain,
145        codomain,
146        dual,
147    }
148}
149
150/// The 15 quadratic splittings of six roots into three pairs — the neighbours of a genus-2 Jacobian in the
151/// (2,2)-isogeny graph. Each pair `(rₐ, r_b)` becomes the quadratic `(x−rₐ)(x−r_b)`.
152pub fn richelot_partitions(roots: &[BigInt; 6], p: &BigInt) -> Vec<[Quad; 3]> {
153    fn quad_from(ra: &BigInt, rb: &BigInt, p: &BigInt) -> Quad {
154        // (x − ra)(x − rb) = x² − (ra+rb)x + ra·rb
155        [mm(ra, rb, p), sm(&ib(0), &am(ra, rb, p), p), ib(1)]
156    }
157    let idx = [0usize, 1, 2, 3, 4, 5];
158    let mut out = Vec::new();
159    // Partition {0,1,2,3,4,5} into three unordered pairs: fix the partner of 0, then of the smallest left.
160    for a in 1..6 {
161        let rest1: Vec<usize> = idx.iter().copied().filter(|&x| x != 0 && x != a).collect();
162        let b0 = rest1[0];
163        for bi in 1..rest1.len() {
164            let b = rest1[bi];
165            let rest2: Vec<usize> = rest1
166                .iter()
167                .copied()
168                .filter(|&x| x != b0 && x != b)
169                .collect();
170            let (c, d) = (rest2[0], rest2[1]);
171            out.push([
172                quad_from(&roots[0], &roots[a], p),
173                quad_from(&roots[b0], &roots[b], p),
174                quad_from(&roots[c], &roots[d], p),
175            ]);
176        }
177    }
178    out
179}
180
181/// Walk the (2,2)-isogeny graph from a genus-2 Jacobian given by its six Weierstrass points: try each of the
182/// 15 Richelot neighbours and report whether **any** is a split (reducible) surface. This is the shape of
183/// the Castryck–Decru search — at real scale it is *guided* by the torsion images rather than exhaustive,
184/// and Robert's generalisation lifts the same walk to dimension 4/8. Returns the splitting quadratics of the
185/// first split neighbour, if one exists.
186pub fn find_split_neighbour(roots: &[BigInt; 6], p: &BigInt) -> Option<[Quad; 3]> {
187    richelot_partitions(roots, p)
188        .into_iter()
189        .find(|g| richelot(g, p).is_split())
190}
191
192/// Evaluate a polynomial at `x` mod `p` (Horner).
193pub fn poly_eval(a: &[BigInt], x: &BigInt, p: &BigInt) -> BigInt {
194    let mut acc = ib(0);
195    for c in a.iter().rev() {
196        acc = am(&mm(&acc, x, p), c, p);
197    }
198    acc
199}
200
201/// A genus-2 curve `C: y² = g(x²)` (an even sextic) with a **(2,2)-split Jacobian** `Jac(C) ~ E₁ × E₂`,
202/// together with its two elliptic quotients. This is the (2,2)-**gluing** in reverse: the two degree-2 maps
203/// `(x,y) ↦ (x², y)` onto `E₁: y² = g(u)` and `(x,y) ↦ (1/x², y/x³)` onto `E₂: y² = ĝ(u)` (the reversed
204/// cubic) exhibit the split. It is the abelian-surface object the Kani/Castryck–Decru oracle detects.
205#[derive(Clone, Debug)]
206pub struct SplitGenus2 {
207    /// The sextic `f(x) = g(x²)`, coefficients low→high (odd coefficients zero).
208    pub sextic: Vec<BigInt>,
209    /// `E₁: y² = g(u)` — the cubic `g`, coefficients low→high.
210    pub e1: Vec<BigInt>,
211    /// `E₂: y² = ĝ(u)` — the reversed cubic `u³·g(1/u)`, coefficients low→high.
212    pub e2: Vec<BigInt>,
213    pub p: BigInt,
214}
215
216/// Glue `E₁: y² = g(u)` with its reverse `E₂: y² = ĝ(u)` into the genus-2 curve `C: y² = g(x²)`. `g` is a
217/// cubic given low→high `[g₀, g₁, g₂, g₃]`. The result carries a split Jacobian — validated by the quotient
218/// maps and by the Richelot `±`-splitting being reducible (`δ = 0`).
219pub fn split_jacobian_from_cubic(g: &[BigInt], p: &BigInt) -> SplitGenus2 {
220    let z = ib(0);
221    let sextic = vec![
222        rp(&g[0], p),
223        z.clone(),
224        rp(&g[1], p),
225        z.clone(),
226        rp(&g[2], p),
227        z.clone(),
228        rp(&g[3], p),
229    ];
230    SplitGenus2 {
231        sextic,
232        e1: g.iter().map(|c| rp(c, p)).collect(),
233        e2: g.iter().rev().map(|c| rp(c, p)).collect(),
234        p: p.clone(),
235    }
236}
237
238/// A **matched-pair (2,2)-gluing**: the genus-2 curve `C: y² = ∏ᵢ(x² + cᵢx + 1)` whose Jacobian is
239/// `(2,2)`-isogenous to `E₁ × E₂`, where `E₁, E₂` share three of the four quartic 2-torsion roots `−cᵢ` and
240/// differ in the fourth (`∓2`). Derived from the involution `x ↦ 1/x` (invariants `t = x + 1/x`,
241/// `w = y(x³+1)/2x³`, giving `W = 2w/(t−1)` with `W² = (t+2)∏(t+cᵢ)`). Unlike the even-sextic special case,
242/// this is the *general* gluing along a matched 2-torsion; any two curves with a symplectic 2-torsion
243/// isomorphism reach this form after a Möbius normalization of the shared points. Validated exactly by
244/// `#Jac(C) = #E₁·#E₂` ([`genus2_jacobian_order`]).
245#[derive(Clone, Debug)]
246pub struct MatchedPairGlue {
247    /// `C: y² = ∏(x² + cᵢx + 1)` — the glued genus-2 curve (a sextic).
248    pub sextic: Vec<BigInt>,
249    /// `E₁: W² = (t+2)·∏(t+cᵢ)` — a quartic model of the first elliptic quotient.
250    pub e1: Vec<BigInt>,
251    /// `E₂: W² = (t−2)·∏(t+cᵢ)` — the second quotient (shares 3 of 4 roots with `E₁`).
252    pub e2: Vec<BigInt>,
253    pub p: BigInt,
254}
255
256/// Glue two elliptic curves along their matched 2-torsion `{−c₁, −c₂, −c₃}` into the genus-2 curve
257/// `C: y² = ∏(x² + cᵢx + 1)`. See [`MatchedPairGlue`].
258pub fn glue_shared_2torsion(c: &[BigInt; 3], p: &BigInt) -> MatchedPairGlue {
259    let quad = |ci: &BigInt| vec![ib(1), rp(ci, p), ib(1)]; // x² + cᵢ x + 1
260    let sextic = poly_mul(&poly_mul(&quad(&c[0]), &quad(&c[1]), p), &quad(&c[2]), p);
261    let lin = |r: BigInt| vec![rp(&r, p), ib(1)]; // t + r
262    let core = poly_mul(
263        &poly_mul(&lin(c[0].clone()), &lin(c[1].clone()), p),
264        &lin(c[2].clone()),
265        p,
266    ); // ∏(t+cᵢ)
267    MatchedPairGlue {
268        sextic,
269        e1: poly_mul(&lin(ib(2)), &core, p),  // (t+2)·∏(t+cᵢ)
270        e2: poly_mul(&lin(ib(-2)), &core, p), // (t−2)·∏(t+cᵢ)
271        p: p.clone(),
272    }
273}
274
275/// Whether the genus-2 curve with these six Weierstrass points has a **reducible** Jacobian (splits as a
276/// product of elliptic curves) — decided by the Richelot split-test: some `(2,2)`-splitting has `δ = 0`. This
277/// is exactly the decision the Castryck–Decru per-digit oracle makes — a correct guess yields a *splitting*
278/// abelian surface, a wrong one an indecomposable genus-2 Jacobian.
279pub fn surface_is_reducible(roots: &[BigInt; 6], p: &BigInt) -> bool {
280    find_split_neighbour(roots, p).is_some()
281}
282
283/// **The per-digit split oracle.** Given the candidate surface for each branch of the recursive descent (one
284/// per guessed `ℓ`-adic digit — in the full attack each is built by Kani gluing from the torsion images and
285/// the guess), return the index of the branch whose surface **splits**. The split-test prunes every branch
286/// but the consistent one — the `is_split`/Kani step of Castryck–Decru, as a wired per-digit selector.
287pub fn select_splitting_branch(branches: &[[BigInt; 6]], p: &BigInt) -> Option<usize> {
288    branches.iter().position(|r| surface_is_reducible(r, p))
289}
290
291// ---- Genus-2 Jacobian arithmetic: Mumford representation + Cantor's algorithm ----------------------
292//
293// A degree-2g+1 (imaginary) hyperelliptic curve C: y² = f(x), deg f = 5, has genus 2. A divisor class in
294// Jac(C) is a Mumford pair (u, v): u monic, deg u ≤ 2, deg v < deg u, and u | (f − v²). This is the concrete
295// point-arithmetic machinery on the abelian surface — the substrate a Richelot isogeny would act on, and the
296// validator that would judge any surface-kernel construction (`#Jac · D = 0` for every class D).
297
298fn pdeg(a: &[BigInt]) -> isize {
299    (0..a.len())
300        .rev()
301        .find(|&i| !a[i].is_zero())
302        .map(|i| i as isize)
303        .unwrap_or(-1)
304}
305fn padd(a: &[BigInt], b: &[BigInt], p: &BigInt) -> Vec<BigInt> {
306    let n = a.len().max(b.len());
307    poly_trim(
308        (0..n)
309            .map(|i| am(a.get(i).unwrap_or(&ib(0)), b.get(i).unwrap_or(&ib(0)), p))
310            .collect(),
311    )
312}
313fn psub(a: &[BigInt], b: &[BigInt], p: &BigInt) -> Vec<BigInt> {
314    poly_trim(poly_sub(a, b, p))
315}
316fn pmul(a: &[BigInt], b: &[BigInt], p: &BigInt) -> Vec<BigInt> {
317    poly_trim(poly_mul(a, b, p))
318}
319fn pscale(a: &[BigInt], s: &BigInt, p: &BigInt) -> Vec<BigInt> {
320    poly_trim(a.iter().map(|c| mm(c, s, p)).collect())
321}
322fn pneg(a: &[BigInt], p: &BigInt) -> Vec<BigInt> {
323    pscale(a, &sm(&ib(0), &ib(1), p), p)
324}
325fn pmonic(a: &[BigInt], p: &BigInt) -> Vec<BigInt> {
326    let d = pdeg(a);
327    if d < 0 {
328        return vec![ib(0)];
329    }
330    pscale(a, &mod_inverse(&a[d as usize], p).unwrap(), p)
331}
332/// Polynomial long division: `a = q·b + r`, `deg r < deg b`. Returns `(q, r)`.
333fn pdivmod(a: &[BigInt], b: &[BigInt], p: &BigInt) -> (Vec<BigInt>, Vec<BigInt>) {
334    let db = pdeg(b);
335    assert!(db >= 0, "division by the zero polynomial");
336    let binv = mod_inverse(&b[db as usize], p).unwrap();
337    let mut r = poly_trim(a.to_vec());
338    let mut q = vec![ib(0)];
339    while pdeg(&r) >= db {
340        let dr = pdeg(&r);
341        let shift = (dr - db) as usize;
342        let coef = mm(&r[dr as usize], &binv, p);
343        if q.len() <= shift {
344            q.resize(shift + 1, ib(0));
345        }
346        q[shift] = am(&q[shift], &coef, p);
347        let mut sub = vec![ib(0); shift];
348        sub.extend(b.iter().map(|c| mm(c, &coef, p)));
349        r = psub(&r, &sub, p);
350    }
351    (poly_trim(q), poly_trim(r))
352}
353fn pmod(a: &[BigInt], m: &[BigInt], p: &BigInt) -> Vec<BigInt> {
354    pdivmod(a, m, p).1
355}
356fn pdiv_exact(a: &[BigInt], b: &[BigInt], p: &BigInt) -> Vec<BigInt> {
357    pdivmod(a, b, p).0
358}
359/// Extended gcd of polynomials: returns `(g, s, t)` with `s·a + t·b = g`, `g` monic.
360fn pext_gcd(a: &[BigInt], b: &[BigInt], p: &BigInt) -> (Vec<BigInt>, Vec<BigInt>, Vec<BigInt>) {
361    let (mut r0, mut r1) = (poly_trim(a.to_vec()), poly_trim(b.to_vec()));
362    let (mut s0, mut s1) = (vec![ib(1)], vec![ib(0)]);
363    let (mut t0, mut t1) = (vec![ib(0)], vec![ib(1)]);
364    while pdeg(&r1) >= 0 {
365        let (q, r) = pdivmod(&r0, &r1, p);
366        r0 = r1;
367        r1 = r;
368        let ns = psub(&s0, &pmul(&q, &s1, p), p);
369        s0 = s1;
370        s1 = ns;
371        let nt = psub(&t0, &pmul(&q, &t1, p), p);
372        t0 = t1;
373        t1 = nt;
374    }
375    let d = pdeg(&r0);
376    if d > 0 || (d == 0 && r0[0] != ib(1)) {
377        let inv = mod_inverse(&r0[d as usize], p).unwrap();
378        r0 = pscale(&r0, &inv, p);
379        s0 = pscale(&s0, &inv, p);
380        t0 = pscale(&t0, &inv, p);
381    }
382    (r0, s0, t0)
383}
384
385/// A divisor class in `Jac(C)` in Mumford form `(u, v)`.
386#[derive(Clone, Debug, PartialEq, Eq)]
387pub struct Mumford {
388    pub u: Vec<BigInt>,
389    pub v: Vec<BigInt>,
390}
391
392/// The identity divisor class `(1, 0)`.
393pub fn jac_identity() -> Mumford {
394    Mumford {
395        u: vec![ib(1)],
396        v: vec![ib(0)],
397    }
398}
399
400/// `−D = (u, −v)`.
401pub fn jac_negate(d: &Mumford, p: &BigInt) -> Mumford {
402    Mumford {
403        u: d.u.clone(),
404        v: pmod(&pneg(&d.v, p), &d.u, p),
405    }
406}
407
408/// Reduce a (possibly unreduced) Mumford pair to `deg u ≤ 2`.
409fn jac_reduce(mut u: Vec<BigInt>, mut v: Vec<BigInt>, f: &[BigInt], p: &BigInt) -> Mumford {
410    while pdeg(&u) > 2 {
411        let up = pdiv_exact(&psub(f, &pmul(&v, &v, p), p), &u, p);
412        let vp = pmod(&pneg(&v, p), &up, p);
413        u = up;
414        v = vp;
415    }
416    let um = pmonic(&u, p);
417    let vm = pmod(&v, &um, p);
418    Mumford { u: um, v: vm }
419}
420
421/// Cantor's algorithm: add two divisor classes on `C: y² = f(x)` (genus 2, `char ≠ 2`).
422pub fn cantor_add(d1: &Mumford, d2: &Mumford, f: &[BigInt], p: &BigInt) -> Mumford {
423    let (u1, v1, u2, v2) = (&d1.u, &d1.v, &d2.u, &d2.v);
424    // d = gcd(u1, u2, v1+v2) = s1·u1 + s2·u2 + s3·(v1+v2).
425    let (g1, e1, e2) = pext_gcd(u1, u2, p);
426    let vsum = padd(v1, v2, p);
427    let (d, c1, c2) = pext_gcd(&g1, &vsum, p);
428    let s1 = pmul(&c1, &e1, p);
429    let s2 = pmul(&c1, &e2, p);
430    let s3 = c2;
431    // u = u1·u2 / d², v = (s1·u1·v2 + s2·u2·v1 + s3·(v1·v2 + f)) / d  mod u.
432    let u = pdiv_exact(&pmul(u1, u2, p), &pmul(&d, &d, p), p);
433    let num = padd(
434        &padd(
435            &pmul(&pmul(&s1, u1, p), v2, p),
436            &pmul(&pmul(&s2, u2, p), v1, p),
437            p,
438        ),
439        &pmul(&s3, &padd(&pmul(v1, v2, p), f, p), p),
440        p,
441    );
442    let v = pmod(&pdiv_exact(&num, &d, p), &u, p);
443    jac_reduce(u, v, f, p)
444}
445
446/// Scalar multiple `[n]·D` by double-and-add.
447pub fn jac_scalar_mul(n: u128, d: &Mumford, f: &[BigInt], p: &BigInt) -> Mumford {
448    let mut result = jac_identity();
449    let mut base = d.clone();
450    let mut k = n;
451    while k > 0 {
452        if k & 1 == 1 {
453            result = cantor_add(&result, &base, f, p);
454        }
455        base = cantor_add(&base, &base, f, p);
456        k >>= 1;
457    }
458    result
459}
460
461/// The order of a divisor class `D` in `Jac(C)` — the least `n | group_order` with `[n]·D = 0`. Computed by
462/// stripping each prime of `group_order` as far as still annihilates `D`.
463pub fn jac_element_order(d: &Mumford, group_order: u128, f: &[BigInt], p: &BigInt) -> u128 {
464    let id = jac_identity();
465    let mut primes = Vec::new();
466    let (mut m, mut q) = (group_order, 2u128);
467    while q * q <= m {
468        if m % q == 0 {
469            primes.push(q);
470            while m % q == 0 {
471                m /= q;
472            }
473        }
474        q += 1;
475    }
476    if m > 1 {
477        primes.push(m);
478    }
479    let mut n = group_order;
480    for &pr in &primes {
481        while n % pr == 0 && jac_scalar_mul(n / pr, d, f, p) == id {
482            n /= pr;
483        }
484    }
485    n
486}
487
488/// Legendre symbol `χ_p(a) ∈ {−1, 0, 1}` by Euler's criterion.
489fn legendre(a: &BigInt, p: &BigInt) -> i64 {
490    let ar = rp(a, p);
491    if ar.is_zero() {
492        return 0;
493    }
494    let e = p.sub(&ib(1)).div_rem(&ib(2)).map(|(q, _)| q).unwrap();
495    if modpow(&ar, &e, p) == ib(1) {
496        1
497    } else {
498        -1
499    }
500}
501
502/// `#{(x,y) ∈ 𝔽_p² : y² = f(x)} + inf` — the `𝔽_p`-point count of `y² = f(x)` (`inf` = points at infinity).
503pub fn count_curve_fp(f: &[BigInt], p: &BigInt, inf: i64) -> i64 {
504    let pu = p.to_i64().unwrap();
505    (0..pu).fold(inf, |n, x| n + 1 + legendre(&poly_eval(f, &ib(x), p), p))
506}
507
508/// The `𝔽_{p²}`-point count of `y² = f(x)` (`f` with `𝔽_p` coefficients), using Euler's criterion in
509/// `𝔽_{p²}` for the quadratic character.
510fn count_curve_fp2(f: &[BigInt], p: &BigInt, inf: i64) -> i64 {
511    use crate::fp2::{fp2_add, fp2_const, fp2_is_zero, fp2_mul, fp2_pow, Fp2};
512    let pu = p.to_i64().unwrap();
513    let exp = (((pu as i128) * (pu as i128) - 1) / 2) as u64;
514    let coeffs: Vec<Fp2> = f.iter().map(|c| (rp(c, p), ib(0))).collect();
515    let mut n = inf;
516    for a in 0..pu {
517        for b in 0..pu {
518            let beta: Fp2 = (ib(a), ib(b));
519            let mut acc = fp2_const(0, p);
520            for c in coeffs.iter().rev() {
521                acc = fp2_add(&fp2_mul(&acc, &beta, p), c, p);
522            }
523            n += 1 + if fp2_is_zero(&acc) {
524                0
525            } else if fp2_pow(&acc, exp, p) == fp2_const(1, p) {
526                1
527            } else {
528                -1
529            };
530        }
531    }
532    n
533}
534
535/// `#Jac(C)(𝔽_p)` for the genus-2 curve `C: y² = f(x)` (deg f = 6, monic), from its L-polynomial via the
536/// point counts over `𝔽_p` and `𝔽_{p²}`. For a split Jacobian `Jac(C) ~ E₁ × E₂` this equals `#E₁·#E₂` (Tate:
537/// isogenous abelian varieties over `𝔽_p` share their order) — the exact point-count validation of a gluing.
538pub fn genus2_jacobian_order(sextic: &[BigInt], p: &BigInt) -> i128 {
539    let pu = p.to_i64().unwrap() as i128;
540    let n1 = count_curve_fp(sextic, p, 2) as i128; // monic sextic ⟹ 2 points at infinity
541    let n2 = count_curve_fp2(sextic, p, 2) as i128;
542    let t1 = (pu + 1) - n1; // Σ αᵢ
543    let t2 = (pu * pu + 1) - n2; // Σ αᵢ²
544                                 // #Jac = ∏(1 − αᵢ) = 1 + p² − (1+p)·t₁ + (t₁² − t₂)/2  (Weil functional equation: e₃ = p·e₁, e₄ = p²).
545    1 + pu * pu - (1 + pu) * t1 + (t1 * t1 - t2) / 2
546}
547
548/// `#Jac(C)(𝔽_p)` for `C: y² = f(x)` of any degree 5 or 6, with the correct number of points at infinity:
549/// deg 5 ⟹ 1; deg 6 ⟹ 2 if the leading coefficient is a square (over `𝔽_p`), else 0. Over `𝔽_{p²}` every
550/// `𝔽_p` leading coefficient is a square, so the count there is 2 (deg 6) or 1 (deg 5). Needed to compare a
551/// Richelot dual (a non-monic, possibly quadratic-twisted sextic) against its domain.
552pub fn genus2_jacobian_order_general(f: &[BigInt], p: &BigInt) -> i128 {
553    let deg = pdeg(f);
554    let pu = p.to_i64().unwrap() as i128;
555    let inf_p = if deg % 2 == 1 {
556        1
557    } else if legendre(&f[deg as usize], p) == 1 {
558        2
559    } else {
560        0
561    };
562    let inf_p2 = if deg % 2 == 1 { 1 } else { 2 };
563    let n1 = count_curve_fp(f, p, inf_p) as i128;
564    let n2 = count_curve_fp2(f, p, inf_p2) as i128;
565    let t1 = (pu + 1) - n1;
566    let t2 = (pu * pu + 1) - n2;
567    1 + pu * pu - (1 + pu) * t1 + (t1 * t1 - t2) / 2
568}
569
570/// A square root of `a` in `𝔽_p` for `p ≡ 3 (mod 4)`, if one exists.
571fn fp_sqrt(a: &BigInt, p: &BigInt) -> Option<BigInt> {
572    let a = rp(a, p);
573    if a.is_zero() {
574        return Some(ib(0));
575    }
576    let exp = p.add(&ib(1)).div_rem(&ib(4)).map(|(q, _)| q)?;
577    let r = modpow(&a, &exp, p);
578    (mm(&r, &r, p) == a).then_some(r)
579}
580
581/// The two roots of a quadratic `g₀ + g₁x + g₂x²` over `𝔽_p`, when they are rational (`p ≡ 3 mod 4`).
582fn quad_roots(q: &[BigInt], p: &BigInt) -> Option<[BigInt; 2]> {
583    if q.len() < 3 || q[2].is_zero() {
584        return None;
585    }
586    let (c0, c1, c2) = (&q[0], &q[1], &q[2]);
587    let disc = sm(&mm(c1, c1, p), &mm(&ib(4), &mm(c0, c2, p), p), p);
588    let sq = fp_sqrt(&disc, p)?;
589    let inv = mod_inverse(&mm(&ib(2), c2, p), p)?;
590    let neg_b = sm(&ib(0), c1, p);
591    Some([
592        mm(&sm(&neg_b, &sq, p), &inv, p),
593        mm(&am(&neg_b, &sq, p), &inv, p),
594    ])
595}
596
597/// The six Weierstrass points of a Richelot codomain — the roots of its three dual quadratics — when they
598/// are all rational over `𝔽_p`. Returning `None` means the codomain's 2-torsion lives in `𝔽_{p²}`, so the
599/// chain-walk over the prime field cannot continue through that neighbour (the lift to `𝔽_{p²}` removes this
600/// obstruction, at the cost of the extension arithmetic).
601fn codomain_roots(dual: &[Vec<BigInt>; 3], p: &BigInt) -> Option<[BigInt; 6]> {
602    let a = quad_roots(&dual[0], p)?;
603    let b = quad_roots(&dual[1], p)?;
604    let c = quad_roots(&dual[2], p)?;
605    Some([
606        a[0].clone(),
607        a[1].clone(),
608        b[0].clone(),
609        b[1].clone(),
610        c[0].clone(),
611        c[1].clone(),
612    ])
613}
614
615/// Walk chains of Richelot (2,2)-isogenies to depth `depth` (a chain of `depth + 1` steps), returning the
616/// sequence of neighbour indices that first reaches a **split** (reducible) surface, or `None` if none does
617/// within the bound. This is the recursive form of the Castryck–Decru search across the (2,2)-graph: from
618/// each node it forms the codomain, extracts its Weierstrass points, and recurses. Neighbours whose codomain
619/// 2-torsion escapes to `𝔽_{p²}` are skipped over the prime field.
620pub fn richelot_chain(roots: &[BigInt; 6], depth: usize, p: &BigInt) -> Option<Vec<usize>> {
621    for (i, g) in richelot_partitions(roots, p).into_iter().enumerate() {
622        let r = richelot(&g, p);
623        if r.is_split() {
624            return Some(vec![i]);
625        }
626        if depth > 0 {
627            if let Some(next) = codomain_roots(&r.dual, p) {
628                if let Some(mut path) = richelot_chain(&next, depth - 1, p) {
629                    path.insert(0, i);
630                    return Some(path);
631                }
632            }
633        }
634    }
635    None
636}
637
638/// The outcome of following a guided Richelot chain.
639#[derive(Clone, Debug, PartialEq, Eq)]
640pub enum GuidedWalk {
641    /// A split (reducible) surface was reached at this step index along the path.
642    SplitAt(usize),
643    /// The path completed without splitting; the six Weierstrass points of the final surface.
644    Ended([BigInt; 6]),
645    /// The chain left the prime field (a codomain's 2-torsion is in `𝔽_{p²}`) at this step, or the index
646    /// was out of range — the prime-field walk cannot continue.
647    Stuck(usize),
648}
649
650/// Follow a **guided** chain of Richelot isogenies: apply the neighbour named by each index in `path` in
651/// turn, reporting the first split. In the full Castryck–Decru attack the path is not free — it is *dictated
652/// by the torsion images* `φ(P), φ(Q)`: the kernel of each (2,2)-step is the image of a prescribed torsion
653/// subgroup, so the walk is a single guided line rather than the 15-way exhaustive tree. This function is
654/// that guided line; deriving `path` from the torsion images is the remaining Castryck–Decru integration.
655pub fn guided_chain(roots: &[BigInt; 6], path: &[usize], p: &BigInt) -> GuidedWalk {
656    let mut cur = roots.clone();
657    for (step, &idx) in path.iter().enumerate() {
658        let parts = richelot_partitions(&cur, p);
659        if idx >= parts.len() {
660            return GuidedWalk::Stuck(step);
661        }
662        let r = richelot(&parts[idx], p);
663        if r.is_split() {
664            return GuidedWalk::SplitAt(step);
665        }
666        match codomain_roots(&r.dual, p) {
667            Some(next) => cur = next,
668            None => return GuidedWalk::Stuck(step),
669        }
670    }
671    GuidedWalk::Ended(cur)
672}
673
674#[cfg(test)]
675#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/hyperelliptic/tests.rs"]
676mod tests;