Module elliptic 

Elliptic-curve primitives over ℤ/N — the additive→multiplicative lift

Pollard’s p−1 gets a single shot at a smooth group order: the multiplicative group (ℤ/p)* has the fixed order p−1, so if that one number isn’t smooth, you lose. Lenstra’s Elliptic Curve Method lifts the problem onto E(𝔽_p), whose order — by Hasse — lies in [p+1−2√p, p+1+2√p] and, crucially, changes when you change the curve. Every curve is a fresh smoothness lottery ticket, and the cost scales with the size of the smallest factor, not N — which makes ECM the champion for prying a small-to-medium prime out of an otherwise-huge modulus.

We work in Montgomery form B·y² = x³ + A·x² + x with x-only (X:Z) projective coordinates. Two payoffs: point arithmetic never needs a modular inverse (only +, −, × mod N), and the ONE place an inverse would be forced — when a point becomes the identity mod p but not mod q, so its Z is ≡ 0 (mod p) but ≢ 0 (mod N) — is exactly where gcd(Z, N) hands us the factor. The “failure” of the group law is the discovery.

This module is the reusable substrate: xdbl, xadd, and ladder are ordinary elliptic-curve group operations mod N and underpin ECDLP / pairing / isogeny work later; ecm_factor is the flagship application.

Structs

Curve

A short Weierstrass curve y² = x³ + a·x + b over the prime field 𝔽_p.

Isogeny

A separable isogeny φ: E → E' of odd prime degree ℓ, built from a kernel generator by Vélu’s formulas. Stores the codomain and, for each kernel representative Q (one per ± pair), the Vélu quantities (xQ, vQ = 6xQ²+2a, uQ = 4yQ²) used to evaluate φ.

IsogenyStep

A single ℓ-isogeny step in a chain: the domain curve, the order-ℓ kernel point quotiented at this step, and the resulting codomain.

Enums

CurveWeakness

The known STRUCTURAL weaknesses that make an elliptic curve’s ECDLP breakable — the symmetries a sound curve must avoid.

Point

An affine point on a curve, or the point at infinity (the group identity).

Functions

curve_security

Audit a curve of known order #E over 𝔽_p for the structural ECDLP weaknesses. None means the only attacks that apply are the generic O(√·) ones — the honest ceiling, not a proof of security.

derive_isogeny_path

Torsion-image → path derivation. A degree-ℓᵃ isogeny is pinned down by a single kernel generator gen of order ℓᵃ — the datum the SIDH/SIKE torsion images reconstruct (via Kani’s gluing). This unfolds that one generator into the explicit chain of a prime-degree ℓ-isogenies: at step i the kernel is the order-ℓ point [ℓ^{a−1−i}]·genᵢ, and gen is pushed forward through each step so its order descends ℓᵃ → ℓᵃ⁻¹ → … → 1. The entire secret path pops out of the one meta-datum — the generator is the rule that emits the per-step rules. Requires ℓ an odd prime and gen of order exactly ℓᵃ.

ecdlp_bsgs

Solve the elliptic-curve discrete log Q = k·P by baby-step/giant-step, given the order n of P. O(√n) group operations — the best generic attack, and exponential in the bit length. This is exactly why a sound (large prime-order) curve resists, and why ECC uses far smaller keys than RSA. None if Q is not a multiple of P.

ecm

ECM stage 3 — the escalating driver. Stages 1 and 2 are the algorithm; this is the orchestration that makes ECM a complete tool (à la GMP-ECM): run the two-stage method at a schedule of increasing bounds (b1, b2 = 100·b1) with growing curve counts, so a factor of any size is found at the cheapest level that reaches it — small factors fall almost immediately, larger ones as the bounds climb, without ever paying the big-bound cost up front. budget caps the curves per level. None if the whole schedule finishes without a factor.

ecm_factor

Lenstra’s ECM, stage 1 only. Try curves Suyama curves at smoothness bound b1; a nontrivial factor of n, or None. Cost tracks the smallest factor, not n. None for n ≤ 3.

ecm_two_stage

ECM with stage 1 + stage 2. Stage 2 (bound b2 > b1) extends each curve’s reach to a group order that is b1-smooth apart from one prime ≤ b2 — a large boost per curve for a small extra cost.

kernel_generator

The SIDH kernel generator P + [s]·Q from a torsion basis (P, Q) and the secret scalar s. The secret isogeny is the quotient by ⟨P + [s]Q⟩; Kani’s gluing is what lets an attacker recover s from the published torsion images, after which derive_isogeny_path unfolds the whole chain.

ladder

Scalar multiplication k·(X:Z) on a Montgomery curve mod n by the Montgomery ladder — a uniform sequence of one double and one differential-add per bit, maintaining the invariant R1 − R0 = P.

point_of_order

A single point of prime order ell on the curve (a candidate isogeny-kernel generator), or None if there is no rational ell-torsion. Requires p ≡ 3 (mod 4).

torsion_basis

A torsion basis of E[n] (n prime): two independent points of order n generating the full n-torsion (ℤ/n)², or None if the n-torsion is not fully rational. Requires p ≡ 3 (mod 4). This is the public torsion basis whose images an SIDH/SIKE key publishes.

weil_pairing

The Weil pairing e_N(P, Q) ∈ μ_N for independent N-torsion points P, Q, via Miller: e_N(P,Q) = (−1)ᴺ · f_{N,P}(Q) / f_{N,Q}(P). Bilinear, alternating, non-degenerate, and (the SIKE- relevant law) isogeny-compatible. None if a Miller evaluation degenerates (e.g. dependent points).

xadd

x-only differential addition on a Montgomery curve mod n: given P=(Xp:Zp), Q=(Xq:Zq) and their known difference P−Q = (Xd:Zd), return P+Q. Again inversion-free.

xdbl

x-only doubling on a Montgomery curve mod n, given a24 = (A+2)/4. Maps (X:Z) to 2·(X:Z) using only field + − × (no inversion).