1use crate::factor::{mod_inverse, modpow};
21use logicaffeine_base::BigInt;
22
23#[inline]
24fn ib(x: i64) -> BigInt {
25 BigInt::from_i64(x)
26}
27#[inline]
28fn rp(a: &BigInt, p: &BigInt) -> BigInt {
29 let r = a.div_rem(p).map(|(_, r)| r).unwrap_or_else(|| a.clone());
30 if r.is_negative() {
31 r.add(p)
32 } else {
33 r
34 }
35}
36#[inline]
37fn mm(a: &BigInt, b: &BigInt, p: &BigInt) -> BigInt {
38 rp(&a.mul(b), p)
39}
40#[inline]
41fn am(a: &BigInt, b: &BigInt, p: &BigInt) -> BigInt {
42 rp(&a.add(b), p)
43}
44#[inline]
45fn sm(a: &BigInt, b: &BigInt, p: &BigInt) -> BigInt {
46 rp(&a.sub(b), p)
47}
48
49pub type Quad = [BigInt; 3];
51
52pub fn poly_mul(a: &[BigInt], b: &[BigInt], p: &BigInt) -> Vec<BigInt> {
54 if a.is_empty() || b.is_empty() {
55 return Vec::new();
56 }
57 let mut r = vec![ib(0); a.len() + b.len() - 1];
58 for (i, ai) in a.iter().enumerate() {
59 for (j, bj) in b.iter().enumerate() {
60 r[i + j] = am(&r[i + j], &mm(ai, bj, p), p);
61 }
62 }
63 r
64}
65
66pub fn poly_deriv(a: &[BigInt], p: &BigInt) -> Vec<BigInt> {
68 (1..a.len()).map(|i| mm(&ib(i as i64), &a[i], p)).collect()
69}
70
71fn poly_sub(a: &[BigInt], b: &[BigInt], p: &BigInt) -> Vec<BigInt> {
72 let n = a.len().max(b.len());
73 (0..n)
74 .map(|i| sm(a.get(i).unwrap_or(&ib(0)), b.get(i).unwrap_or(&ib(0)), p))
75 .collect()
76}
77
78fn poly_trim(mut a: Vec<BigInt>) -> Vec<BigInt> {
80 while a.len() > 1 && a.last().is_some_and(|c| c.is_zero()) {
81 a.pop();
82 }
83 a
84}
85
86#[derive(Clone, Debug)]
88pub struct Richelot {
89 pub delta: BigInt,
91 pub domain: Vec<BigInt>,
93 pub codomain: Vec<BigInt>,
95 pub dual: [Vec<BigInt>; 3],
97}
98
99impl Richelot {
100 pub fn is_split(&self) -> bool {
103 self.delta.is_zero()
104 }
105}
106
107pub fn richelot(g: &[Quad; 3], p: &BigInt) -> Richelot {
109 let m = |i: usize, j: usize| &g[i][2 - j]; let det = {
112 let t1 = mm(
113 m(0, 0),
114 &sm(&mm(m(1, 1), m(2, 2), p), &mm(m(1, 2), m(2, 1), p), p),
115 p,
116 );
117 let t2 = mm(
118 m(0, 1),
119 &sm(&mm(m(1, 0), m(2, 2), p), &mm(m(1, 2), m(2, 0), p), p),
120 p,
121 );
122 let t3 = mm(
123 m(0, 2),
124 &sm(&mm(m(1, 0), m(2, 1), p), &mm(m(1, 1), m(2, 0), p), p),
125 p,
126 );
127 am(&sm(&t1, &t2, p), &t3, p)
128 };
129
130 let quad = |q: &Quad| vec![q[0].clone(), q[1].clone(), q[2].clone()];
132 let dual_of = |j: usize, k: usize| {
133 let (gj, gk) = (quad(&g[j]), quad(&g[k]));
134 let (dj, dk) = (poly_deriv(&gj, p), poly_deriv(&gk, p));
135 poly_trim(poly_sub(&poly_mul(&gj, &dk, p), &poly_mul(&dj, &gk, p), p))
136 };
137 let dual = [dual_of(1, 2), dual_of(2, 0), dual_of(0, 1)];
138
139 let domain = poly_mul(&poly_mul(&quad(&g[0]), &quad(&g[1]), p), &quad(&g[2]), p);
140 let codomain = poly_mul(&poly_mul(&dual[0], &dual[1], p), &dual[2], p);
141
142 Richelot {
143 delta: det,
144 domain,
145 codomain,
146 dual,
147 }
148}
149
150pub fn richelot_partitions(roots: &[BigInt; 6], p: &BigInt) -> Vec<[Quad; 3]> {
153 fn quad_from(ra: &BigInt, rb: &BigInt, p: &BigInt) -> Quad {
154 [mm(ra, rb, p), sm(&ib(0), &am(ra, rb, p), p), ib(1)]
156 }
157 let idx = [0usize, 1, 2, 3, 4, 5];
158 let mut out = Vec::new();
159 for a in 1..6 {
161 let rest1: Vec<usize> = idx.iter().copied().filter(|&x| x != 0 && x != a).collect();
162 let b0 = rest1[0];
163 for bi in 1..rest1.len() {
164 let b = rest1[bi];
165 let rest2: Vec<usize> = rest1
166 .iter()
167 .copied()
168 .filter(|&x| x != b0 && x != b)
169 .collect();
170 let (c, d) = (rest2[0], rest2[1]);
171 out.push([
172 quad_from(&roots[0], &roots[a], p),
173 quad_from(&roots[b0], &roots[b], p),
174 quad_from(&roots[c], &roots[d], p),
175 ]);
176 }
177 }
178 out
179}
180
181pub fn find_split_neighbour(roots: &[BigInt; 6], p: &BigInt) -> Option<[Quad; 3]> {
187 richelot_partitions(roots, p)
188 .into_iter()
189 .find(|g| richelot(g, p).is_split())
190}
191
192pub fn poly_eval(a: &[BigInt], x: &BigInt, p: &BigInt) -> BigInt {
194 let mut acc = ib(0);
195 for c in a.iter().rev() {
196 acc = am(&mm(&acc, x, p), c, p);
197 }
198 acc
199}
200
201#[derive(Clone, Debug)]
206pub struct SplitGenus2 {
207 pub sextic: Vec<BigInt>,
209 pub e1: Vec<BigInt>,
211 pub e2: Vec<BigInt>,
213 pub p: BigInt,
214}
215
216pub fn split_jacobian_from_cubic(g: &[BigInt], p: &BigInt) -> SplitGenus2 {
220 let z = ib(0);
221 let sextic = vec![
222 rp(&g[0], p),
223 z.clone(),
224 rp(&g[1], p),
225 z.clone(),
226 rp(&g[2], p),
227 z.clone(),
228 rp(&g[3], p),
229 ];
230 SplitGenus2 {
231 sextic,
232 e1: g.iter().map(|c| rp(c, p)).collect(),
233 e2: g.iter().rev().map(|c| rp(c, p)).collect(),
234 p: p.clone(),
235 }
236}
237
238#[derive(Clone, Debug)]
246pub struct MatchedPairGlue {
247 pub sextic: Vec<BigInt>,
249 pub e1: Vec<BigInt>,
251 pub e2: Vec<BigInt>,
253 pub p: BigInt,
254}
255
256pub fn glue_shared_2torsion(c: &[BigInt; 3], p: &BigInt) -> MatchedPairGlue {
259 let quad = |ci: &BigInt| vec![ib(1), rp(ci, p), ib(1)]; let sextic = poly_mul(&poly_mul(&quad(&c[0]), &quad(&c[1]), p), &quad(&c[2]), p);
261 let lin = |r: BigInt| vec![rp(&r, p), ib(1)]; let core = poly_mul(
263 &poly_mul(&lin(c[0].clone()), &lin(c[1].clone()), p),
264 &lin(c[2].clone()),
265 p,
266 ); MatchedPairGlue {
268 sextic,
269 e1: poly_mul(&lin(ib(2)), &core, p), e2: poly_mul(&lin(ib(-2)), &core, p), p: p.clone(),
272 }
273}
274
275pub fn surface_is_reducible(roots: &[BigInt; 6], p: &BigInt) -> bool {
280 find_split_neighbour(roots, p).is_some()
281}
282
283pub fn select_splitting_branch(branches: &[[BigInt; 6]], p: &BigInt) -> Option<usize> {
288 branches.iter().position(|r| surface_is_reducible(r, p))
289}
290
291fn pdeg(a: &[BigInt]) -> isize {
299 (0..a.len())
300 .rev()
301 .find(|&i| !a[i].is_zero())
302 .map(|i| i as isize)
303 .unwrap_or(-1)
304}
305fn padd(a: &[BigInt], b: &[BigInt], p: &BigInt) -> Vec<BigInt> {
306 let n = a.len().max(b.len());
307 poly_trim(
308 (0..n)
309 .map(|i| am(a.get(i).unwrap_or(&ib(0)), b.get(i).unwrap_or(&ib(0)), p))
310 .collect(),
311 )
312}
313fn psub(a: &[BigInt], b: &[BigInt], p: &BigInt) -> Vec<BigInt> {
314 poly_trim(poly_sub(a, b, p))
315}
316fn pmul(a: &[BigInt], b: &[BigInt], p: &BigInt) -> Vec<BigInt> {
317 poly_trim(poly_mul(a, b, p))
318}
319fn pscale(a: &[BigInt], s: &BigInt, p: &BigInt) -> Vec<BigInt> {
320 poly_trim(a.iter().map(|c| mm(c, s, p)).collect())
321}
322fn pneg(a: &[BigInt], p: &BigInt) -> Vec<BigInt> {
323 pscale(a, &sm(&ib(0), &ib(1), p), p)
324}
325fn pmonic(a: &[BigInt], p: &BigInt) -> Vec<BigInt> {
326 let d = pdeg(a);
327 if d < 0 {
328 return vec![ib(0)];
329 }
330 pscale(a, &mod_inverse(&a[d as usize], p).unwrap(), p)
331}
332fn pdivmod(a: &[BigInt], b: &[BigInt], p: &BigInt) -> (Vec<BigInt>, Vec<BigInt>) {
334 let db = pdeg(b);
335 assert!(db >= 0, "division by the zero polynomial");
336 let binv = mod_inverse(&b[db as usize], p).unwrap();
337 let mut r = poly_trim(a.to_vec());
338 let mut q = vec![ib(0)];
339 while pdeg(&r) >= db {
340 let dr = pdeg(&r);
341 let shift = (dr - db) as usize;
342 let coef = mm(&r[dr as usize], &binv, p);
343 if q.len() <= shift {
344 q.resize(shift + 1, ib(0));
345 }
346 q[shift] = am(&q[shift], &coef, p);
347 let mut sub = vec![ib(0); shift];
348 sub.extend(b.iter().map(|c| mm(c, &coef, p)));
349 r = psub(&r, &sub, p);
350 }
351 (poly_trim(q), poly_trim(r))
352}
353fn pmod(a: &[BigInt], m: &[BigInt], p: &BigInt) -> Vec<BigInt> {
354 pdivmod(a, m, p).1
355}
356fn pdiv_exact(a: &[BigInt], b: &[BigInt], p: &BigInt) -> Vec<BigInt> {
357 pdivmod(a, b, p).0
358}
359fn pext_gcd(a: &[BigInt], b: &[BigInt], p: &BigInt) -> (Vec<BigInt>, Vec<BigInt>, Vec<BigInt>) {
361 let (mut r0, mut r1) = (poly_trim(a.to_vec()), poly_trim(b.to_vec()));
362 let (mut s0, mut s1) = (vec![ib(1)], vec![ib(0)]);
363 let (mut t0, mut t1) = (vec![ib(0)], vec![ib(1)]);
364 while pdeg(&r1) >= 0 {
365 let (q, r) = pdivmod(&r0, &r1, p);
366 r0 = r1;
367 r1 = r;
368 let ns = psub(&s0, &pmul(&q, &s1, p), p);
369 s0 = s1;
370 s1 = ns;
371 let nt = psub(&t0, &pmul(&q, &t1, p), p);
372 t0 = t1;
373 t1 = nt;
374 }
375 let d = pdeg(&r0);
376 if d > 0 || (d == 0 && r0[0] != ib(1)) {
377 let inv = mod_inverse(&r0[d as usize], p).unwrap();
378 r0 = pscale(&r0, &inv, p);
379 s0 = pscale(&s0, &inv, p);
380 t0 = pscale(&t0, &inv, p);
381 }
382 (r0, s0, t0)
383}
384
385#[derive(Clone, Debug, PartialEq, Eq)]
387pub struct Mumford {
388 pub u: Vec<BigInt>,
389 pub v: Vec<BigInt>,
390}
391
392pub fn jac_identity() -> Mumford {
394 Mumford {
395 u: vec![ib(1)],
396 v: vec![ib(0)],
397 }
398}
399
400pub fn jac_negate(d: &Mumford, p: &BigInt) -> Mumford {
402 Mumford {
403 u: d.u.clone(),
404 v: pmod(&pneg(&d.v, p), &d.u, p),
405 }
406}
407
408fn jac_reduce(mut u: Vec<BigInt>, mut v: Vec<BigInt>, f: &[BigInt], p: &BigInt) -> Mumford {
410 while pdeg(&u) > 2 {
411 let up = pdiv_exact(&psub(f, &pmul(&v, &v, p), p), &u, p);
412 let vp = pmod(&pneg(&v, p), &up, p);
413 u = up;
414 v = vp;
415 }
416 let um = pmonic(&u, p);
417 let vm = pmod(&v, &um, p);
418 Mumford { u: um, v: vm }
419}
420
421pub fn cantor_add(d1: &Mumford, d2: &Mumford, f: &[BigInt], p: &BigInt) -> Mumford {
423 let (u1, v1, u2, v2) = (&d1.u, &d1.v, &d2.u, &d2.v);
424 let (g1, e1, e2) = pext_gcd(u1, u2, p);
426 let vsum = padd(v1, v2, p);
427 let (d, c1, c2) = pext_gcd(&g1, &vsum, p);
428 let s1 = pmul(&c1, &e1, p);
429 let s2 = pmul(&c1, &e2, p);
430 let s3 = c2;
431 let u = pdiv_exact(&pmul(u1, u2, p), &pmul(&d, &d, p), p);
433 let num = padd(
434 &padd(
435 &pmul(&pmul(&s1, u1, p), v2, p),
436 &pmul(&pmul(&s2, u2, p), v1, p),
437 p,
438 ),
439 &pmul(&s3, &padd(&pmul(v1, v2, p), f, p), p),
440 p,
441 );
442 let v = pmod(&pdiv_exact(&num, &d, p), &u, p);
443 jac_reduce(u, v, f, p)
444}
445
446pub fn jac_scalar_mul(n: u128, d: &Mumford, f: &[BigInt], p: &BigInt) -> Mumford {
448 let mut result = jac_identity();
449 let mut base = d.clone();
450 let mut k = n;
451 while k > 0 {
452 if k & 1 == 1 {
453 result = cantor_add(&result, &base, f, p);
454 }
455 base = cantor_add(&base, &base, f, p);
456 k >>= 1;
457 }
458 result
459}
460
461pub fn jac_element_order(d: &Mumford, group_order: u128, f: &[BigInt], p: &BigInt) -> u128 {
464 let id = jac_identity();
465 let mut primes = Vec::new();
466 let (mut m, mut q) = (group_order, 2u128);
467 while q * q <= m {
468 if m % q == 0 {
469 primes.push(q);
470 while m % q == 0 {
471 m /= q;
472 }
473 }
474 q += 1;
475 }
476 if m > 1 {
477 primes.push(m);
478 }
479 let mut n = group_order;
480 for &pr in &primes {
481 while n % pr == 0 && jac_scalar_mul(n / pr, d, f, p) == id {
482 n /= pr;
483 }
484 }
485 n
486}
487
488fn legendre(a: &BigInt, p: &BigInt) -> i64 {
490 let ar = rp(a, p);
491 if ar.is_zero() {
492 return 0;
493 }
494 let e = p.sub(&ib(1)).div_rem(&ib(2)).map(|(q, _)| q).unwrap();
495 if modpow(&ar, &e, p) == ib(1) {
496 1
497 } else {
498 -1
499 }
500}
501
502pub fn count_curve_fp(f: &[BigInt], p: &BigInt, inf: i64) -> i64 {
504 let pu = p.to_i64().unwrap();
505 (0..pu).fold(inf, |n, x| n + 1 + legendre(&poly_eval(f, &ib(x), p), p))
506}
507
508fn count_curve_fp2(f: &[BigInt], p: &BigInt, inf: i64) -> i64 {
511 use crate::fp2::{fp2_add, fp2_const, fp2_is_zero, fp2_mul, fp2_pow, Fp2};
512 let pu = p.to_i64().unwrap();
513 let exp = (((pu as i128) * (pu as i128) - 1) / 2) as u64;
514 let coeffs: Vec<Fp2> = f.iter().map(|c| (rp(c, p), ib(0))).collect();
515 let mut n = inf;
516 for a in 0..pu {
517 for b in 0..pu {
518 let beta: Fp2 = (ib(a), ib(b));
519 let mut acc = fp2_const(0, p);
520 for c in coeffs.iter().rev() {
521 acc = fp2_add(&fp2_mul(&acc, &beta, p), c, p);
522 }
523 n += 1 + if fp2_is_zero(&acc) {
524 0
525 } else if fp2_pow(&acc, exp, p) == fp2_const(1, p) {
526 1
527 } else {
528 -1
529 };
530 }
531 }
532 n
533}
534
535pub fn genus2_jacobian_order(sextic: &[BigInt], p: &BigInt) -> i128 {
539 let pu = p.to_i64().unwrap() as i128;
540 let n1 = count_curve_fp(sextic, p, 2) as i128; let n2 = count_curve_fp2(sextic, p, 2) as i128;
542 let t1 = (pu + 1) - n1; let t2 = (pu * pu + 1) - n2; 1 + pu * pu - (1 + pu) * t1 + (t1 * t1 - t2) / 2
546}
547
548pub fn genus2_jacobian_order_general(f: &[BigInt], p: &BigInt) -> i128 {
553 let deg = pdeg(f);
554 let pu = p.to_i64().unwrap() as i128;
555 let inf_p = if deg % 2 == 1 {
556 1
557 } else if legendre(&f[deg as usize], p) == 1 {
558 2
559 } else {
560 0
561 };
562 let inf_p2 = if deg % 2 == 1 { 1 } else { 2 };
563 let n1 = count_curve_fp(f, p, inf_p) as i128;
564 let n2 = count_curve_fp2(f, p, inf_p2) as i128;
565 let t1 = (pu + 1) - n1;
566 let t2 = (pu * pu + 1) - n2;
567 1 + pu * pu - (1 + pu) * t1 + (t1 * t1 - t2) / 2
568}
569
570fn fp_sqrt(a: &BigInt, p: &BigInt) -> Option<BigInt> {
572 let a = rp(a, p);
573 if a.is_zero() {
574 return Some(ib(0));
575 }
576 let exp = p.add(&ib(1)).div_rem(&ib(4)).map(|(q, _)| q)?;
577 let r = modpow(&a, &exp, p);
578 (mm(&r, &r, p) == a).then_some(r)
579}
580
581fn quad_roots(q: &[BigInt], p: &BigInt) -> Option<[BigInt; 2]> {
583 if q.len() < 3 || q[2].is_zero() {
584 return None;
585 }
586 let (c0, c1, c2) = (&q[0], &q[1], &q[2]);
587 let disc = sm(&mm(c1, c1, p), &mm(&ib(4), &mm(c0, c2, p), p), p);
588 let sq = fp_sqrt(&disc, p)?;
589 let inv = mod_inverse(&mm(&ib(2), c2, p), p)?;
590 let neg_b = sm(&ib(0), c1, p);
591 Some([
592 mm(&sm(&neg_b, &sq, p), &inv, p),
593 mm(&am(&neg_b, &sq, p), &inv, p),
594 ])
595}
596
597fn codomain_roots(dual: &[Vec<BigInt>; 3], p: &BigInt) -> Option<[BigInt; 6]> {
602 let a = quad_roots(&dual[0], p)?;
603 let b = quad_roots(&dual[1], p)?;
604 let c = quad_roots(&dual[2], p)?;
605 Some([
606 a[0].clone(),
607 a[1].clone(),
608 b[0].clone(),
609 b[1].clone(),
610 c[0].clone(),
611 c[1].clone(),
612 ])
613}
614
615pub fn richelot_chain(roots: &[BigInt; 6], depth: usize, p: &BigInt) -> Option<Vec<usize>> {
621 for (i, g) in richelot_partitions(roots, p).into_iter().enumerate() {
622 let r = richelot(&g, p);
623 if r.is_split() {
624 return Some(vec![i]);
625 }
626 if depth > 0 {
627 if let Some(next) = codomain_roots(&r.dual, p) {
628 if let Some(mut path) = richelot_chain(&next, depth - 1, p) {
629 path.insert(0, i);
630 return Some(path);
631 }
632 }
633 }
634 }
635 None
636}
637
638#[derive(Clone, Debug, PartialEq, Eq)]
640pub enum GuidedWalk {
641 SplitAt(usize),
643 Ended([BigInt; 6]),
645 Stuck(usize),
648}
649
650pub fn guided_chain(roots: &[BigInt; 6], path: &[usize], p: &BigInt) -> GuidedWalk {
656 let mut cur = roots.clone();
657 for (step, &idx) in path.iter().enumerate() {
658 let parts = richelot_partitions(&cur, p);
659 if idx >= parts.len() {
660 return GuidedWalk::Stuck(step);
661 }
662 let r = richelot(&parts[idx], p);
663 if r.is_split() {
664 return GuidedWalk::SplitAt(step);
665 }
666 match codomain_roots(&r.dual, p) {
667 Some(next) => cur = next,
668 None => return GuidedWalk::Stuck(step),
669 }
670 }
671 GuidedWalk::Ended(cur)
672}
673
674#[cfg(test)]
675#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/hyperelliptic/tests.rs"]
676mod tests;