Module fp2 

𝔽_{p²} arithmetic and the supersingular isogeny graph

The quadratic extension 𝔽_{p²} = 𝔽_p[i]/(i²+1) (for p ≡ 3 (mod 4), so −1 is a non-residue and i² = −1 is irreducible) is where the supersingular curves live — and so where CSIDH, SIKE, and the 2022 Castryck–Decru break happen. This module gives the field arithmetic and builds the supersingular ℓ=2 isogeny graph: vertices are supersingular j-invariants in 𝔽_{p²}, edges the 2-isogenies. We build it not through Vélu but through the classical level-2 modular polynomial Φ₂(X,Y) — the three roots of Φ₂(j, ·) are exactly the j-invariants 2-isogenous to j. So the whole graph is field arithmetic + cubic root-finding + a breadth-first walk from a known supersingular vertex (j = 1728, supersingular whenever p ≡ 3 (mod 4)). The result is a 3-regular Ramanujan graph whose size is the supersingular mass ⌊p/12⌋ + ε.

Structs

Curve2

A Weierstrass curve y² = x³ + ax + b over 𝔽_{p²}.

Isogeny2

A separable ell-isogeny over 𝔽_{p²} by Vélu’s formulas (the Curve2 analogue of elliptic::Isogeny).

IsogenyStep2

A single ℓ-isogeny step over 𝔽_{p²}: domain, the order-ℓ kernel, and codomain.

SsVertex

A vertex of the supersingular isogeny graph: a j-invariant and its 2-isogenous neighbours (as a multiset — a double root of Φ₂ is a double edge).

Enums

Point2

An affine point over 𝔽_{p²}, or the identity.

Functions

aut_1728

The order-4 automorphism ι:(x,y) ↦ (−x, i·y) of the j = 1728 curve y² = x³ + x (i² = −1 lives in 𝔽_{p²} for p ≡ 3 mod 4). ι² = [−1], so ⟨ι⟩ ≅ ℤ/4 = Aut(E₀). It permutes the keyspace, and E₀/⟨K⟩ ≅ E₀/⟨ι(K)⟩ — the symmetry that makes recovering one kernel recover its whole orbit.

derive_isogeny_path2

Unfold one order-ℓᵃ kernel generator into the chain of a prime-degree ℓ-isogenies over 𝔽_{p²} — the Curve2 analogue of crate::elliptic::derive_isogeny_path. ℓ an odd prime.

fp2_add

fp2_const

A rational constant k as an element of 𝔽_{p²}.

fp2_inv

(a+bi)⁻¹ = (a − bi)/(a² + b²). None only for 0.

fp2_is_zero

fp2_mul

(a+bi)(c+di) = (ac − bd) + (ad + bc)i.

fp2_neg

fp2_pow

α^k in 𝔽_{p²} by square-and-multiply.

fp2_sqrt

√α in 𝔽_{p²} (p ≡ 3 mod 4), or None if α is not a square. From β² = α with β = x + yi: x² − y² = a, 2xy = b, whence x² = (a ± √(a²+b²))/2; a final β² = α check makes it exact.

fp2_sub

full_order_basis2

A rank-2 basis (P, Q) of E[ℓᵃ] = (ℤ/ℓᵃ)² — both of order exactly ℓᵃ, independent. The full ℓᵃ-torsion is 𝔽_{p²}-rational on a supersingular curve when ℓᵃ | p+1.

isogeny_graph_distances

Backward BFS on the supersingular ℓ-isogeny graph from target: the minimum ℓ-isogeny distance to each reachable j-invariant, out to max_depth. This is a sound per-digit oracle — a partial curve farther from the target than its remaining step budget cannot lie on the secret path, so its whole subtree is dead.

kernel_generator2

The SIDH kernel generator P + [s]·Q over 𝔽_{p²}.

keyspace_codomain_classes

Partition the keyspace by codomain j-invariant: secrets whose isogeny lands on the same curve (up to isomorphism). These classes are exactly the Aut(E₀)-orbits — so if one secret in a class is invertible (its codomain is the target E), every secret in the class maps to a curve ≅ E. Returns (j, [secrets]) groups.

point_of_order2

A point of prime order ell over 𝔽_{p²} (a candidate isogeny kernel), or None.

point_order2

The order of a point over 𝔽_{p²} (least k ≥ 1 with k·pt = O), searched up to bound.

product_weil_pairing

The Weil pairing on a product surface E₁ × E₂: e((P₁,P₂),(Q₁,Q₂)) = e_N(P₁,Q₁)·e_N(P₂,Q₂). A subgroup on which this vanishes (= 1) is isotropic; a maximal isotropic (Lagrangian) subgroup is the kernel of an (N,N)-isogeny of abelian surfaces — the gluing at the heart of Kani’s theorem and the Castryck–Decru attack.

push_through2

Push a point through an entire isogeny chain, rebuilding each step’s Vélu map.

recover_secret2

Images → generator reconstruction (flat oracle). The secret isogeny φ: E₀ → E of degree ℓᵃ has kernel ⟨P_A + [s]Q_A⟩; the published torsion images φ(P_B), φ(Q_B) pin s down. Enumerate the whole keyspace and return the scalar whose unfolded chain reproduces both images — a genuine images → generator inversion at SIDH scale. O(ℓᵃ); the correctness oracle for the structured recovery below.

recover_secret_pruned2

Oracle-pruned images → generator recovery. Walks the ℓ-adic keyspace tree but consults the isogeny graph reachability oracle (backward BFS from the public codomain target) at every node, pruning any branch that can no longer reach the target. Returns the secret, its generator, and the number of leaf image-tests performed (the pruned search visits only the target’s Aut-orbit). Same answer as recover_secret2 — soundness guarantees the true path is never pruned.

recover_secret_recursive2

Structured images → generator recovery. Walks the ℓ-adic keyspace tree (auto-partitioning by digit) rather than the flat list, returning the recovered ℓ-adic digits, the secret s = Σ dₖ·ℓᵏ, and its generator. Same answer as recover_secret2 — but the recursion is the digit-by-digit structure the Castryck–Decru Kani oracle prunes with a per-digit split-test.

supersingular_graph

Build the supersingular ℓ=2 isogeny graph over 𝔽_{p²} (requires p ≡ 3 (mod 4)). Breadth-first from the supersingular vertex j = 1728, following the roots of Φ₂(j,·). Because the graph is connected, this reaches every supersingular j-invariant; its size is the supersingular mass ⌊p/12⌋ + ε and every vertex has out-degree 3. None if p ≢ 3 (mod 4).

torsion_basis2

A torsion basis of E[n] over 𝔽_{p²} (n prime) — the full n-torsion is 𝔽_{p²}-rational on a supersingular curve when n | p+1. None if it is not fully rational.

weil_pairing2

The Weil pairing over 𝔽_{p²} — the Curve2 analogue of elliptic::weil_pairing, via Miller.

Type Aliases

Fp2

An element a + b·i of 𝔽_{p²} = 𝔽_p[i]/(i²+1).