ecfft/
find_curve.rs

1use crate::ec::GoodCurve;
2use crate::ec::Point;
3use crate::utils::is_odd;
4use ark_ff::Field;
5use rand::Rng;
6
7/// Returns the x-coordinate of Q if P is a half point of Q. Otherwise returns
8/// None. y^2 = x(x^2 + a*x + B), B = b^2. `F` must be an odd order field.
9/// <https://www.ams.org/journals/mcom/2005-74-249/S0025-5718-04-01640-0/S0025-5718-04-01640-0.pdf>
10/// "If Q = 2P, we say that Q has a half point P".
11fn double_point_x<F: Field>(px: F, a: F, bb: F) -> Option<F> {
12    assert!(is_odd::<F>());
13    let pxpx = px.square();
14    let pypy = px * (pxpx + a * px + bb);
15    if pypy.is_zero() {
16        return None;
17    }
18    Some((pxpx - bb).square() / pypy.double().double())
19}
20
21/// Returns the x-coordinate of P if P is a half point of Q. Otherwise returns
22/// None. y^2 = x(x^2 + a*x + B), B = b^2. `F` must be an odd order field.
23/// <https://www.ams.org/journals/mcom/2005-74-249/S0025-5718-04-01640-0/S0025-5718-04-01640-0.pdf>
24/// "If Q = 2P, we say that Q has a half point P".
25fn half_point_x<F: Field>(qx: F, a: F, bb: F) -> Option<F> {
26    assert!(is_odd::<F>());
27    let roots = fi_roots(1, qx, a, bb).or_else(|| fi_roots(2, qx, a, bb))?;
28    roots
29        .into_iter()
30        .find(|&x| (x * (x.square() + a * x + bb)).sqrt().is_some())
31}
32
33/// Finds the roots of a quadratic equation a*x^2 + b*x + c
34/// F must be an odd order field
35fn roots<F: Field>(a: F, b: F, c: F) -> Option<[F; 2]> {
36    assert!(is_odd::<F>());
37    let discriminant = b.square() - (a * c).double().double();
38    let discriminant_sqrt = discriminant.sqrt()?;
39    let two_inv = a.double().inverse()?;
40    Some([
41        (-b + discriminant_sqrt) * two_inv,
42        (-b - discriminant_sqrt) * two_inv,
43    ])
44}
45
46/// Finds the roots of f_{1, ξ} or f_{2, ξ} if they exists
47/// Let Q be a point such that x(Q) = ξ
48/// F must be an odd order field
49fn fi_roots<F: Field>(i: usize, qx: F, a: F, bb: F) -> Option<[F; 2]> {
50    assert!(i == 1 || i == 2);
51    let delta = qx.square() + a * qx + bb;
52    let delta_sqrt = delta.sqrt()?;
53    let one = F::one();
54    let x_coeff = -(qx.double() + (-one).pow([i as u64]) * delta_sqrt.double());
55    roots(one, x_coeff, bb)
56}
57
58/// Determines the 2-sylow subgroup of curve y^2 = x(x^2 + a*x + B), B = b^2
59/// Algorithm from: https://www.ams.org/journals/mcom/2005-74-249/S0025-5718-04-01640-0/S0025-5718-04-01640-0.pdf
60/// Output is of the form (n, r, x1, x2) with n, r such that Sylow_2(E(Fq)) is
61/// isomorphic to Z/2^nZ × Z/2^rZ and x-coordinates x1, x2 of points of order
62/// 2^n and 2^r, respectively, generating this Sylow subgroup. Note that None
63/// refers to infinity. Panics if `F` is not a field with odd order.
64// TODO: finish this implementation
65fn _find_two_sylow_subgroup<F: Field>(a: F, bb: F) -> (u32, u32, Option<F>, Option<F>) {
66    assert!(is_odd::<F>());
67    let discriminant = a.square() - bb.double().double();
68    assert!(!discriminant.is_zero());
69    let one = F::one();
70    let zero = F::zero();
71
72    if discriminant.sqrt().is_some() {
73        // == non-cyclic case ==
74
75        // the roots (r0, r1, r2) of our curve equation give us our 2-torsion points
76        // x^3 + a*x^2 + B = x(x^2 + a*x + B), B = b^2
77        let Some([r1, r2]) = roots(F::one(), a, bb) else { unreachable!() };
78        let r0 = zero;
79
80        // check if rational points of order 4 exist (lemma 3)
81        let p4_cond1 = bb.sqrt().and_then(|b| (a - b.double()).sqrt()).is_some();
82        let p4_cond2 = r1.sqrt().and_then(|_| (r1.double() + a).sqrt()).is_some();
83        let p4_cond3 = r2.sqrt().and_then(|_| (r2.double() + a).sqrt()).is_some();
84
85        if !p4_cond1 && !p4_cond2 && !p4_cond3 {
86            // there is no point with order 4
87            return (1, 1, Some(zero), Some(r1));
88        }
89
90        // find an x-coordinate of points of order 4 (lemma 3)
91        // safe to unwrap since we've already checked if points of order 4 exist
92        let p4_x0 = roots(one, r0, -bb).map(|[x, _]| x).unwrap();
93        let p4_x1 = roots(one, -r1.double(), bb).map(|[x, _]| x).unwrap();
94        let p4_x2 = roots(one, -r2.double(), bb).map(|[x, _]| x).unwrap();
95
96        let has_half_point = |x: F| -> bool {
97            // halving conditions (Proposition 2)
98            if x.sqrt().is_none() {
99                return false;
100            }
101            let delta = x.square() + a * x + bb;
102            let delta_sqrt = match delta.sqrt() {
103                Some(sqrt) => sqrt,
104                None => return false,
105            };
106            (x.double() + a + delta_sqrt.double()).sqrt().is_some()
107        };
108
109        let mut k = 2;
110        let mut h = 1;
111        let mut acc0 = p4_x0;
112        let mut acc1 = p4_x1;
113        let mut acc2 = p4_x2;
114        loop {
115            let acc0_has_half_point = has_half_point(acc0);
116            let acc1_has_half_point = has_half_point(acc1);
117            let acc2_has_half_point = has_half_point(acc2);
118
119            if !acc0_has_half_point && !acc1_has_half_point && !acc2_has_half_point {
120                // no accumulators have a half point
121                return (h, h, Some(acc0), Some(acc1));
122            }
123
124            if acc0_has_half_point && acc1_has_half_point && acc2_has_half_point {
125                // all accumulators have a half point
126                acc0 = half_point_x(acc0, a, bb).unwrap();
127                acc1 = half_point_x(acc1, a, bb).unwrap();
128                acc2 = half_point_x(acc2, a, bb).unwrap();
129                k += 1;
130                h = k;
131                continue;
132            }
133
134            if h == 1 {
135                // `x2` is the x-coord of a point of order 2 that does not have a half point
136                // `acc` is TODO
137                let _x2 = match (
138                    acc0_has_half_point,
139                    acc1_has_half_point,
140                    acc2_has_half_point,
141                ) {
142                    (false, _, _) => r0,
143                    (_, false, _) => r1,
144                    (_, _, false) => r2,
145                    _ => unreachable!(),
146                };
147
148                todo!()
149            }
150
151            todo!()
152        }
153
154        // TODO
155    } else if let Some(b) = bb.sqrt() {
156        // == cyclic case ==
157        let p4_x = match ((a + b.double()).sqrt(), (a - b.double()).sqrt()) {
158            (Some(_), _) => b,
159            (_, Some(_)) => -b,
160            _ => unreachable!(),
161        };
162
163        if double_point_x(p4_x, a, bb).is_none() {
164            return (1, 0, Some(zero), None);
165        }
166
167        let mut k = 2;
168        let mut acc = p4_x;
169        while let Some(x) = half_point_x(acc, a, bb) {
170            k += 1;
171            acc = x;
172        }
173
174        (k, 0, Some(acc), None)
175    } else {
176        (0, 0, None, None)
177    }
178}
179
180/// Determines the 2-sylow subgroup of curve y^2 = x(x^2 + a*x + B), B = b^2
181/// Output is of the form (n, x) with n such that Sylow_2(E(Fq)) is
182/// isomorphic to Z/2^nZ and x-coordinates x, the x-coordinate of the point
183/// of order 2^n generating this Sylow subgroup. Note that None refers to
184/// infinity. Panics if `F` is not a field with odd order.
185///
186/// Algorithm from: https://www.ams.org/journals/mcom/2005-74-249/S0025-5718-04-01640-0/S0025-5718-04-01640-0.pdf
187/// note that the algorithm in the paper finds the 2-slyow subgoup of non-cyclic
188/// curves as well. This has been ommited since we are only interested in cyclic
189/// subgroups for ECFFT.
190fn cyclic_two_sylow_subgroup<F: Field>(a: F, bb: F) -> (u32, Option<F>) {
191    assert!(is_odd::<F>());
192    let discriminant = a.square() - bb.double().double();
193    assert!(!discriminant.is_zero());
194
195    if let (Some(b), None) = (bb.sqrt(), discriminant.sqrt()) {
196        // 2-sylow subgroup is cyclic
197        let p4_x = match ((a + b.double()).sqrt(), (a - b.double()).sqrt()) {
198            (Some(_), _) => b,
199            (_, Some(_)) => -b,
200            _ => unreachable!(),
201        };
202
203        if double_point_x(p4_x, a, bb).is_none() {
204            return (1, Some(F::zero()));
205        }
206
207        let mut k = 2;
208        let mut acc = p4_x;
209        while let Some(x) = half_point_x(acc, a, bb) {
210            k += 1;
211            acc = x;
212        }
213
214        (k, Some(acc))
215    } else {
216        (0, None)
217    }
218}
219
220/// Returns a point with order 2^n on a Good Curve such that n >= k.
221/// Output is of the form (n, subgroup_generator_point)
222/// Based on `find_curve` algorithm from "ECFFT part II":
223/// <https://www.math.toronto.edu/swastik/ECFFT2.pdf>
224pub fn find_curve<F: Field>(mut rng: impl Rng, k: u32) -> (u32, Point<GoodCurve<F>>) {
225    let k = k.max(2);
226    if is_odd::<F>() {
227        loop {
228            // curve: y^2 = x*(x^2 + a*x + b)
229            let a = F::rand(&mut rng);
230            let bb = F::rand(&mut rng);
231            // TODO: may be faster this way but would be nice to
232            // finish the generic two sylow algorithm.
233            let (n, x) = cyclic_two_sylow_subgroup(a, bb);
234            if n >= k {
235                let x = x.unwrap();
236                let yy = x * (x.square() + a * x + bb);
237                let y = yy.sqrt().unwrap();
238                let good_curve = GoodCurve::new_odd(a, bb);
239                let p = Point::new(x, y, good_curve);
240                return (n, p);
241            }
242        }
243    } else {
244        todo!()
245    }
246}
ecfft/find_curve.rs

ecfft/
find_curve.rs
