Skip to main content

logicaffeine_proof/
elliptic.rs

1//! # Elliptic-curve primitives over ℤ/N — the additive→multiplicative lift
2//!
3//! Pollard's `p−1` gets a single shot at a smooth group order: the multiplicative group `(ℤ/p)*` has the
4//! *fixed* order `p−1`, so if that one number isn't smooth, you lose. Lenstra's **Elliptic Curve Method**
5//! lifts the problem onto `E(𝔽_p)`, whose order — by Hasse — lies in `[p+1−2√p, p+1+2√p]` and, crucially,
6//! **changes when you change the curve.** Every curve is a fresh smoothness lottery ticket, and the cost
7//! scales with the size of the *smallest* factor, not `N` — which makes ECM the champion for prying a
8//! small-to-medium prime out of an otherwise-huge modulus.
9//!
10//! We work in **Montgomery form** `B·y² = x³ + A·x² + x` with **x-only `(X:Z)` projective coordinates**.
11//! Two payoffs: point arithmetic never needs a modular inverse (only `+`, `−`, `×` mod `N`), and the ONE
12//! place an inverse *would* be forced — when a point becomes the identity mod `p` but not mod `q`, so its
13//! `Z` is `≡ 0 (mod p)` but `≢ 0 (mod N)` — is exactly where `gcd(Z, N)` hands us the factor. The "failure"
14//! of the group law *is* the discovery.
15//!
16//! This module is the reusable substrate: [`xdbl`], [`xadd`], and [`ladder`] are ordinary elliptic-curve
17//! group operations mod `N` and underpin ECDLP / pairing / isogeny work later; [`ecm_factor`] is the
18//! flagship application.
19
20use crate::factor::{gcd, mod_inverse, modpow};
21use logicaffeine_base::BigInt;
22use std::collections::HashMap;
23
24#[inline]
25fn i(x: i64) -> BigInt {
26    BigInt::from_i64(x)
27}
28
29/// The non-negative residue `a mod n` (handles a negative `a`).
30#[inline]
31fn rem_pos(a: &BigInt, n: &BigInt) -> BigInt {
32    let r = a.div_rem(n).map(|(_, r)| r).unwrap_or_else(|| a.clone());
33    if r.is_negative() {
34        r.add(n)
35    } else {
36        r
37    }
38}
39
40#[inline]
41fn mulmod(a: &BigInt, b: &BigInt, n: &BigInt) -> BigInt {
42    rem_pos(&a.mul(b), n)
43}
44#[inline]
45fn addmod(a: &BigInt, b: &BigInt, n: &BigInt) -> BigInt {
46    rem_pos(&a.add(b), n)
47}
48#[inline]
49fn submod(a: &BigInt, b: &BigInt, n: &BigInt) -> BigInt {
50    rem_pos(&a.sub(b), n)
51}
52
53/// x-only **doubling** on a Montgomery curve mod `n`, given `a24 = (A+2)/4`. Maps `(X:Z)` to `2·(X:Z)`
54/// using only field `+ − ×` (no inversion).
55pub fn xdbl(x: &BigInt, z: &BigInt, a24: &BigInt, n: &BigInt) -> (BigInt, BigInt) {
56    let xpz = addmod(x, z, n);
57    let xmz = submod(x, z, n);
58    let t1 = mulmod(&xpz, &xpz, n); // (X+Z)²
59    let t2 = mulmod(&xmz, &xmz, n); // (X−Z)²
60    let x2 = mulmod(&t1, &t2, n); // (X+Z)²(X−Z)²
61    let t3 = submod(&t1, &t2, n); // 4XZ = (X+Z)² − (X−Z)²
62    let inner = addmod(&t2, &mulmod(a24, &t3, n), n); // (X−Z)² + a24·4XZ
63    let z2 = mulmod(&t3, &inner, n);
64    (x2, z2)
65}
66
67/// x-only **differential addition** on a Montgomery curve mod `n`: given `P=(Xp:Zp)`, `Q=(Xq:Zq)` and their
68/// known difference `P−Q = (Xd:Zd)`, return `P+Q`. Again inversion-free.
69pub fn xadd(
70    xp: &BigInt,
71    zp: &BigInt,
72    xq: &BigInt,
73    zq: &BigInt,
74    xd: &BigInt,
75    zd: &BigInt,
76    n: &BigInt,
77) -> (BigInt, BigInt) {
78    let a = mulmod(&submod(xp, zp, n), &addmod(xq, zq, n), n); // (Xp−Zp)(Xq+Zq)
79    let b = mulmod(&addmod(xp, zp, n), &submod(xq, zq, n), n); // (Xp+Zp)(Xq−Zq)
80    let s = addmod(&a, &b, n);
81    let d = submod(&a, &b, n);
82    let xr = mulmod(zd, &mulmod(&s, &s, n), n); // Zd·(a+b)²
83    let zr = mulmod(xd, &mulmod(&d, &d, n), n); // Xd·(a−b)²
84    (xr, zr)
85}
86
87/// Scalar multiplication `k·(X:Z)` on a Montgomery curve mod `n` by the **Montgomery ladder** — a uniform
88/// sequence of one double and one differential-add per bit, maintaining the invariant `R1 − R0 = P`.
89pub fn ladder(k: u64, x: &BigInt, z: &BigInt, a24: &BigInt, n: &BigInt) -> (BigInt, BigInt) {
90    if k == 0 {
91        return (i(0), i(0)); // the identity (a point with Z = 0)
92    }
93    if k == 1 {
94        return (x.clone(), z.clone());
95    }
96    let mut r0 = (x.clone(), z.clone()); // P
97    let mut r1 = xdbl(x, z, a24, n); // 2P  (R1 − R0 = P)
98    for bit in (0..(64 - k.leading_zeros() - 1)).rev() {
99        if (k >> bit) & 1 == 1 {
100            r0 = xadd(&r0.0, &r0.1, &r1.0, &r1.1, x, z, n);
101            r1 = xdbl(&r1.0, &r1.1, a24, n);
102        } else {
103            r1 = xadd(&r0.0, &r0.1, &r1.0, &r1.1, x, z, n);
104            r0 = xdbl(&r0.0, &r0.1, a24, n);
105        }
106    }
107    r0
108}
109
110/// Primes `≤ b` by the sieve of Eratosthenes.
111fn primes_up_to(b: u64) -> Vec<u64> {
112    if b < 2 {
113        return Vec::new();
114    }
115    let mut sieve = vec![true; (b as usize) + 1];
116    sieve[0] = false;
117    sieve[1] = false;
118    let mut p = 2usize;
119    while p * p <= b as usize {
120        if sieve[p] {
121            let mut m = p * p;
122            while m <= b as usize {
123                sieve[m] = false;
124                m += p;
125            }
126        }
127        p += 1;
128    }
129    (2..=b).filter(|&x| sieve[x as usize]).collect()
130}
131
132/// **ECM stage 2** — the baby-step/giant-step continuation. After stage 1 has multiplied the base point by
133/// every prime power `≤ b1` (leaving `q = (qx:qz)`), stage 2 catches a factor `p` whose group order
134/// `#E(𝔽_p)` is `b1`-smooth EXCEPT for a *single* prime `ℓ ∈ (b1, b2]` — such an `ℓ` satisfies
135/// `ℓ·q ≡ O (mod p)`. Writing each such prime as `ℓ = i·d ± j`, that is `x((i·d)·q) = x(j·q) (mod p)`; we
136/// accumulate the product of all cross-differences `X(T_i)·Z(S_j) − X(S_j)·Z(T_i)` mod `n` and take ONE gcd,
137/// so the whole interval costs a single inversion. This is the standard, large power boost over stage 1.
138fn ecm_stage2(
139    qx: &BigInt,
140    qz: &BigInt,
141    a24: &BigInt,
142    b1: u64,
143    b2: u64,
144    n: &BigInt,
145) -> Option<BigInt> {
146    let one = i(1);
147    let d = 210u64; // 2·3·5·7 — primes cluster as i·d ± j with |j| ≤ 105
148    let half = (d / 2) as usize;
149
150    // Baby steps S[j] = j·q for j = 1..=half (built by the differential-addition chain).
151    let mut sx = vec![i(0); half + 1];
152    let mut sz = vec![i(0); half + 1];
153    sx[1] = qx.clone();
154    sz[1] = qz.clone();
155    if half >= 2 {
156        let s2 = xdbl(qx, qz, a24, n);
157        sx[2] = s2.0;
158        sz[2] = s2.1;
159        for j in 3..=half {
160            let s = xadd(&sx[j - 1], &sz[j - 1], qx, qz, &sx[j - 2], &sz[j - 2], n);
161            sx[j] = s.0;
162            sz[j] = s.1;
163        }
164    }
165
166    // Bin each prime in (b1, b2] by its nearest giant index i and offset j: ℓ = i·d ± j.
167    let mut bins: HashMap<u64, Vec<usize>> = HashMap::new();
168    let (mut i_lo, mut i_hi) = (u64::MAX, 0u64);
169    for &ell in primes_up_to(b2).iter().filter(|&&p| p > b1) {
170        let ii = (ell + d / 2) / d;
171        let j = (ell as i64 - (ii * d) as i64).unsigned_abs() as usize;
172        if (1..=half).contains(&j) {
173            bins.entry(ii).or_default().push(j);
174            i_lo = i_lo.min(ii);
175            i_hi = i_hi.max(ii);
176        }
177    }
178    if i_lo > i_hi {
179        return None; // no primes in range
180    }
181
182    // Giant steps T_i = (i·d)·q, advanced by the differential addition T_{i+1} = T_i + d·q (diff T_{i-1}).
183    let dq = ladder(d, qx, qz, a24, n);
184    let mut t_prev = ladder(i_lo.saturating_sub(1) * d, qx, qz, a24, n);
185    let mut t_cur = ladder(i_lo * d, qx, qz, a24, n);
186    let mut accum = one.clone();
187    for ii in i_lo..=i_hi {
188        if ii > i_lo {
189            let t_next = xadd(&t_cur.0, &t_cur.1, &dq.0, &dq.1, &t_prev.0, &t_prev.1, n);
190            t_prev = t_cur;
191            t_cur = t_next;
192        }
193        if let Some(js) = bins.get(&ii) {
194            for &j in js {
195                let cross = submod(
196                    &mulmod(&t_cur.0, &sz[j], n),
197                    &mulmod(&sx[j], &t_cur.1, n),
198                    n,
199                );
200                if !cross.is_zero() {
201                    accum = mulmod(&accum, &cross, n);
202                }
203            }
204        }
205    }
206    let g = gcd(&accum, n);
207    (g != one && g != *n).then_some(g)
208}
209
210/// Run stage 1 (and stage 2 when `b2 > b1`) on ONE Suyama curve `σ`. Returns a factor or `None`.
211fn ecm_one_curve(n: &BigInt, sigma_u: u64, b1: u64, b2: u64, primes1: &[u64]) -> Option<BigInt> {
212    let one = i(1);
213    let sigma = i(sigma_u as i64);
214    let u = submod(&mulmod(&sigma, &sigma, n), &i(5), n); // σ² − 5
215    let v = mulmod(&i(4), &sigma, n); // 4σ
216    let u3 = mulmod(&mulmod(&u, &u, n), &u, n);
217    let v3 = mulmod(&mulmod(&v, &v, n), &v, n);
218    let vmu = submod(&v, &u, n);
219    let vmu3 = mulmod(&mulmod(&vmu, &vmu, n), &vmu, n);
220    let num = mulmod(&vmu3, &addmod(&mulmod(&i(3), &u, n), &v, n), n); // (v−u)³(3u+v)
221    let den = mulmod(&mulmod(&i(4), &u3, n), &v, n); // 4u³v
222
223    // The one forced inverse; a nontrivial gcd(den, n) IS a factor (bonus).
224    let g = gcd(&den, n);
225    if g != one && g != *n {
226        return Some(g);
227    }
228    let a24 = mulmod(&num, &mod_inverse(&den, n)?, n);
229    let mut pt = (u3, v3);
230
231    // Stage 1: multiply by ∏_{p ≤ b1} p^{⌊log_p b1⌋}, one prime power at a time.
232    for &p in primes1 {
233        let mut q = p;
234        while q <= b1 {
235            pt = ladder(p, &pt.0, &pt.1, &a24, n);
236            q = q.saturating_mul(p);
237        }
238    }
239    let g = gcd(&pt.1, n);
240    if g != one && g != *n {
241        return Some(g);
242    }
243    if b2 > b1 {
244        return ecm_stage2(&pt.0, &pt.1, &a24, b1, b2, n);
245    }
246    None
247}
248
249/// The per-curve Suyama seed: `σ ≥ 6`, varied by curve index and `seed`.
250#[inline]
251fn suyama_sigma(seed: u64, c: usize) -> u64 {
252    6 + seed.wrapping_add(c as u64).wrapping_mul(2_654_435_761) % 1_000_000_000
253}
254
255/// **Lenstra's ECM, stage 1 only.** Try `curves` Suyama curves at smoothness bound `b1`; a nontrivial
256/// factor of `n`, or `None`. Cost tracks the *smallest* factor, not `n`. `None` for `n ≤ 3`.
257pub fn ecm_factor(n: &BigInt, b1: u64, curves: usize, seed: u64) -> Option<BigInt> {
258    if n.to_i64().is_some_and(|v| v <= 3) {
259        return None;
260    }
261    if !n.is_odd() {
262        return Some(i(2));
263    }
264    let primes = primes_up_to(b1);
265    (0..curves).find_map(|c| ecm_one_curve(n, suyama_sigma(seed, c), b1, b1, &primes))
266}
267
268/// **ECM with stage 1 + stage 2.** Stage 2 (bound `b2 > b1`) extends each curve's reach to a group order
269/// that is `b1`-smooth apart from one prime `≤ b2` — a large boost per curve for a small extra cost.
270pub fn ecm_two_stage(n: &BigInt, b1: u64, b2: u64, curves: usize, seed: u64) -> Option<BigInt> {
271    if n.to_i64().is_some_and(|v| v <= 3) {
272        return None;
273    }
274    if !n.is_odd() {
275        return Some(i(2));
276    }
277    let primes = primes_up_to(b1);
278    (0..curves).find_map(|c| ecm_one_curve(n, suyama_sigma(seed, c), b1, b2, &primes))
279}
280
281/// **ECM stage 3 — the escalating driver.** Stages 1 and 2 are the algorithm; this is the orchestration that
282/// makes ECM a complete tool (à la GMP-ECM): run the two-stage method at a schedule of increasing bounds
283/// `(b1, b2 = 100·b1)` with growing curve counts, so a factor of *any* size is found at the cheapest level
284/// that reaches it — small factors fall almost immediately, larger ones as the bounds climb, without ever
285/// paying the big-bound cost up front. `budget` caps the curves per level. `None` if the whole schedule
286/// finishes without a factor.
287pub fn ecm(n: &BigInt, budget: usize, seed: u64) -> Option<BigInt> {
288    const SCHEDULE: &[(u64, usize)] = &[(2_000, 25), (11_000, 90), (50_000, 300), (250_000, 700)];
289    for (level, &(b1, curves)) in SCHEDULE.iter().enumerate() {
290        let curves = curves.min(budget.max(1));
291        if let Some(f) = ecm_two_stage(
292            n,
293            b1,
294            b1.saturating_mul(100),
295            curves,
296            seed.wrapping_add(level as u64),
297        ) {
298            return Some(f);
299        }
300    }
301    None
302}
303
304// ---- Full Weierstrass arithmetic over 𝔽_p and the ECDLP ---------------------------------------------
305//
306// ECM *factors*; the elliptic-curve DISCRETE LOG is the other, deeper problem — the one ECC's security
307// rests on. Here we build full affine point arithmetic over a prime field and (a) solve the ECDLP by
308// baby-step/giant-step, which runs in O(√n) and so *proves the generic wall* (exponential in bit length —
309// why sound ECC resists and gets away with small keys), and (b) audit a curve for the exact structural
310// symmetries that DO break it: anomalous (Smart, polynomial), supersingular (MOV), smooth order (Pohlig–
311// Hellman). The generic ECDLP has NO sub-exponential attack — unlike factoring/DLP — which is the honest
312// reason ECC is, per bit, the strongest of the classical assumptions.
313
314/// A short Weierstrass curve `y² = x³ + a·x + b` over the prime field `𝔽_p`.
315#[derive(Clone, Debug, PartialEq, Eq)]
316pub struct Curve {
317    pub a: BigInt,
318    pub b: BigInt,
319    pub p: BigInt,
320}
321
322/// An affine point on a curve, or the point at infinity (the group identity).
323#[derive(Clone, Debug, PartialEq, Eq)]
324pub enum Point {
325    Infinity,
326    Affine(BigInt, BigInt),
327}
328
329impl Curve {
330    pub fn new(a: BigInt, b: BigInt, p: BigInt) -> Curve {
331        Curve { a, b, p }
332    }
333
334    /// Whether `pt` satisfies the curve equation.
335    pub fn is_on_curve(&self, pt: &Point) -> bool {
336        match pt {
337            Point::Infinity => true,
338            Point::Affine(x, y) => {
339                let lhs = mulmod(y, y, &self.p);
340                let x3 = mulmod(&mulmod(x, x, &self.p), x, &self.p);
341                let rhs = addmod(
342                    &addmod(&x3, &mulmod(&self.a, x, &self.p), &self.p),
343                    &self.b,
344                    &self.p,
345                );
346                lhs == rhs
347            }
348        }
349    }
350
351    /// The group inverse `−P`.
352    pub fn negate(&self, pt: &Point) -> Point {
353        match pt {
354            Point::Infinity => Point::Infinity,
355            Point::Affine(x, y) => Point::Affine(x.clone(), submod(&i(0), y, &self.p)),
356        }
357    }
358
359    /// The group law `P + Q`.
360    pub fn add(&self, p1: &Point, p2: &Point) -> Point {
361        match (p1, p2) {
362            (Point::Infinity, _) => p2.clone(),
363            (_, Point::Infinity) => p1.clone(),
364            (Point::Affine(x1, y1), Point::Affine(x2, y2)) => {
365                if x1 == x2 {
366                    if addmod(y1, y2, &self.p).is_zero() {
367                        return Point::Infinity; // P = −Q
368                    }
369                    return self.double(p1); // P = Q
370                }
371                let den = mod_inverse(&submod(x2, x1, &self.p), &self.p)
372                    .expect("distinct x invertible over 𝔽_p");
373                let lam = mulmod(&submod(y2, y1, &self.p), &den, &self.p);
374                let x3 = submod(
375                    &submod(&mulmod(&lam, &lam, &self.p), x1, &self.p),
376                    x2,
377                    &self.p,
378                );
379                let y3 = submod(
380                    &mulmod(&lam, &submod(x1, &x3, &self.p), &self.p),
381                    y1,
382                    &self.p,
383                );
384                Point::Affine(x3, y3)
385            }
386        }
387    }
388
389    /// Point doubling `2P`.
390    pub fn double(&self, pt: &Point) -> Point {
391        match pt {
392            Point::Infinity => Point::Infinity,
393            Point::Affine(x, y) => {
394                if y.is_zero() {
395                    return Point::Infinity; // vertical tangent
396                }
397                let num = addmod(
398                    &mulmod(&i(3), &mulmod(x, x, &self.p), &self.p),
399                    &self.a,
400                    &self.p,
401                );
402                let den = mod_inverse(&mulmod(&i(2), y, &self.p), &self.p)
403                    .expect("2y invertible over 𝔽_p");
404                let lam = mulmod(&num, &den, &self.p);
405                let x3 = submod(
406                    &mulmod(&lam, &lam, &self.p),
407                    &mulmod(&i(2), x, &self.p),
408                    &self.p,
409                );
410                let y3 = submod(&mulmod(&lam, &submod(x, &x3, &self.p), &self.p), y, &self.p);
411                Point::Affine(x3, y3)
412            }
413        }
414    }
415
416    /// Scalar multiplication `k·P` by double-and-add (`k ≥ 0`).
417    pub fn mul(&self, k: &BigInt, pt: &Point) -> Point {
418        let mut result = Point::Infinity;
419        let mut addend = pt.clone();
420        let (_, bytes) = k.to_le_bytes();
421        for byte in bytes {
422            for b in 0..8 {
423                if (byte >> b) & 1 == 1 {
424                    result = self.add(&result, &addend);
425                }
426                addend = self.double(&addend);
427            }
428        }
429        result
430    }
431
432    /// `#E(𝔽_p)` by direct point counting (includes the identity). `O(p)` — small `p` only.
433    pub fn count_points(&self) -> u64 {
434        let p_u = self.p.to_i64().expect("small prime") as u64;
435        let exp = self.p.sub(&i(1)).div_rem(&i(2)).unwrap().0; // (p−1)/2 — the Legendre symbol exponent
436        let one = i(1);
437        let mut count = 1u64; // infinity
438        for xu in 0..p_u {
439            let x = i(xu as i64);
440            let x3 = mulmod(&mulmod(&x, &x, &self.p), &x, &self.p);
441            let rhs = addmod(
442                &addmod(&x3, &mulmod(&self.a, &x, &self.p), &self.p),
443                &self.b,
444                &self.p,
445            );
446            if rhs.is_zero() {
447                count += 1;
448            } else if modpow(&rhs, &exp, &self.p) == one {
449                count += 2; // a quadratic residue has two square roots
450            }
451        }
452        count
453    }
454
455    /// The order of `pt` — least `k > 0` with `k·pt = O`, searched up to `bound`; `None` if larger.
456    pub fn point_order(&self, pt: &Point, bound: u64) -> Option<u64> {
457        let mut cur = pt.clone();
458        for k in 1..=bound {
459            if cur == Point::Infinity {
460                return Some(k);
461            }
462            cur = self.add(&cur, pt);
463        }
464        None
465    }
466}
467
468fn point_key(pt: &Point) -> Vec<u8> {
469    match pt {
470        Point::Infinity => vec![0xff],
471        Point::Affine(x, y) => {
472            let (_, xb) = x.to_le_bytes();
473            let (_, yb) = y.to_le_bytes();
474            let mut k = vec![0x00, xb.len() as u8];
475            k.extend(xb);
476            k.extend(yb);
477            k
478        }
479    }
480}
481
482/// Solve the **elliptic-curve discrete log** `Q = k·P` by baby-step/giant-step, given the order `n` of `P`.
483/// `O(√n)` group operations — the best generic attack, and exponential in the bit length. This is exactly
484/// why a sound (large prime-order) curve resists, and why ECC uses far smaller keys than RSA. `None` if `Q`
485/// is not a multiple of `P`.
486pub fn ecdlp_bsgs(curve: &Curve, base: &Point, target: &Point, n: u64) -> Option<BigInt> {
487    let m = (n as f64).sqrt() as u64 + 1;
488    let mut baby: HashMap<Vec<u8>, u64> = HashMap::new();
489    let mut cur = Point::Infinity;
490    for j in 0..m {
491        baby.entry(point_key(&cur)).or_insert(j);
492        cur = curve.add(&cur, base);
493    }
494    let neg_mp = curve.negate(&curve.mul(&i(m as i64), base)); // −(m·P)
495    let mut gamma = target.clone();
496    for step in 0..=m {
497        if let Some(&j) = baby.get(&point_key(&gamma)) {
498            return Some(i((step * m + j) as i64));
499        }
500        gamma = curve.add(&gamma, &neg_mp);
501    }
502    None
503}
504
505/// The known STRUCTURAL weaknesses that make an elliptic curve's ECDLP breakable — the symmetries a sound
506/// curve must avoid.
507#[derive(Clone, Debug, PartialEq, Eq)]
508pub enum CurveWeakness {
509    /// `#E(𝔽_p) = p` (trace 1): **anomalous** — Smart's attack solves the ECDLP in *polynomial* time.
510    Anomalous,
511    /// `#E(𝔽_p) = p + 1` (trace 0): **supersingular** — small embedding degree; MOV maps to a sub-exp DLP.
512    Supersingular,
513    /// The order's largest prime factor is small: **Pohlig–Hellman** shrinks the ECDLP to that subgroup.
514    SmoothOrder { largest_prime_factor: u64 },
515}
516
517/// Audit a curve of known order `#E` over `𝔽_p` for the structural ECDLP weaknesses. `None` means the only
518/// attacks that apply are the generic `O(√·)` ones — the honest ceiling, not a proof of security.
519pub fn curve_security(p: u64, order: u64) -> Option<CurveWeakness> {
520    if order == p {
521        return Some(CurveWeakness::Anomalous);
522    }
523    if order == p + 1 {
524        return Some(CurveWeakness::Supersingular);
525    }
526    let lpf = largest_prime_factor(order);
527    if lpf.saturating_mul(lpf) < order {
528        return Some(CurveWeakness::SmoothOrder {
529            largest_prime_factor: lpf,
530        });
531    }
532    None
533}
534
535fn largest_prime_factor(mut m: u64) -> u64 {
536    let mut largest = 1u64;
537    let mut d = 2u64;
538    while d * d <= m {
539        while m % d == 0 {
540            largest = d;
541            m /= d;
542        }
543        d += 1;
544    }
545    largest.max(m)
546}
547
548// ---- Isogenies: the maps BETWEEN elliptic curves — where the new mathematics lives -------------------
549//
550// An isogeny φ: E → E' is a nonconstant morphism that is also a group homomorphism; its kernel is a finite
551// subgroup, and its degree is the kernel size. Isogenies are the edges of the isogeny graph, the object
552// underneath CSIDH and SIKE — and the place a symmetry break (Castryck–Decru, 2022) collapsed a whole
553// post-quantum finalist by exploiting hidden torsion/endomorphism structure. Two curves are the same
554// vertex iff they share a **j-invariant** (the isomorphism symmetry). Given a kernel, **Vélu's formulas**
555// build φ and the codomain E'. A deep invariant we exploit as a test oracle: isogenous curves have the
556// SAME number of points (Tate) — the group order is an isogeny invariant.
557
558impl Curve {
559    /// The **j-invariant** `1728 · 4a³ / (4a³ + 27b²)` — the complete isomorphism invariant of the curve
560    /// (two curves are isomorphic over the algebraic closure iff their j-invariants agree). `None` if the
561    /// curve is singular (`4a³ + 27b² ≡ 0`).
562    pub fn j_invariant(&self) -> Option<BigInt> {
563        let p = &self.p;
564        let a3 = mulmod(&mulmod(&self.a, &self.a, p), &self.a, p);
565        let four_a3 = mulmod(&i(4), &a3, p);
566        let disc = addmod(
567            &four_a3,
568            &mulmod(&i(27), &mulmod(&self.b, &self.b, p), p),
569            p,
570        );
571        if disc.is_zero() {
572            return None;
573        }
574        Some(mulmod(
575            &mulmod(&i(1728), &four_a3, p),
576            &mod_inverse(&disc, p)?,
577            p,
578        ))
579    }
580}
581
582/// A separable isogeny `φ: E → E'` of odd prime degree `ℓ`, built from a kernel generator by Vélu's
583/// formulas. Stores the codomain and, for each kernel representative `Q` (one per `±` pair), the Vélu
584/// quantities `(xQ, vQ = 6xQ²+2a, uQ = 4yQ²)` used to evaluate `φ`.
585#[derive(Clone, Debug)]
586pub struct Isogeny {
587    pub domain: Curve,
588    pub codomain: Curve,
589    pub degree: u64,
590    kernel: Vec<(BigInt, BigInt, BigInt)>, // (xQ, vQ, uQ)
591}
592
593impl Isogeny {
594    /// Build the `ℓ`-isogeny with kernel `⟨gen⟩` by **Vélu's formulas** (`ℓ` an odd prime, `gen` of order
595    /// exactly `ℓ`). The codomain is `y² = x³ + (a − 5v)x + (b − 7w)` where `v = Σ vQ`, `w = Σ (uQ + xQ·vQ)`
596    /// over the `(ℓ−1)/2` kernel representatives. `None` unless `ℓ` is an odd prime and `gen` has order `ℓ`.
597    pub fn from_kernel(curve: &Curve, gen: &Point, ell: u64) -> Option<Isogeny> {
598        if ell < 3 || ell % 2 == 0 {
599            return None;
600        }
601        let p = &curve.p;
602        let mut kernel = Vec::with_capacity(((ell - 1) / 2) as usize);
603        let mut cur = gen.clone();
604        for _ in 0..((ell - 1) / 2) {
605            match &cur {
606                Point::Affine(xq, yq) => {
607                    let vq = addmod(
608                        &mulmod(&i(6), &mulmod(xq, xq, p), p),
609                        &mulmod(&i(2), &curve.a, p),
610                        p,
611                    );
612                    let uq = mulmod(&i(4), &mulmod(yq, yq, p), p);
613                    kernel.push((xq.clone(), vq, uq));
614                }
615                Point::Infinity => return None, // gen's order is smaller than ℓ
616            }
617            cur = curve.add(&cur, gen);
618        }
619        // Confirm the order is exactly ℓ (odd prime): ℓ·gen = O and gen ≠ O.
620        let _ = cur;
621        if matches!(gen, Point::Infinity) || curve.mul(&i(ell as i64), gen) != Point::Infinity {
622            return None;
623        }
624        let (mut vsum, mut wsum) = (i(0), i(0));
625        for (xq, vq, uq) in &kernel {
626            vsum = addmod(&vsum, vq, p);
627            wsum = addmod(&wsum, &addmod(uq, &mulmod(xq, vq, p), p), p);
628        }
629        let a2 = submod(&curve.a, &mulmod(&i(5), &vsum, p), p);
630        let b2 = submod(&curve.b, &mulmod(&i(7), &wsum, p), p);
631        Some(Isogeny {
632            domain: curve.clone(),
633            codomain: Curve::new(a2, b2, p.clone()),
634            degree: ell,
635            kernel,
636        })
637    }
638
639    /// Evaluate `φ` at a point. Kernel points map to the identity. For `P = (x, y) ∉ ker`, the x-map is
640    /// `X = x + Σ [ vQ/(x−xQ) + uQ/(x−xQ)² ]` and — since a normalized isogeny pulls back the invariant
641    /// differential (`φ*(dX/Y) = dx/y`) — the y-coordinate is `Y = y · X'(x) = y·[1 − Σ (vQ/(x−xQ)² +
642    /// 2uQ/(x−xQ)³)]`.
643    pub fn eval(&self, pt: &Point) -> Point {
644        let p = &self.domain.p;
645        match pt {
646            Point::Infinity => Point::Infinity,
647            Point::Affine(x, y) => {
648                let mut xnew = x.clone();
649                let mut yfac = i(1);
650                for (xq, vq, uq) in &self.kernel {
651                    let d = submod(x, xq, p);
652                    if d.is_zero() {
653                        return Point::Infinity; // P = ±Q ∈ ker
654                    }
655                    let di = mod_inverse(&d, p).expect("nonzero over 𝔽_p");
656                    let di2 = mulmod(&di, &di, p);
657                    let di3 = mulmod(&di2, &di, p);
658                    xnew = addmod(
659                        &xnew,
660                        &addmod(&mulmod(vq, &di, p), &mulmod(uq, &di2, p), p),
661                        p,
662                    );
663                    yfac = submod(
664                        &yfac,
665                        &addmod(
666                            &mulmod(vq, &di2, p),
667                            &mulmod(&mulmod(&i(2), uq, p), &di3, p),
668                            p,
669                        ),
670                        p,
671                    );
672                }
673                Point::Affine(xnew, mulmod(y, &yfac, p))
674            }
675        }
676    }
677}
678
679// ---- The Weil pairing: the ultimate symmetry on torsion --------------------------------------------
680//
681// `e_N: E[N] × E[N] → μ_N` is the canonical pairing on the N-torsion — bilinear, alternating
682// (`e(P,P)=1`), non-degenerate, and Galois/isogeny-compatible: `e_N(φP, φQ) = e_N(P,Q)^{deg φ}`. That last
683// law is the symmetry the torsion images in SIKE are FORCED to obey, and the lever the Castryck–Decru
684// break pulls. We compute it by Miller's algorithm (a double-and-add accumulating line-function values).
685
686/// The pair `(ℓ(Q), v(Q))` for the DOUBLING step: the tangent line at `T` and the vertical at `2T`,
687/// evaluated at `Q = (xq, yq)`.
688fn miller_double_lines(c: &Curve, t: &Point, xq: &BigInt, yq: &BigInt) -> Option<(BigInt, BigInt)> {
689    let p = &c.p;
690    let (xt, yt) = match t {
691        Point::Affine(x, y) => (x, y),
692        Point::Infinity => return None,
693    };
694    if yt.is_zero() {
695        return None; // 2-torsion; avoided for odd order
696    }
697    let lam = mulmod(
698        &addmod(&mulmod(&i(3), &mulmod(xt, xt, p), p), &c.a, p),
699        &mod_inverse(&mulmod(&i(2), yt, p), p)?,
700        p,
701    );
702    let ell = submod(&submod(yq, yt, p), &mulmod(&lam, &submod(xq, xt, p), p), p);
703    let t2 = c.double(t);
704    let vert = match &t2 {
705        Point::Affine(x2, _) => submod(xq, x2, p),
706        Point::Infinity => i(1), // 2T = O: no vertical factor
707    };
708    Some((ell, vert))
709}
710
711/// The pair `(ℓ(Q), v(Q))` for the ADDITION step: the chord through `T` and `P`, and the vertical at
712/// `T + P`, evaluated at `Q`.
713fn miller_add_lines(
714    c: &Curve,
715    t: &Point,
716    pp: &Point,
717    xq: &BigInt,
718    yq: &BigInt,
719) -> Option<(BigInt, BigInt)> {
720    let p = &c.p;
721    let ((xt, yt), (xpp, ypp)) = match (t, pp) {
722        (Point::Affine(a, b), Point::Affine(cc, d)) => ((a, b), (cc, d)),
723        _ => return None,
724    };
725    if xt == xpp {
726        if yt == ypp {
727            return miller_double_lines(c, t, xq, yq); // T = P
728        }
729        // T = −P ⟹ T + P = O: the line is the vertical through xt.
730        return Some((submod(xq, xt, p), i(1)));
731    }
732    let lam = mulmod(
733        &submod(ypp, yt, p),
734        &mod_inverse(&submod(xpp, xt, p), p)?,
735        p,
736    );
737    let ell = submod(&submod(yq, yt, p), &mulmod(&lam, &submod(xq, xt, p), p), p);
738    let sum = c.add(t, pp);
739    let vert = match &sum {
740        Point::Affine(x3, _) => submod(xq, x3, p),
741        Point::Infinity => i(1),
742    };
743    Some((ell, vert))
744}
745
746/// Miller's function `f_{n,P}(Q)` as a field element (numerator·denominator⁻¹, batched to one inversion).
747fn miller(c: &Curve, pp: &Point, qq: &Point, n: u64) -> Option<BigInt> {
748    let p = &c.p;
749    let (xq, yq) = match qq {
750        Point::Affine(x, y) => (x, y),
751        Point::Infinity => return None,
752    };
753    let (mut num, mut den) = (i(1), i(1));
754    let mut t = pp.clone();
755    for bit in (0..(64 - n.leading_zeros() - 1)).rev() {
756        let (ell, vert) = miller_double_lines(c, &t, xq, yq)?;
757        num = mulmod(&mulmod(&num, &num, p), &ell, p);
758        den = mulmod(&mulmod(&den, &den, p), &vert, p);
759        t = c.double(&t);
760        if (n >> bit) & 1 == 1 {
761            let (ell, vert) = miller_add_lines(c, &t, pp, xq, yq)?;
762            num = mulmod(&num, &ell, p);
763            den = mulmod(&den, &vert, p);
764            t = c.add(&t, pp);
765        }
766    }
767    if den.is_zero() {
768        return None;
769    }
770    Some(mulmod(&num, &mod_inverse(&den, p)?, p))
771}
772
773/// The **Weil pairing** `e_N(P, Q) ∈ μ_N` for independent `N`-torsion points `P, Q`, via Miller:
774/// `e_N(P,Q) = (−1)ᴺ · f_{N,P}(Q) / f_{N,Q}(P)`. Bilinear, alternating, non-degenerate, and (the SIKE-
775/// relevant law) isogeny-compatible. `None` if a Miller evaluation degenerates (e.g. dependent points).
776pub fn weil_pairing(c: &Curve, pp: &Point, qq: &Point, n: u64) -> Option<BigInt> {
777    if pp == qq || matches!(pp, Point::Infinity) || matches!(qq, Point::Infinity) {
778        return Some(i(1)); // e(P,P)=1 and the degenerate cases
779    }
780    let fp = miller(c, pp, qq, n)?;
781    let fq = miller(c, qq, pp, n)?;
782    let ratio = mulmod(&fp, &mod_inverse(&fq, &c.p)?, &c.p);
783    let e = if n % 2 == 1 {
784        submod(&i(0), &ratio, &c.p)
785    } else {
786        ratio
787    }; // (−1)ᴺ
788    Some(e)
789}
790
791/// A square root of `a` mod `p` for `p ≡ 3 (mod 4)` (the SIDH regime): `a^{(p+1)/4}`; `None` for a
792/// non-residue.
793fn sqrt_fp(a: &BigInt, p: &BigInt) -> Option<BigInt> {
794    let exp = p.add(&i(1)).div_rem(&i(4))?.0;
795    let r = modpow(a, &exp, p);
796    (mulmod(&r, &r, p) == rem_pos(a, p)).then_some(r)
797}
798
799/// Every affine point of the curve (requires `p ≡ 3 (mod 4)`). `O(p)`.
800fn all_affine_points(curve: &Curve) -> Vec<Point> {
801    let pu = curve.p.to_i64().expect("small prime") as u64;
802    let mut v = Vec::new();
803    for xu in 0..pu {
804        let x = i(xu as i64);
805        let x3 = mulmod(&mulmod(&x, &x, &curve.p), &x, &curve.p);
806        let rhs = addmod(
807            &addmod(&x3, &mulmod(&curve.a, &x, &curve.p), &curve.p),
808            &curve.b,
809            &curve.p,
810        );
811        if rhs.is_zero() {
812            v.push(Point::Affine(x, i(0)));
813        } else if let Some(y) = sqrt_fp(&rhs, &curve.p) {
814            v.push(Point::Affine(x.clone(), submod(&i(0), &y, &curve.p)));
815            v.push(Point::Affine(x, y));
816        }
817    }
818    v
819}
820
821/// A **torsion basis** of `E[n]` (`n` prime): two independent points of order `n` generating the full
822/// `n`-torsion `(ℤ/n)²`, or `None` if the `n`-torsion is not fully rational. Requires `p ≡ 3 (mod 4)`. This
823/// is the public torsion basis whose images an SIDH/SIKE key publishes.
824pub fn torsion_basis(curve: &Curve, n: u64) -> Option<(Point, Point)> {
825    let order_n: Vec<Point> = all_affine_points(curve)
826        .into_iter()
827        .filter(|pt| curve.mul(&i(n as i64), pt) == Point::Infinity)
828        .collect();
829    for p in &order_n {
830        let span: Vec<Point> = (0..n).map(|k| curve.mul(&i(k as i64), p)).collect();
831        if let Some(q) = order_n.iter().find(|q| !span.contains(q)) {
832            return Some((p.clone(), q.clone()));
833        }
834    }
835    None
836}
837
838/// A single point of prime order `ell` on the curve (a candidate isogeny-kernel generator), or `None` if
839/// there is no rational `ell`-torsion. Requires `p ≡ 3 (mod 4)`.
840pub fn point_of_order(curve: &Curve, ell: u64) -> Option<Point> {
841    all_affine_points(curve)
842        .into_iter()
843        .find(|pt| curve.mul(&i(ell as i64), pt) == Point::Infinity)
844}
845
846/// The SIDH kernel generator `P + [s]·Q` from a torsion basis `(P, Q)` and the secret scalar `s`. The secret
847/// isogeny is the quotient by `⟨P + [s]Q⟩`; Kani's gluing is what lets an attacker recover `s` from the
848/// published torsion images, after which [`derive_isogeny_path`] unfolds the whole chain.
849pub fn kernel_generator(curve: &Curve, p_pt: &Point, q_pt: &Point, s: &BigInt) -> Point {
850    curve.add(p_pt, &curve.mul(s, q_pt))
851}
852
853/// A single `ℓ`-isogeny step in a chain: the `domain` curve, the order-`ℓ` `kernel` point quotiented at this
854/// step, and the resulting `codomain`.
855#[derive(Clone, Debug, PartialEq, Eq)]
856pub struct IsogenyStep {
857    pub domain: Curve,
858    pub kernel: Point,
859    pub codomain: Curve,
860}
861
862/// **Torsion-image → path derivation.** A degree-`ℓᵃ` isogeny is pinned down by a *single* kernel generator
863/// `gen` of order `ℓᵃ` — the datum the SIDH/SIKE torsion images reconstruct (via Kani's gluing). This unfolds
864/// that one generator into the explicit chain of `a` prime-degree `ℓ`-isogenies: at step `i` the kernel is
865/// the order-`ℓ` point `[ℓ^{a−1−i}]·genᵢ`, and `gen` is pushed forward through each step so its order descends
866/// `ℓᵃ → ℓᵃ⁻¹ → … → 1`. The entire secret path pops out of the one meta-datum — the generator is the rule
867/// that emits the per-step rules. Requires `ℓ` an odd prime and `gen` of order exactly `ℓᵃ`.
868pub fn derive_isogeny_path(
869    curve: &Curve,
870    gen: &Point,
871    ell: u64,
872    a: u32,
873) -> Option<Vec<IsogenyStep>> {
874    let mut steps = Vec::with_capacity(a as usize);
875    let mut e = curve.clone();
876    let mut g = gen.clone();
877    for step in 0..a {
878        let mut mult = i(1);
879        for _ in 0..(a - 1 - step) {
880            mult = mult.mul(&i(ell as i64));
881        }
882        let k = e.mul(&mult, &g); // [ℓ^{a−1−step}]·g — order exactly ℓ
883        let iso = Isogeny::from_kernel(&e, &k, ell)?;
884        steps.push(IsogenyStep {
885            domain: e.clone(),
886            kernel: k,
887            codomain: iso.codomain.clone(),
888        });
889        g = iso.eval(&g);
890        e = iso.codomain;
891    }
892    Some(steps)
893}
894
895#[cfg(test)]
896#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/elliptic/tests.rs"]
897mod tests;