1//! Short Weierstrass curve y² = x³ + ax + b over F_p (p < 2^62), affine points in Montgomery form.2//!3//! Conventions match `src/wp34/ec.py`: affine coordinates, `None`/`Pt::INF` is the point at infinity,4//! the group law counts one group addition (`add`) or doubling (`dbl`) plus one field inversion (`inv`)5//! and the field multiplications (`mul`, squarings included) actually performed.67use crate::field::Field;8use serde::{Deserialize, Serialize};910#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Serialize, Deserialize)]11pub struct Counters {12 pub add: u64,13 pub dbl: u64,14 pub inv: u64,15 pub mul: u64,16}1718impl Counters {19 #[inline]20 pub fn merge(&mut self, o: &Counters) {21 self.add += o.add;22 self.dbl += o.dbl;23 self.inv += o.inv;24 self.mul += o.mul;25 }26 pub fn group_ops(&self) -> u64 {27 self.add + self.dbl28 }29}3031/// Affine point in Montgomery form; `inf` marks the point at infinity.32#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]33pub struct Pt {34 pub x: u64,35 pub y: u64,36 pub inf: bool,37}3839impl Pt {40 pub const INF: Pt = Pt { x: 0, y: 0, inf: true };41 #[inline(always)]42 pub fn new(x: u64, y: u64) -> Pt {43 Pt { x, y, inf: false }44 }45}4647#[derive(Clone, Copy, Debug)]48pub struct Curve {49 pub f: Field,50 /// a, b in Montgomery form51 pub a: u64,52 pub b: u64,53 /// standard-form a, b (for JSON / checks)54 pub a_std: u64,55 pub b_std: u64,56}5758impl Curve {59 pub fn new(p: u64, a: u64, b: u64) -> Curve {60 let f = Field::new(p);61 assert!(a < p && b < p, "a, b must be reduced mod p");62 // discriminant check: 4a³ + 27b² ≠ 063 let am = f.to_mont(a);64 let bm = f.to_mont(b);65 let a3 = f.mul(f.mul(am, am), am);66 let d = f.add(f.mul(f.to_mont(4 % p), a3), f.mul(f.to_mont(27 % p), f.sqr(bm)));67 assert!(d != 0, "singular curve");68 Curve { f, a: am, b: bm, a_std: a, b_std: b }69 }7071 #[inline]72 pub fn p(&self) -> u64 {73 self.f.p74 }7576 pub fn point_from_std(&self, x: u64, y: u64) -> Pt {77 Pt::new(self.f.to_mont(x % self.f.p), self.f.to_mont(y % self.f.p))78 }7980 pub fn point_to_std(&self, p: &Pt) -> Option<(u64, u64)> {81 if p.inf {82 None83 } else {84 Some((self.f.from_mont(p.x), self.f.from_mont(p.y)))85 }86 }8788 pub fn is_on_curve(&self, pt: &Pt) -> bool {89 if pt.inf {90 return true;91 }92 let f = &self.f;93 let lhs = f.sqr(pt.y);94 let rhs = f.add(f.add(f.mul(f.sqr(pt.x), pt.x), f.mul(self.a, pt.x)), self.b);95 lhs == rhs96 }9798 #[inline(always)]99 pub fn neg(&self, pt: &Pt) -> Pt {100 if pt.inf {101 *pt102 } else {103 Pt::new(pt.x, self.f.neg(pt.y))104 }105 }106107 /// Full affine addition with all special cases (one inversion). Counted.108 pub fn add(&self, p: &Pt, q: &Pt, c: &mut Counters) -> Pt {109 if p.inf {110 return *q;111 }112 if q.inf {113 return *p;114 }115 let f = &self.f;116 if p.x == q.x {117 if f.add(p.y, q.y) == 0 {118 return Pt::INF;119 }120 return self.dbl(p, c);121 }122 c.add += 1;123 c.inv += 1;124 c.mul += 3;125 let lam = f.mul(f.sub(q.y, p.y), f.inv(f.sub(q.x, p.x)));126 self.finish_add(p, q.x, lam)127 }128129 /// Doubling with all special cases (one inversion). Counted.130 pub fn dbl(&self, p: &Pt, c: &mut Counters) -> Pt {131 if p.inf || p.y == 0 {132 return Pt::INF;133 }134 let f = &self.f;135 c.dbl += 1;136 c.inv += 1;137 c.mul += 4;138 let num = f.add(f.mul(f.to_mont(3), f.sqr(p.x)), self.a);139 let lam = f.mul(num, f.inv(f.dbl(p.y)));140 self.finish_dbl(p, lam)141 }142143 /// Given the slope λ of the chord through p and q (q.x = `qx`), compute p + q.144 /// Costs 2 field multiplications (λ², λ·(x1−x3)); counted by the caller.145 #[inline(always)]146 pub fn finish_add(&self, p: &Pt, qx: u64, lam: u64) -> Pt {147 let f = &self.f;148 let x3 = f.sub(f.sub(f.sqr(lam), p.x), qx);149 let y3 = f.sub(f.mul(lam, f.sub(p.x, x3)), p.y);150 Pt::new(x3, y3)151 }152153 /// Given the tangent slope λ at p, compute 2p (2 multiplications, counted by caller).154 #[inline(always)]155 pub fn finish_dbl(&self, p: &Pt, lam: u64) -> Pt {156 let f = &self.f;157 let x3 = f.sub(f.sqr(lam), f.dbl(p.x));158 let y3 = f.sub(f.mul(lam, f.sub(p.x, x3)), p.y);159 Pt::new(x3, y3)160 }161162 /// Numerator of the tangent slope: 3x² + a (one squaring + one multiplication, counted by caller).163 #[inline(always)]164 pub fn tangent_num(&self, p: &Pt) -> u64 {165 let f = &self.f;166 f.add(f.mul(f.to_mont(3), f.sqr(p.x)), self.a)167 }168169 /// Left-to-right double-and-add scalar multiplication (k any u64). Counted.170 pub fn mul(&self, k: u64, p: &Pt, c: &mut Counters) -> Pt {171 if p.inf || k == 0 {172 return Pt::INF;173 }174 let mut r = Pt::INF;175 let bits = 64 - k.leading_zeros();176 for i in (0..bits).rev() {177 r = self.dbl(&r, c);178 if (k >> i) & 1 == 1 {179 r = self.add(&r, p, c);180 }181 }182 r183 }184185 pub fn eq(&self, p: &Pt, q: &Pt) -> bool {186 if p.inf || q.inf {187 return p.inf && q.inf;188 }189 p.x == q.x && p.y == q.y190 }191192 /// Random point by lifting random x (standard-form output converted to Montgomery).193 pub fn random_point<R: rand::Rng>(&self, rng: &mut R) -> Pt {194 let f = &self.f;195 loop {196 let x = rng.random_range(0..f.p);197 let xm = f.to_mont(x);198 let rhs = f.add(f.add(f.mul(f.sqr(xm), xm), f.mul(self.a, xm)), self.b);199 if let Some(y) = f.sqrt_plain(f.from_mont(rhs)) {200 let y = if rng.random_bool(0.5) { y } else { (f.p - y) % f.p };201 return Pt::new(xm, f.to_mont(y));202 }203 }204 }205}206207/// Fixed-base comb table: 16 nibble positions × 16 entries, so that k·P costs ≤ 15 additions208/// (plus the table precomputation). Used to start random walks cheaply (u·G + v·Q).209pub struct CombTable {210 pub table: Vec<[Pt; 16]>, // table[i][d] = d·16^i·P211}212213impl CombTable {214 pub fn new(curve: &Curve, p: &Pt, c: &mut Counters) -> CombTable {215 let mut table = Vec::with_capacity(16);216 let mut base = *p; // 16^i P217 for _ in 0..16 {218 let mut row = [Pt::INF; 16];219 for d in 1..16 {220 row[d] = curve.add(&row[d - 1], &base, c);221 }222 // next base = 16·base223 let mut nb = base;224 for _ in 0..4 {225 nb = curve.dbl(&nb, c);226 }227 base = nb;228 table.push(row);229 }230 CombTable { table }231 }232233 pub fn mul(&self, curve: &Curve, k: u64, c: &mut Counters) -> Pt {234 let mut r = Pt::INF;235 for i in 0..16 {236 let d = ((k >> (4 * i)) & 0xF) as usize;237 if d != 0 {238 r = curve.add(&r, &self.table[i][d], c);239 }240 }241 r242 }243}244