1use 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#[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
53pub 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); let t2 = mulmod(&xmz, &xmz, n); let x2 = mulmod(&t1, &t2, n); let t3 = submod(&t1, &t2, n); let inner = addmod(&t2, &mulmod(a24, &t3, n), n); let z2 = mulmod(&t3, &inner, n);
64 (x2, z2)
65}
66
67pub 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); let b = mulmod(&addmod(xp, zp, n), &submod(xq, zq, n), n); let s = addmod(&a, &b, n);
81 let d = submod(&a, &b, n);
82 let xr = mulmod(zd, &mulmod(&s, &s, n), n); let zr = mulmod(xd, &mulmod(&d, &d, n), n); (xr, zr)
85}
86
87pub fn ladder(k: u64, x: &BigInt, z: &BigInt, a24: &BigInt, n: &BigInt) -> (BigInt, BigInt) {
90 if k == 0 {
91 return (i(0), i(0)); }
93 if k == 1 {
94 return (x.clone(), z.clone());
95 }
96 let mut r0 = (x.clone(), z.clone()); let mut r1 = xdbl(x, z, a24, n); 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
110fn 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
132fn 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; let half = (d / 2) as usize;
149
150 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 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; }
181
182 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
210fn 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); let v = mulmod(&i(4), &sigma, n); 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); let den = mulmod(&mulmod(&i(4), &u3, n), &v, n); 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 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#[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
255pub 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
268pub 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
281pub 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#[derive(Clone, Debug, PartialEq, Eq)]
316pub struct Curve {
317 pub a: BigInt,
318 pub b: BigInt,
319 pub p: BigInt,
320}
321
322#[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 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 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 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; }
369 return self.double(p1); }
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 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; }
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 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 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; let one = i(1);
437 let mut count = 1u64; 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; }
451 }
452 count
453 }
454
455 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
482pub 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)); 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#[derive(Clone, Debug, PartialEq, Eq)]
508pub enum CurveWeakness {
509 Anomalous,
511 Supersingular,
513 SmoothOrder { largest_prime_factor: u64 },
515}
516
517pub 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
548impl Curve {
559 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#[derive(Clone, Debug)]
586pub struct Isogeny {
587 pub domain: Curve,
588 pub codomain: Curve,
589 pub degree: u64,
590 kernel: Vec<(BigInt, BigInt, BigInt)>, }
592
593impl Isogeny {
594 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, }
617 cur = curve.add(&cur, gen);
618 }
619 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 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; }
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
679fn 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; }
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), };
708 Some((ell, vert))
709}
710
711fn 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); }
729 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
746fn 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
773pub 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)); }
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 }; Some(e)
789}
790
791fn 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
799fn 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
821pub 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
838pub 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
846pub 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#[derive(Clone, Debug, PartialEq, Eq)]
856pub struct IsogenyStep {
857 pub domain: Curve,
858 pub kernel: Point,
859 pub codomain: Curve,
860}
861
862pub 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); 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;