Skip to main content

logicaffeine_proof/
fp2.rs

1//! # 𝔽_{p²} arithmetic and the supersingular isogeny graph
2//!
3//! The quadratic extension `𝔽_{p²} = 𝔽_p[i]/(i²+1)` (for `p ≡ 3 (mod 4)`, so `−1` is a non-residue and
4//! `i² = −1` is irreducible) is where the supersingular curves live — and so where CSIDH, SIKE, and the
5//! 2022 Castryck–Decru break happen. This module gives the field arithmetic and builds the **supersingular
6//! ℓ=2 isogeny graph**: vertices are supersingular j-invariants in `𝔽_{p²}`, edges the 2-isogenies. We
7//! build it not through Vélu but through the classical **level-2 modular polynomial** `Φ₂(X,Y)` — the three
8//! roots of `Φ₂(j, ·)` are exactly the j-invariants 2-isogenous to `j`. So the whole graph is field
9//! arithmetic + cubic root-finding + a breadth-first walk from a known supersingular vertex (`j = 1728`,
10//! supersingular whenever `p ≡ 3 (mod 4)`). The result is a 3-regular **Ramanujan graph** whose size is the
11//! supersingular mass `⌊p/12⌋ + ε`.
12
13use crate::factor::mod_inverse;
14use logicaffeine_base::BigInt;
15
16/// An element `a + b·i` of `𝔽_{p²} = 𝔽_p[i]/(i²+1)`.
17pub type Fp2 = (BigInt, BigInt);
18
19#[inline]
20fn ib(x: i64) -> BigInt {
21    BigInt::from_i64(x)
22}
23
24#[inline]
25fn rem_pos(a: &BigInt, p: &BigInt) -> BigInt {
26    let r = a.div_rem(p).map(|(_, r)| r).unwrap_or_else(|| a.clone());
27    if r.is_negative() {
28        r.add(p)
29    } else {
30        r
31    }
32}
33
34#[inline]
35fn m(a: &BigInt, b: &BigInt, p: &BigInt) -> BigInt {
36    rem_pos(&a.mul(b), p)
37}
38#[inline]
39fn s(a: &BigInt, b: &BigInt, p: &BigInt) -> BigInt {
40    rem_pos(&a.sub(b), p)
41}
42#[inline]
43fn a_(a: &BigInt, b: &BigInt, p: &BigInt) -> BigInt {
44    rem_pos(&a.add(b), p)
45}
46
47/// A rational constant `k` as an element of `𝔽_{p²}`.
48pub fn fp2_const(k: i64, p: &BigInt) -> Fp2 {
49    (rem_pos(&ib(k), p), ib(0))
50}
51
52pub fn fp2_add(x: &Fp2, y: &Fp2, p: &BigInt) -> Fp2 {
53    (a_(&x.0, &y.0, p), a_(&x.1, &y.1, p))
54}
55pub fn fp2_sub(x: &Fp2, y: &Fp2, p: &BigInt) -> Fp2 {
56    (s(&x.0, &y.0, p), s(&x.1, &y.1, p))
57}
58pub fn fp2_neg(x: &Fp2, p: &BigInt) -> Fp2 {
59    (s(&ib(0), &x.0, p), s(&ib(0), &x.1, p))
60}
61
62/// `(a+bi)(c+di) = (ac − bd) + (ad + bc)i`.
63pub fn fp2_mul(x: &Fp2, y: &Fp2, p: &BigInt) -> Fp2 {
64    let ac = m(&x.0, &y.0, p);
65    let bd = m(&x.1, &y.1, p);
66    let ad = m(&x.0, &y.1, p);
67    let bc = m(&x.1, &y.0, p);
68    (s(&ac, &bd, p), a_(&ad, &bc, p))
69}
70
71/// `(a+bi)⁻¹ = (a − bi)/(a² + b²)`. `None` only for `0`.
72pub fn fp2_inv(x: &Fp2, p: &BigInt) -> Option<Fp2> {
73    let norm = a_(&m(&x.0, &x.0, p), &m(&x.1, &x.1, p), p);
74    let ninv = mod_inverse(&norm, p)?;
75    Some((m(&x.0, &ninv, p), m(&s(&ib(0), &x.1, p), &ninv, p)))
76}
77
78pub fn fp2_is_zero(x: &Fp2) -> bool {
79    x.0.is_zero() && x.1.is_zero()
80}
81
82// ---- The level-2 modular polynomial and the supersingular graph -------------------------------------
83
84/// `Φ₂(j, Y)` as the cubic `c₃Y³ + c₂Y² + c₁Y + c₀` over `𝔽_{p²}` (returned low-degree first). The classical
85/// polynomial `Φ₂(X,Y) = X³ + Y³ − X²Y² + 1488(X²Y+XY²) − 162000(X²+Y²) + 40773375·XY + 8748000000(X+Y) −
86/// 157464000000000`, with `X = j` fixed.
87fn phi2_in_y(j: &Fp2, p: &BigInt) -> [Fp2; 4] {
88    let j2 = fp2_mul(j, j, p);
89    let j3 = fp2_mul(&j2, j, p);
90    let k = |c: i64| fp2_const(c, p);
91    let c3 = k(1);
92    // c2 = −j² + 1488·j − 162000
93    let c2 = fp2_sub(
94        &fp2_add(&fp2_neg(&j2, p), &fp2_mul(&k(1488), j, p), p),
95        &k(162000),
96        p,
97    );
98    // c1 = 1488·j² + 40773375·j + 8748000000
99    let c1 = fp2_add(
100        &fp2_add(&fp2_mul(&k(1488), &j2, p), &fp2_mul(&k(40773375), j, p), p),
101        &k(8_748_000_000),
102        p,
103    );
104    // c0 = j³ − 162000·j² + 8748000000·j − 157464000000000
105    let c0 = fp2_sub(
106        &fp2_add(
107            &fp2_sub(&j3, &fp2_mul(&k(162000), &j2, p), p),
108            &fp2_mul(&k(8_748_000_000), j, p),
109            p,
110        ),
111        &k(157_464_000_000_000),
112        p,
113    );
114    [c0, c1, c2, c3]
115}
116
117/// Evaluate a polynomial (low-degree-first coefficients) at `y` over `𝔽_{p²}` by Horner's rule.
118fn poly_eval(coeffs: &[Fp2], y: &Fp2, p: &BigInt) -> Fp2 {
119    let mut acc = fp2_const(0, p);
120    for c in coeffs.iter().rev() {
121        acc = fp2_add(&fp2_mul(&acc, y, p), c, p);
122    }
123    acc
124}
125
126/// Divide a polynomial by `(Y − r)` over `𝔽_{p²}` (synthetic division); returns `(quotient, remainder)`.
127fn poly_div_linear(coeffs: &[Fp2], r: &Fp2, p: &BigInt) -> (Vec<Fp2>, Fp2) {
128    let mut q = vec![fp2_const(0, p); coeffs.len().saturating_sub(1)];
129    let mut carry = fp2_const(0, p);
130    for k in (0..coeffs.len()).rev() {
131        let cur = fp2_add(&coeffs[k], &fp2_mul(&carry, r, p), p);
132        if k == 0 {
133            return (q, cur); // remainder
134        }
135        q[k - 1] = cur.clone();
136        carry = cur;
137    }
138    (q, fp2_const(0, p))
139}
140
141/// All elements of `𝔽_{p²}` (small `p` only).
142fn fp2_elements(p: &BigInt) -> Vec<Fp2> {
143    let pu = p.to_i64().expect("small prime") as i64;
144    let mut v = Vec::new();
145    for a in 0..pu {
146        for b in 0..pu {
147            v.push((ib(a), ib(b)));
148        }
149    }
150    v
151}
152
153/// The roots of a cubic over `𝔽_{p²}`, each paired with its multiplicity (found by brute force over the
154/// field, then divided out). For a supersingular `j`, `Φ₂(j,·)` splits completely, so the multiplicities
155/// sum to 3.
156fn cubic_roots(coeffs: &[Fp2; 4], p: &BigInt) -> Vec<(Fp2, usize)> {
157    let mut out = Vec::new();
158    for y in fp2_elements(p) {
159        if fp2_is_zero(&poly_eval(coeffs, &y, p)) {
160            // multiplicity by repeated division
161            let mut poly: Vec<Fp2> = coeffs.to_vec();
162            let mut mult = 0usize;
163            loop {
164                let (q, rem) = poly_div_linear(&poly, &y, p);
165                if !fp2_is_zero(&rem) {
166                    break;
167                }
168                mult += 1;
169                poly = q;
170                if poly.len() <= 1 {
171                    break;
172                }
173            }
174            out.push((y, mult));
175        }
176    }
177    out
178}
179
180/// A vertex of the supersingular isogeny graph: a j-invariant and its 2-isogenous neighbours (as a
181/// multiset — a double root of `Φ₂` is a double edge).
182#[derive(Clone, Debug)]
183pub struct SsVertex {
184    pub j: Fp2,
185    pub neighbors: Vec<Fp2>,
186}
187
188/// Build the **supersingular ℓ=2 isogeny graph** over `𝔽_{p²}` (requires `p ≡ 3 (mod 4)`). Breadth-first
189/// from the supersingular vertex `j = 1728`, following the roots of `Φ₂(j,·)`. Because the graph is
190/// connected, this reaches *every* supersingular j-invariant; its size is the supersingular mass
191/// `⌊p/12⌋ + ε` and every vertex has out-degree 3. `None` if `p ≢ 3 (mod 4)`.
192pub fn supersingular_graph(p: &BigInt) -> Option<Vec<SsVertex>> {
193    if rem_pos(p, &ib(4)) != ib(3) {
194        return None;
195    }
196    let start = fp2_const(1728, p);
197    let mut visited: Vec<Fp2> = Vec::new();
198    let mut queue: Vec<Fp2> = vec![start];
199    let mut graph: Vec<SsVertex> = Vec::new();
200    while let Some(j) = queue.pop() {
201        if visited.iter().any(|v| v == &j) {
202            continue;
203        }
204        visited.push(j.clone());
205        let mut neighbors = Vec::new();
206        for (root, mult) in cubic_roots(&phi2_in_y(&j, p), p) {
207            for _ in 0..mult {
208                neighbors.push(root.clone());
209            }
210            if !visited.iter().any(|v| v == &root) && !queue.iter().any(|v| v == &root) {
211                queue.push(root);
212            }
213        }
214        graph.push(SsVertex { j, neighbors });
215    }
216    Some(graph)
217}
218
219// ---- Elliptic curves over 𝔽_{p²} — SIKE scale ------------------------------------------------------
220//
221// Supersingular curves, and their FULL ℓ-torsion (`E[ℓ] ≅ (ℤ/ℓ)²`), are rational only over the quadratic
222// extension: `#E(𝔽_{p²}) = (p ∓ 1)²`, so `E(𝔽_{p²}) ≅ (ℤ/(p∓1))²` carries the torsion SIKE's basis lives
223// in. This is the concrete curve layer over 𝔽_{p²}: the same Weierstrass group law as over the prime
224// field, with every coordinate an `Fp2`.
225
226/// A Weierstrass curve `y² = x³ + ax + b` over `𝔽_{p²}`.
227#[derive(Clone, Debug, PartialEq, Eq)]
228pub struct Curve2 {
229    pub a: Fp2,
230    pub b: Fp2,
231    pub p: BigInt,
232}
233
234/// An affine point over `𝔽_{p²}`, or the identity.
235#[derive(Clone, Debug, PartialEq, Eq)]
236pub enum Point2 {
237    Infinity,
238    Affine(Fp2, Fp2),
239}
240
241impl Curve2 {
242    pub fn new(a: Fp2, b: Fp2, p: BigInt) -> Curve2 {
243        Curve2 { a, b, p }
244    }
245
246    pub fn is_on_curve(&self, pt: &Point2) -> bool {
247        match pt {
248            Point2::Infinity => true,
249            Point2::Affine(x, y) => {
250                let lhs = fp2_mul(y, y, &self.p);
251                let x3 = fp2_mul(&fp2_mul(x, x, &self.p), x, &self.p);
252                let rhs = fp2_add(
253                    &fp2_add(&x3, &fp2_mul(&self.a, x, &self.p), &self.p),
254                    &self.b,
255                    &self.p,
256                );
257                lhs == rhs
258            }
259        }
260    }
261
262    pub fn negate(&self, pt: &Point2) -> Point2 {
263        match pt {
264            Point2::Infinity => Point2::Infinity,
265            Point2::Affine(x, y) => Point2::Affine(x.clone(), fp2_neg(y, &self.p)),
266        }
267    }
268
269    pub fn add(&self, p1: &Point2, p2: &Point2) -> Point2 {
270        match (p1, p2) {
271            (Point2::Infinity, _) => p2.clone(),
272            (_, Point2::Infinity) => p1.clone(),
273            (Point2::Affine(x1, y1), Point2::Affine(x2, y2)) => {
274                if x1 == x2 {
275                    if fp2_is_zero(&fp2_add(y1, y2, &self.p)) {
276                        return Point2::Infinity; // P = −Q
277                    }
278                    return self.double(p1); // P = Q
279                }
280                let den =
281                    fp2_inv(&fp2_sub(x2, x1, &self.p), &self.p).expect("distinct x invertible");
282                let lam = fp2_mul(&fp2_sub(y2, y1, &self.p), &den, &self.p);
283                let x3 = fp2_sub(
284                    &fp2_sub(&fp2_mul(&lam, &lam, &self.p), x1, &self.p),
285                    x2,
286                    &self.p,
287                );
288                let y3 = fp2_sub(
289                    &fp2_mul(&lam, &fp2_sub(x1, &x3, &self.p), &self.p),
290                    y1,
291                    &self.p,
292                );
293                Point2::Affine(x3, y3)
294            }
295        }
296    }
297
298    pub fn double(&self, pt: &Point2) -> Point2 {
299        match pt {
300            Point2::Infinity => Point2::Infinity,
301            Point2::Affine(x, y) => {
302                if fp2_is_zero(y) {
303                    return Point2::Infinity;
304                }
305                let num = fp2_add(
306                    &fp2_mul(&fp2_const(3, &self.p), &fp2_mul(x, x, &self.p), &self.p),
307                    &self.a,
308                    &self.p,
309                );
310                let den = fp2_inv(&fp2_mul(&fp2_const(2, &self.p), y, &self.p), &self.p)
311                    .expect("2y invertible");
312                let lam = fp2_mul(&num, &den, &self.p);
313                let x3 = fp2_sub(
314                    &fp2_mul(&lam, &lam, &self.p),
315                    &fp2_mul(&fp2_const(2, &self.p), x, &self.p),
316                    &self.p,
317                );
318                let y3 = fp2_sub(
319                    &fp2_mul(&lam, &fp2_sub(x, &x3, &self.p), &self.p),
320                    y,
321                    &self.p,
322                );
323                Point2::Affine(x3, y3)
324            }
325        }
326    }
327
328    /// Scalar multiplication `k·P` by double-and-add (`k ≥ 0`).
329    pub fn mul(&self, k: &BigInt, pt: &Point2) -> Point2 {
330        let mut result = Point2::Infinity;
331        let mut addend = pt.clone();
332        let (_, bytes) = k.to_le_bytes();
333        for byte in bytes {
334            for bit in 0..8 {
335                if (byte >> bit) & 1 == 1 {
336                    result = self.add(&result, &addend);
337                }
338                addend = self.double(&addend);
339            }
340        }
341        result
342    }
343
344    /// The j-invariant in `𝔽_{p²}` — the supersingular-graph vertex this curve sits at.
345    pub fn j_invariant(&self) -> Option<Fp2> {
346        let a3 = fp2_mul(&fp2_mul(&self.a, &self.a, &self.p), &self.a, &self.p);
347        let four_a3 = fp2_mul(&fp2_const(4, &self.p), &a3, &self.p);
348        let disc = fp2_add(
349            &four_a3,
350            &fp2_mul(
351                &fp2_const(27, &self.p),
352                &fp2_mul(&self.b, &self.b, &self.p),
353                &self.p,
354            ),
355            &self.p,
356        );
357        if fp2_is_zero(&disc) {
358            return None;
359        }
360        Some(fp2_mul(
361            &fp2_mul(&fp2_const(1728, &self.p), &four_a3, &self.p),
362            &fp2_inv(&disc, &self.p)?,
363            &self.p,
364        ))
365    }
366}
367
368// ---- Square roots, torsion, Vélu, and the Weil pairing OVER 𝔽_{p²} (SIKE scale) --------------------
369
370/// `√a` in `𝔽_p` for `p ≡ 3 (mod 4)`: `a^{(p+1)/4}`; `None` for a non-residue.
371fn fp_sqrt(a: &BigInt, p: &BigInt) -> Option<BigInt> {
372    let ap = rem_pos(a, p);
373    if ap.is_zero() {
374        return Some(ib(0));
375    }
376    let exp = p.add(&ib(1)).div_rem(&ib(4))?.0;
377    let r = crate::factor::modpow(&ap, &exp, p);
378    (m(&r, &r, p) == ap).then_some(r)
379}
380
381/// `√α` in `𝔽_{p²}` (`p ≡ 3 mod 4`), or `None` if `α` is not a square. From `β² = α` with `β = x + yi`:
382/// `x² − y² = a`, `2xy = b`, whence `x² = (a ± √(a²+b²))/2`; a final `β² = α` check makes it exact.
383pub fn fp2_sqrt(alpha: &Fp2, p: &BigInt) -> Option<Fp2> {
384    let (a, b) = (&alpha.0, &alpha.1);
385    if b.is_zero() {
386        if let Some(r) = fp_sqrt(a, p) {
387            return Some((r, ib(0)));
388        }
389        return fp_sqrt(&s(&ib(0), a, p), p).map(|r| (ib(0), r)); // a non-residue ⟹ √a = √(−a)·i
390    }
391    let norm = a_(&m(a, a, p), &m(b, b, p), p);
392    let sn = fp_sqrt(&norm, p)?;
393    let inv2 = crate::factor::mod_inverse(&ib(2), p)?;
394    for signed in [sn.clone(), s(&ib(0), &sn, p)] {
395        let t = m(&a_(a, &signed, p), &inv2, p); // (a ± √N)/2
396        if let Some(x) = fp_sqrt(&t, p) {
397            if x.is_zero() {
398                continue;
399            }
400            let y = m(b, &crate::factor::mod_inverse(&m(&ib(2), &x, p), p)?, p);
401            let cand = (x, y);
402            if fp2_mul(&cand, &cand, p) == *alpha {
403                return Some(cand);
404            }
405        }
406    }
407    None
408}
409
410/// Every affine point of a curve over `𝔽_{p²}`, found by an `𝔽_{p²}` square root per x — `O(p²)`, not the
411/// `O(p⁴)` of brute enumeration, so it reaches SIKE-shaped primes.
412fn points_on_curve2(c: &Curve2) -> Vec<Point2> {
413    let pu = c.p.to_i64().expect("small prime");
414    let mut v = vec![Point2::Infinity];
415    for xa in 0..pu {
416        for xb in 0..pu {
417            let x = (ib(xa), ib(xb));
418            let x3 = fp2_mul(&fp2_mul(&x, &x, &c.p), &x, &c.p);
419            let rhs = fp2_add(&fp2_add(&x3, &fp2_mul(&c.a, &x, &c.p), &c.p), &c.b, &c.p);
420            if fp2_is_zero(&rhs) {
421                v.push(Point2::Affine(x, fp2_const(0, &c.p)));
422            } else if let Some(y) = fp2_sqrt(&rhs, &c.p) {
423                v.push(Point2::Affine(x.clone(), fp2_neg(&y, &c.p)));
424                v.push(Point2::Affine(x, y));
425            }
426        }
427    }
428    v
429}
430
431/// A point of prime order `ell` over `𝔽_{p²}` (a candidate isogeny kernel), or `None`.
432pub fn point_of_order2(c: &Curve2, ell: u64) -> Option<Point2> {
433    points_on_curve2(c)
434        .into_iter()
435        .find(|pt| *pt != Point2::Infinity && c.mul(&ib(ell as i64), pt) == Point2::Infinity)
436}
437
438/// A torsion basis of `E[n]` over `𝔽_{p²}` (`n` prime) — the full `n`-torsion is `𝔽_{p²}`-rational on a
439/// supersingular curve when `n | p+1`. `None` if it is not fully rational.
440pub fn torsion_basis2(c: &Curve2, n: u64) -> Option<(Point2, Point2)> {
441    let onp: Vec<Point2> = points_on_curve2(c)
442        .into_iter()
443        .filter(|pt| *pt != Point2::Infinity && c.mul(&ib(n as i64), pt) == Point2::Infinity)
444        .collect();
445    for p in &onp {
446        let span: Vec<Point2> = (0..n).map(|k| c.mul(&ib(k as i64), p)).collect();
447        if let Some(q) = onp.iter().find(|q| !span.contains(q)) {
448            return Some((p.clone(), q.clone()));
449        }
450    }
451    None
452}
453
454/// A separable `ell`-isogeny over `𝔽_{p²}` by Vélu's formulas (the `Curve2` analogue of `elliptic::Isogeny`).
455#[derive(Clone, Debug)]
456pub struct Isogeny2 {
457    pub domain: Curve2,
458    pub codomain: Curve2,
459    pub degree: u64,
460    kernel: Vec<(Fp2, Fp2, Fp2)>, // (xQ, vQ, uQ)
461}
462
463impl Isogeny2 {
464    pub fn from_kernel(curve: &Curve2, gen: &Point2, ell: u64) -> Option<Isogeny2> {
465        if ell < 3 || ell % 2 == 0 {
466            return None;
467        }
468        let p = &curve.p;
469        let mut kernel = Vec::new();
470        let mut cur = gen.clone();
471        for _ in 0..((ell - 1) / 2) {
472            match &cur {
473                Point2::Affine(xq, yq) => {
474                    let vq = fp2_add(
475                        &fp2_mul(&fp2_const(6, p), &fp2_mul(xq, xq, p), p),
476                        &fp2_mul(&fp2_const(2, p), &curve.a, p),
477                        p,
478                    );
479                    let uq = fp2_mul(&fp2_const(4, p), &fp2_mul(yq, yq, p), p);
480                    kernel.push((xq.clone(), vq, uq));
481                }
482                Point2::Infinity => return None,
483            }
484            cur = curve.add(&cur, gen);
485        }
486        if matches!(gen, Point2::Infinity) || curve.mul(&ib(ell as i64), gen) != Point2::Infinity {
487            return None;
488        }
489        let (mut vsum, mut wsum) = (fp2_const(0, p), fp2_const(0, p));
490        for (xq, vq, uq) in &kernel {
491            vsum = fp2_add(&vsum, vq, p);
492            wsum = fp2_add(&wsum, &fp2_add(uq, &fp2_mul(xq, vq, p), p), p);
493        }
494        let a2 = fp2_sub(&curve.a, &fp2_mul(&fp2_const(5, p), &vsum, p), p);
495        let b2 = fp2_sub(&curve.b, &fp2_mul(&fp2_const(7, p), &wsum, p), p);
496        Some(Isogeny2 {
497            domain: curve.clone(),
498            codomain: Curve2::new(a2, b2, p.clone()),
499            degree: ell,
500            kernel,
501        })
502    }
503
504    pub fn eval(&self, pt: &Point2) -> Point2 {
505        let p = &self.domain.p;
506        match pt {
507            Point2::Infinity => Point2::Infinity,
508            Point2::Affine(x, y) => {
509                let mut xnew = x.clone();
510                let mut yfac = fp2_const(1, p);
511                for (xq, vq, uq) in &self.kernel {
512                    let d = fp2_sub(x, xq, p);
513                    if fp2_is_zero(&d) {
514                        return Point2::Infinity;
515                    }
516                    let di = fp2_inv(&d, p).expect("nonzero");
517                    let di2 = fp2_mul(&di, &di, p);
518                    let di3 = fp2_mul(&di2, &di, p);
519                    xnew = fp2_add(
520                        &xnew,
521                        &fp2_add(&fp2_mul(vq, &di, p), &fp2_mul(uq, &di2, p), p),
522                        p,
523                    );
524                    let tail = fp2_add(
525                        &fp2_mul(vq, &di2, p),
526                        &fp2_mul(&fp2_mul(&fp2_const(2, p), uq, p), &di3, p),
527                        p,
528                    );
529                    yfac = fp2_sub(&yfac, &tail, p);
530                }
531                Point2::Affine(xnew, fp2_mul(y, &yfac, p))
532            }
533        }
534    }
535}
536
537fn mline_double2(c: &Curve2, t: &Point2, xq: &Fp2, yq: &Fp2) -> Option<(Fp2, Fp2)> {
538    let p = &c.p;
539    let (xt, yt) = match t {
540        Point2::Affine(x, y) => (x, y),
541        Point2::Infinity => return None,
542    };
543    if fp2_is_zero(yt) {
544        return None;
545    }
546    let num = fp2_add(&fp2_mul(&fp2_const(3, p), &fp2_mul(xt, xt, p), p), &c.a, p);
547    let lam = fp2_mul(&num, &fp2_inv(&fp2_mul(&fp2_const(2, p), yt, p), p)?, p);
548    let ell = fp2_sub(
549        &fp2_sub(yq, yt, p),
550        &fp2_mul(&lam, &fp2_sub(xq, xt, p), p),
551        p,
552    );
553    let vert = match c.double(t) {
554        Point2::Affine(x2, _) => fp2_sub(xq, &x2, p),
555        Point2::Infinity => fp2_const(1, p),
556    };
557    Some((ell, vert))
558}
559
560fn mline_add2(c: &Curve2, t: &Point2, pp: &Point2, xq: &Fp2, yq: &Fp2) -> Option<(Fp2, Fp2)> {
561    let p = &c.p;
562    let ((xt, yt), (xpp, ypp)) = match (t, pp) {
563        (Point2::Affine(a, b), Point2::Affine(cc, d)) => ((a, b), (cc, d)),
564        _ => return None,
565    };
566    if xt == xpp {
567        if yt == ypp {
568            return mline_double2(c, t, xq, yq);
569        }
570        return Some((fp2_sub(xq, xt, p), fp2_const(1, p)));
571    }
572    let lam = fp2_mul(&fp2_sub(ypp, yt, p), &fp2_inv(&fp2_sub(xpp, xt, p), p)?, p);
573    let ell = fp2_sub(
574        &fp2_sub(yq, yt, p),
575        &fp2_mul(&lam, &fp2_sub(xq, xt, p), p),
576        p,
577    );
578    let vert = match c.add(t, pp) {
579        Point2::Affine(x3, _) => fp2_sub(xq, &x3, p),
580        Point2::Infinity => fp2_const(1, p),
581    };
582    Some((ell, vert))
583}
584
585fn miller2(c: &Curve2, pp: &Point2, qq: &Point2, n: u64) -> Option<Fp2> {
586    let p = &c.p;
587    let (xq, yq) = match qq {
588        Point2::Affine(x, y) => (x, y),
589        Point2::Infinity => return None,
590    };
591    let (mut num, mut den) = (fp2_const(1, p), fp2_const(1, p));
592    let mut t = pp.clone();
593    for bit in (0..(64 - n.leading_zeros() - 1)).rev() {
594        let (ell, vert) = mline_double2(c, &t, xq, yq)?;
595        num = fp2_mul(&fp2_mul(&num, &num, p), &ell, p);
596        den = fp2_mul(&fp2_mul(&den, &den, p), &vert, p);
597        t = c.double(&t);
598        if (n >> bit) & 1 == 1 {
599            let (ell, vert) = mline_add2(c, &t, pp, xq, yq)?;
600            num = fp2_mul(&num, &ell, p);
601            den = fp2_mul(&den, &vert, p);
602            t = c.add(&t, pp);
603        }
604    }
605    if fp2_is_zero(&den) {
606        return None;
607    }
608    Some(fp2_mul(&num, &fp2_inv(&den, p)?, p))
609}
610
611/// The **Weil pairing over `𝔽_{p²}`** — the `Curve2` analogue of `elliptic::weil_pairing`, via Miller.
612pub fn weil_pairing2(c: &Curve2, pp: &Point2, qq: &Point2, n: u64) -> Option<Fp2> {
613    if pp == qq || matches!(pp, Point2::Infinity) || matches!(qq, Point2::Infinity) {
614        return Some(fp2_const(1, &c.p));
615    }
616    let fp = miller2(c, pp, qq, n)?;
617    let fq = miller2(c, qq, pp, n)?;
618    let ratio = fp2_mul(&fp, &fp2_inv(&fq, &c.p)?, &c.p);
619    Some(if n % 2 == 1 {
620        fp2_neg(&ratio, &c.p)
621    } else {
622        ratio
623    })
624}
625
626/// The Weil pairing on a **product surface** `E₁ × E₂`: `e((P₁,P₂),(Q₁,Q₂)) = e_N(P₁,Q₁)·e_N(P₂,Q₂)`. A
627/// subgroup on which this vanishes (`= 1`) is **isotropic**; a *maximal* isotropic (Lagrangian) subgroup is
628/// the kernel of an `(N,N)`-isogeny of abelian surfaces — the gluing at the heart of Kani's theorem and the
629/// Castryck–Decru attack.
630pub fn product_weil_pairing(
631    c1: &Curve2,
632    c2: &Curve2,
633    p: (&Point2, &Point2),
634    q: (&Point2, &Point2),
635    n: u64,
636) -> Option<Fp2> {
637    let e1 = weil_pairing2(c1, p.0, q.0, n)?;
638    let e2 = weil_pairing2(c2, p.1, q.1, n)?;
639    Some(fp2_mul(&e1, &e2, &c1.p))
640}
641
642/// `α^k` in `𝔽_{p²}` by square-and-multiply.
643pub fn fp2_pow(alpha: &Fp2, k: u64, p: &BigInt) -> Fp2 {
644    let mut result = fp2_const(1, p);
645    let mut base = alpha.clone();
646    let mut e = k;
647    while e > 0 {
648        if e & 1 == 1 {
649            result = fp2_mul(&result, &base, p);
650        }
651        base = fp2_mul(&base, &base, p);
652        e >>= 1;
653    }
654    result
655}
656
657// ===== SIDH keyspace over 𝔽_{p²}: unfolding, images → generator recovery, the ℓ-adic tree, Aut-orbits =====
658
659/// The order of a point over `𝔽_{p²}` (least `k ≥ 1` with `k·pt = O`), searched up to `bound`.
660pub fn point_order2(c: &Curve2, pt: &Point2, bound: u64) -> Option<u64> {
661    let mut cur = pt.clone();
662    for k in 1..=bound {
663        if cur == Point2::Infinity {
664            return Some(k);
665        }
666        cur = c.add(&cur, pt);
667    }
668    None
669}
670
671/// The SIDH kernel generator `P + [s]·Q` over `𝔽_{p²}`.
672pub fn kernel_generator2(c: &Curve2, p_pt: &Point2, q_pt: &Point2, s: &BigInt) -> Point2 {
673    c.add(p_pt, &c.mul(s, q_pt))
674}
675
676/// A rank-2 basis `(P, Q)` of `E[ℓᵃ] = (ℤ/ℓᵃ)²` — both of order exactly `ℓᵃ`, independent. The full
677/// `ℓᵃ`-torsion is `𝔽_{p²}`-rational on a supersingular curve when `ℓᵃ | p+1`.
678pub fn full_order_basis2(c: &Curve2, ell: u64, a: u32) -> Option<(Point2, Point2)> {
679    let n = ell.pow(a);
680    let full: Vec<Point2> = points_on_curve2(c)
681        .into_iter()
682        .filter(|pt| point_order2(c, pt, n + 1) == Some(n))
683        .collect();
684    for p in &full {
685        let span: Vec<Point2> = (0..n).map(|k| c.mul(&ib(k as i64), p)).collect();
686        if let Some(q) = full.iter().find(|q| !span.contains(q)) {
687            return Some((p.clone(), q.clone()));
688        }
689    }
690    None
691}
692
693/// A single `ℓ`-isogeny step over `𝔽_{p²}`: domain, the order-`ℓ` kernel, and codomain.
694#[derive(Clone, Debug, PartialEq)]
695pub struct IsogenyStep2 {
696    pub domain: Curve2,
697    pub kernel: Point2,
698    pub codomain: Curve2,
699}
700
701/// Unfold one order-`ℓᵃ` kernel generator into the chain of `a` prime-degree `ℓ`-isogenies over `𝔽_{p²}` —
702/// the `Curve2` analogue of [`crate::elliptic::derive_isogeny_path`]. `ℓ` an odd prime.
703pub fn derive_isogeny_path2(
704    c: &Curve2,
705    gen: &Point2,
706    ell: u64,
707    a: u32,
708) -> Option<Vec<IsogenyStep2>> {
709    let mut steps = Vec::with_capacity(a as usize);
710    let mut e = c.clone();
711    let mut g = gen.clone();
712    for step in 0..a {
713        let mut mult = ib(1);
714        for _ in 0..(a - 1 - step) {
715            mult = mult.mul(&ib(ell as i64));
716        }
717        let k = e.mul(&mult, &g);
718        let iso = Isogeny2::from_kernel(&e, &k, ell)?;
719        steps.push(IsogenyStep2 {
720            domain: e.clone(),
721            kernel: k,
722            codomain: iso.codomain.clone(),
723        });
724        g = iso.eval(&g);
725        e = iso.codomain;
726    }
727    Some(steps)
728}
729
730/// Push a point through an entire isogeny chain, rebuilding each step's Vélu map.
731pub fn push_through2(steps: &[IsogenyStep2], ell: u64, pt: &Point2) -> Option<Point2> {
732    let mut cur = pt.clone();
733    for step in steps {
734        cur = Isogeny2::from_kernel(&step.domain, &step.kernel, ell)?.eval(&cur);
735    }
736    Some(cur)
737}
738
739/// **Images → generator reconstruction (flat oracle).** The secret isogeny `φ: E₀ → E` of degree `ℓᵃ` has
740/// kernel `⟨P_A + [s]Q_A⟩`; the published torsion images `φ(P_B), φ(Q_B)` pin `s` down. Enumerate the whole
741/// keyspace and return the scalar whose unfolded chain reproduces both images — a genuine images → generator
742/// inversion at SIDH scale. `O(ℓᵃ)`; the correctness oracle for the structured recovery below.
743pub fn recover_secret2(
744    e0: &Curve2,
745    basis_a: (&Point2, &Point2),
746    ell: u64,
747    a: u32,
748    basis_b: (&Point2, &Point2),
749    images: (&Point2, &Point2),
750) -> Option<(BigInt, Point2, Vec<IsogenyStep2>)> {
751    let n = ell.pow(a);
752    for s in 0..n {
753        let sb = ib(s as i64);
754        let gen = kernel_generator2(e0, basis_a.0, basis_a.1, &sb);
755        if point_order2(e0, &gen, n + 1) != Some(n) {
756            continue;
757        }
758        let Some(path) = derive_isogeny_path2(e0, &gen, ell, a) else {
759            continue;
760        };
761        match (
762            push_through2(&path, ell, basis_b.0),
763            push_through2(&path, ell, basis_b.1),
764        ) {
765            (Some(ip), Some(iq)) if &ip == images.0 && &iq == images.1 => {
766                return Some((sb, gen, path))
767            }
768            _ => {}
769        }
770    }
771    None
772}
773
774/// The digit-tree walk: `s = Σ dₖ·ℓᵏ`, so the secret's `ℓ`-adic digits `d₀,…,d_{a-1}` index a depth-`a`
775/// `ℓ`-ary tree whose depth-`k` node fixes `s mod ℓᵏ`. All secrets under one node share their first `k`
776/// isogeny steps — the auto-partition. DFS over the digits, testing each leaf's chain against the images.
777#[allow(clippy::too_many_arguments)]
778fn walk_keyspace_tree(
779    e0: &Curve2,
780    ba: (&Point2, &Point2),
781    ell: u64,
782    a: u32,
783    n: u64,
784    bb: (&Point2, &Point2),
785    images: (&Point2, &Point2),
786    digits: &mut Vec<u64>,
787) -> Option<(BigInt, Point2)> {
788    if digits.len() as u32 == a {
789        let (mut s, mut place) = (ib(0), ib(1));
790        for &d in digits.iter() {
791            s = s.add(&place.mul(&ib(d as i64)));
792            place = place.mul(&ib(ell as i64));
793        }
794        let gen = kernel_generator2(e0, ba.0, ba.1, &s);
795        if point_order2(e0, &gen, n + 1) != Some(n) {
796            return None;
797        }
798        let path = derive_isogeny_path2(e0, &gen, ell, a)?;
799        let (ip, iq) = (
800            push_through2(&path, ell, bb.0)?,
801            push_through2(&path, ell, bb.1)?,
802        );
803        return (&ip == images.0 && &iq == images.1).then_some((s, gen));
804    }
805    for d in 0..ell {
806        digits.push(d);
807        if let Some(found) = walk_keyspace_tree(e0, ba, ell, a, n, bb, images, digits) {
808            return Some(found);
809        }
810        digits.pop();
811    }
812    None
813}
814
815/// **Structured images → generator recovery.** Walks the `ℓ`-adic keyspace *tree* (auto-partitioning by
816/// digit) rather than the flat list, returning the recovered `ℓ`-adic digits, the secret `s = Σ dₖ·ℓᵏ`, and
817/// its generator. Same answer as [`recover_secret2`] — but the recursion **is** the digit-by-digit structure
818/// the Castryck–Decru Kani oracle prunes with a per-digit split-test.
819pub fn recover_secret_recursive2(
820    e0: &Curve2,
821    basis_a: (&Point2, &Point2),
822    ell: u64,
823    a: u32,
824    basis_b: (&Point2, &Point2),
825    images: (&Point2, &Point2),
826) -> Option<(Vec<u64>, BigInt, Point2)> {
827    let n = ell.pow(a);
828    let mut digits: Vec<u64> = Vec::with_capacity(a as usize);
829    let (s, gen) = walk_keyspace_tree(e0, basis_a, ell, a, n, basis_b, images, &mut digits)?;
830    Some((digits, s, gen))
831}
832
833/// The order-4 automorphism `ι:(x,y) ↦ (−x, i·y)` of the `j = 1728` curve `y² = x³ + x` (`i² = −1` lives in
834/// `𝔽_{p²}` for `p ≡ 3 mod 4`). `ι² = [−1]`, so `⟨ι⟩ ≅ ℤ/4 = Aut(E₀)`. It permutes the keyspace, and
835/// `E₀/⟨K⟩ ≅ E₀/⟨ι(K)⟩` — the symmetry that makes recovering one kernel recover its whole orbit.
836pub fn aut_1728(p: &BigInt, pt: &Point2) -> Point2 {
837    match pt {
838        Point2::Infinity => Point2::Infinity,
839        Point2::Affine(x, y) => {
840            let i_unit = (ib(0), ib(1)); // i ∈ 𝔽_{p²}
841            Point2::Affine(fp2_neg(x, p), fp2_mul(&i_unit, y, p))
842        }
843    }
844}
845
846/// Partition the keyspace by **codomain `j`-invariant**: secrets whose isogeny lands on the same curve (up to
847/// isomorphism). These classes are exactly the `Aut(E₀)`-orbits — so if one secret in a class is invertible
848/// (its codomain is the target `E`), every secret in the class maps to a curve `≅ E`. Returns
849/// `(j, [secrets])` groups.
850pub fn keyspace_codomain_classes(
851    e0: &Curve2,
852    basis_a: (&Point2, &Point2),
853    ell: u64,
854    a: u32,
855) -> Vec<(Fp2, Vec<u64>)> {
856    let n = ell.pow(a);
857    let mut classes: Vec<(Fp2, Vec<u64>)> = Vec::new();
858    for s in 0..n {
859        let gen = kernel_generator2(e0, basis_a.0, basis_a.1, &ib(s as i64));
860        if point_order2(e0, &gen, n + 1) != Some(n) {
861            continue;
862        }
863        let Some(path) = derive_isogeny_path2(e0, &gen, ell, a) else {
864            continue;
865        };
866        let Some(j) = path.last().and_then(|st| st.codomain.j_invariant()) else {
867            continue;
868        };
869        match classes.iter().position(|(cj, _)| *cj == j) {
870            Some(idx) => classes[idx].1.push(s),
871            None => classes.push((j, vec![s])),
872        }
873    }
874    classes
875}
876
877/// The `ℓ+1` `ℓ`-isogenous neighbours of a curve: the codomains of the `ℓ+1` order-`ℓ` subgroups of `E[ℓ]`.
878fn ell_isogeny_neighbors(c: &Curve2, ell: u64) -> Vec<Curve2> {
879    let Some((r, s)) = full_order_basis2(c, ell, 1) else {
880        return Vec::new();
881    };
882    let mut gens: Vec<Point2> = (0..ell)
883        .map(|i| c.add(&r, &c.mul(&ib(i as i64), &s)))
884        .collect();
885    gens.push(s);
886    gens.into_iter()
887        .filter_map(|g| Isogeny2::from_kernel(c, &g, ell).map(|iso| iso.codomain))
888        .collect()
889}
890
891/// Backward BFS on the supersingular `ℓ`-isogeny graph from `target`: the minimum `ℓ`-isogeny distance to each
892/// reachable `j`-invariant, out to `max_depth`. This is a **sound per-digit oracle** — a partial curve farther
893/// from the target than its remaining step budget cannot lie on the secret path, so its whole subtree is dead.
894pub fn isogeny_graph_distances(target: &Curve2, ell: u64, max_depth: u32) -> Vec<(Fp2, u32)> {
895    let Some(j0) = target.j_invariant() else {
896        return Vec::new();
897    };
898    let mut dist: Vec<(Fp2, u32)> = vec![(j0, 0)];
899    let mut frontier = vec![target.clone()];
900    for d in 1..=max_depth {
901        let mut next = Vec::new();
902        for c in &frontier {
903            for nbr in ell_isogeny_neighbors(c, ell) {
904                if let Some(j) = nbr.j_invariant() {
905                    if !dist.iter().any(|(jj, _)| *jj == j) {
906                        dist.push((j, d));
907                        next.push(nbr);
908                    }
909                }
910            }
911        }
912        if next.is_empty() {
913            break;
914        }
915        frontier = next;
916    }
917    dist
918}
919
920/// Oracle-pruned digit-tree walk: at each depth-`k` node the partial curve `E_k` (the codomain after `k`
921/// steps of the prefix) is checked against the reachability oracle `dists`; if it is not within `a−k` steps of
922/// the target, the subtree is pruned. Sound (the true prefix always satisfies the budget), so the answer is
923/// unchanged — but leaf image-tests are confined to curves that can still reach `E`, which is exactly the
924/// target's `Aut`-orbit. `leaves` counts the image-tests actually performed.
925#[allow(clippy::too_many_arguments)]
926fn walk_pruned(
927    e0: &Curve2,
928    ba: (&Point2, &Point2),
929    ell: u64,
930    a: u32,
931    n: u64,
932    bb: (&Point2, &Point2),
933    images: (&Point2, &Point2),
934    dists: &[(Fp2, u32)],
935    digits: &mut Vec<u64>,
936    leaves: &mut usize,
937) -> Option<(BigInt, Point2)> {
938    let k = digits.len() as u32;
939    let (mut p, mut place) = (ib(0), ib(1));
940    for &d in digits.iter() {
941        p = p.add(&place.mul(&ib(d as i64)));
942        place = place.mul(&ib(ell as i64));
943    }
944    if k > 0 {
945        let gen_p = kernel_generator2(e0, ba.0, ba.1, &p);
946        let path = derive_isogeny_path2(e0, &gen_p, ell, a)?;
947        let jk = path[(k - 1) as usize].codomain.j_invariant()?;
948        match dists.iter().find(|(jj, _)| *jj == jk).map(|(_, d)| *d) {
949            Some(dk) if dk <= a - k => {} // still reachable within budget — keep going
950            _ => return None,             // too far (or off-graph) ⟹ prune the whole subtree
951        }
952    }
953    if k == a {
954        *leaves += 1;
955        let gen = kernel_generator2(e0, ba.0, ba.1, &p);
956        if point_order2(e0, &gen, n + 1) != Some(n) {
957            return None;
958        }
959        let path = derive_isogeny_path2(e0, &gen, ell, a)?;
960        let (ip, iq) = (
961            push_through2(&path, ell, bb.0)?,
962            push_through2(&path, ell, bb.1)?,
963        );
964        return (&ip == images.0 && &iq == images.1).then_some((p, gen));
965    }
966    for d in 0..ell {
967        digits.push(d);
968        if let Some(found) = walk_pruned(e0, ba, ell, a, n, bb, images, dists, digits, leaves) {
969            return Some(found);
970        }
971        digits.pop();
972    }
973    None
974}
975
976/// **Oracle-pruned images → generator recovery.** Walks the `ℓ`-adic keyspace tree but consults the isogeny
977/// graph reachability oracle (backward BFS from the *public* codomain `target`) at every node, pruning any
978/// branch that can no longer reach the target. Returns the secret, its generator, and the number of leaf
979/// image-tests performed (the pruned search visits only the target's `Aut`-orbit). Same answer as
980/// [`recover_secret2`] — soundness guarantees the true path is never pruned.
981pub fn recover_secret_pruned2(
982    e0: &Curve2,
983    basis_a: (&Point2, &Point2),
984    ell: u64,
985    a: u32,
986    basis_b: (&Point2, &Point2),
987    images: (&Point2, &Point2),
988    target: &Curve2,
989) -> Option<(BigInt, Point2, usize)> {
990    let n = ell.pow(a);
991    let dists = isogeny_graph_distances(target, ell, a);
992    let mut digits: Vec<u64> = Vec::with_capacity(a as usize);
993    let mut leaves = 0usize;
994    let (s, gen) = walk_pruned(
995        e0,
996        basis_a,
997        ell,
998        a,
999        n,
1000        basis_b,
1001        images,
1002        &dists,
1003        &mut digits,
1004        &mut leaves,
1005    )?;
1006    Some((s, gen, leaves))
1007}
1008
1009#[cfg(test)]
1010#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/fp2/tests.rs"]
1011mod tests;