lambdaworks_math/circle/
point.rs

1use super::errors::CircleError;
2use crate::field::traits::IsField;
3use crate::field::{
4    element::FieldElement,
5    fields::mersenne31::{extensions::Degree4ExtensionField, field::Mersenne31Field},
6};
7use core::ops::{Add, AddAssign, Mul, MulAssign};
8
9/// Given a Field F, we implement here the Group which consists of all the points (x, y) such as
10/// x in F, y in F and x^2 + y^2 = 1, i.e. the Circle. The operation of the group will have
11/// additive notation and is as follows:
12/// (a, b) + (c, d) = (a * c - b * d, a * d + b * c)
13#[derive(Debug, Clone)]
14pub struct CirclePoint<F: IsField> {
15    pub x: FieldElement<F>,
16    pub y: FieldElement<F>,
17}
18
19impl<F: IsField + HasCircleParams<F>> CirclePoint<F> {
20    pub fn new(x: FieldElement<F>, y: FieldElement<F>) -> Result<Self, CircleError> {
21        if x.square() + y.square() == FieldElement::one() {
22            Ok(Self { x, y })
23        } else {
24            Err(CircleError::PointDoesntSatisfyCircleEquation)
25        }
26    }
27
28    /// Neutral element of the Circle group (with additive notation).
29    pub fn zero() -> Self {
30        Self::new(FieldElement::one(), FieldElement::zero()).unwrap()
31    }
32
33    /// Computes 2(x, y) = (2x^2 - 1, 2xy).
34    pub fn double(&self) -> Self {
35        Self::new(
36            self.x.square().double() - FieldElement::one(),
37            self.x.double() * self.y.clone(),
38        )
39        .unwrap()
40    }
41
42    /// Computes 2^n * (x, y).
43    pub fn repeated_double(self, n: u32) -> Self {
44        let mut res = self;
45        for _ in 0..n {
46            res = res.double();
47        }
48        res
49    }
50
51    /// Computes the inverse of the point.
52    /// We are using -(x, y) = (x, -y), i.e. the inverse of the group opertion is conjugation
53    /// because the norm of every point in the circle is one.
54    pub fn conjugate(self) -> Self {
55        Self {
56            x: self.x,
57            y: -self.y,
58        }
59    }
60
61    pub fn antipode(self) -> Self {
62        Self {
63            x: -self.x,
64            y: -self.y,
65        }
66    }
67
68    pub const GENERATOR: Self = Self {
69        x: F::CIRCLE_GENERATOR_X,
70        y: F::CIRCLE_GENERATOR_Y,
71    };
72
73    /// Returns the generator of the subgroup of order n = 2^log_2_size.
74    /// We are using that 2^k * g is a generator of the subgroup of order 2^{31 - k}.
75    pub fn get_generator_of_subgroup(log_2_size: u32) -> Self {
76        Self::GENERATOR.repeated_double(31 - log_2_size)
77    }
78
79    pub const ORDER: u128 = F::ORDER;
80}
81
82/// Parameters of the base field that we'll need to define its Circle.
83pub trait HasCircleParams<F: IsField> {
84    type FE;
85
86    /// Coordinate x of the generator of the circle group.
87    const CIRCLE_GENERATOR_X: FieldElement<F>;
88
89    /// Coordinate y of the generator of the circle group.
90    const CIRCLE_GENERATOR_Y: FieldElement<F>;
91
92    const ORDER: u128;
93}
94
95impl HasCircleParams<Mersenne31Field> for Mersenne31Field {
96    type FE = FieldElement<Mersenne31Field>;
97
98    const CIRCLE_GENERATOR_X: Self::FE = Self::FE::const_from_raw(2);
99
100    const CIRCLE_GENERATOR_Y: Self::FE = Self::FE::const_from_raw(1268011823);
101
102    /// ORDER = 2^31
103    const ORDER: u128 = 2147483648;
104}
105
106impl HasCircleParams<Degree4ExtensionField> for Degree4ExtensionField {
107    type FE = FieldElement<Degree4ExtensionField>;
108
109    // These parameters were taken from stwo's implementation:
110    // https://github.com/starkware-libs/stwo/blob/9cfd48af4e8ac5dd67643a92927c894066fa989c/crates/prover/src/core/circle.rs
111    const CIRCLE_GENERATOR_X: Self::FE =
112        Degree4ExtensionField::const_from_coefficients(1, 0, 478637715, 513582971);
113
114    const CIRCLE_GENERATOR_Y: Self::FE =
115        Degree4ExtensionField::const_from_coefficients(992285211, 649143431, 740191619, 1186584352);
116
117    /// ORDER = (2^31 - 1)^4 - 1
118    const ORDER: u128 = 21267647892944572736998860269687930880;
119}
120
121/// Equality between two cricle points.
122impl<F: IsField + HasCircleParams<F>> PartialEq for CirclePoint<F> {
123    fn eq(&self, other: &Self) -> bool {
124        self.x == other.x && self.y == other.y
125    }
126}
127
128/// Addition (i.e. group operation) between two points:
129/// (a, b) + (c, d) = (a * c - b * d, a * d + b * c)
130impl<F: IsField + HasCircleParams<F>> Add for &CirclePoint<F> {
131    type Output = CirclePoint<F>;
132    fn add(self, other: Self) -> Self::Output {
133        let x = &self.x * &other.x - &self.y * &other.y;
134        let y = &self.x * &other.y + &self.y * &other.x;
135        CirclePoint { x, y }
136    }
137}
138impl<F: IsField + HasCircleParams<F>> Add for CirclePoint<F> {
139    type Output = CirclePoint<F>;
140    fn add(self, rhs: CirclePoint<F>) -> Self::Output {
141        &self + &rhs
142    }
143}
144impl<F: IsField + HasCircleParams<F>> Add<CirclePoint<F>> for &CirclePoint<F> {
145    type Output = CirclePoint<F>;
146    fn add(self, rhs: CirclePoint<F>) -> Self::Output {
147        self + &rhs
148    }
149}
150impl<F: IsField + HasCircleParams<F>> Add<&CirclePoint<F>> for CirclePoint<F> {
151    type Output = CirclePoint<F>;
152    fn add(self, rhs: &CirclePoint<F>) -> Self::Output {
153        &self + rhs
154    }
155}
156impl<F: IsField + HasCircleParams<F>> AddAssign<&CirclePoint<F>> for CirclePoint<F> {
157    fn add_assign(&mut self, rhs: &CirclePoint<F>) {
158        *self = &*self + rhs;
159    }
160}
161impl<F: IsField + HasCircleParams<F>> AddAssign<CirclePoint<F>> for CirclePoint<F> {
162    fn add_assign(&mut self, rhs: CirclePoint<F>) {
163        *self += &rhs;
164    }
165}
166/// Multiplication between a point and a scalar (i.e. group operation repeatedly):
167/// (x, y) * n = (x ,y) + ... + (x, y) n-times.
168impl<F: IsField + HasCircleParams<F>> Mul<u128> for &CirclePoint<F> {
169    type Output = CirclePoint<F>;
170    fn mul(self, scalar: u128) -> Self::Output {
171        let mut scalar = scalar;
172        let mut res = CirclePoint::<F>::zero();
173        let mut cur = self.clone();
174        loop {
175            if scalar == 0 {
176                return res;
177            }
178            if scalar & 1 == 1 {
179                res += &cur;
180            }
181            cur = cur.double();
182            scalar >>= 1;
183        }
184    }
185}
186impl<F: IsField + HasCircleParams<F>> Mul<u128> for CirclePoint<F> {
187    type Output = CirclePoint<F>;
188    fn mul(self, scalar: u128) -> Self::Output {
189        &self * scalar
190    }
191}
192impl<F: IsField + HasCircleParams<F>> MulAssign<u128> for CirclePoint<F> {
193    fn mul_assign(&mut self, scalar: u128) {
194        let mut scalar = scalar;
195        let mut res = CirclePoint::<F>::zero();
196        loop {
197            if scalar == 0 {
198                *self = res.clone();
199            }
200            if scalar & 1 == 1 {
201                res += &*self;
202            }
203            *self = self.double();
204            scalar >>= 1;
205        }
206    }
207}
208
209#[cfg(test)]
210mod tests {
211    use super::*;
212    type F = Mersenne31Field;
213    type FE = FieldElement<F>;
214    type G = CirclePoint<F>;
215
216    type Fp4 = Degree4ExtensionField;
217    type Fp4E = FieldElement<Fp4>;
218    type G4 = CirclePoint<Fp4>;
219
220    #[test]
221    fn create_new_valid_g_point() {
222        let valid_point = G::new(FE::one(), FE::zero()).unwrap();
223        let expected = G {
224            x: FE::one(),
225            y: FE::zero(),
226        };
227        assert_eq!(valid_point, expected)
228    }
229
230    #[test]
231    fn create_new_valid_g4_point() {
232        let valid_point = G4::new(Fp4E::one(), Fp4E::zero()).unwrap();
233        let expected = G4 {
234            x: Fp4E::one(),
235            y: Fp4E::zero(),
236        };
237        assert_eq!(valid_point, expected)
238    }
239
240    #[test]
241    fn create_new_invalid_circle_point() {
242        let invalid_point = G::new(FE::one(), FE::one());
243        assert!(invalid_point.is_err())
244    }
245
246    #[test]
247    fn create_new_invalid_g4_circle_point() {
248        let invalid_point = G4::new(Fp4E::one(), Fp4E::one());
249        assert!(invalid_point.is_err())
250    }
251
252    #[test]
253    fn zero_plus_zero_is_zero() {
254        let a = G::zero();
255        let b = G::zero();
256        assert_eq!(&a + &b, G::zero())
257    }
258
259    #[test]
260    fn generator_plus_zero_is_generator() {
261        let g = G::GENERATOR;
262        let zero = G::zero();
263        assert_eq!(&g + &zero, g)
264    }
265
266    #[test]
267    fn double_equals_mul_two() {
268        let g = G::GENERATOR;
269        assert_eq!(g.clone().double(), g * 2)
270    }
271
272    #[test]
273    fn mul_eight_equals_double_three_times() {
274        let g = G::GENERATOR;
275        assert_eq!(g.clone().repeated_double(3), g * 8)
276    }
277
278    #[test]
279    fn generator_g1_has_order_two_pow_31() {
280        let g = G::GENERATOR;
281        let n = 31;
282        assert_eq!(g.repeated_double(n), G::zero())
283    }
284
285    #[test]
286    fn generator_g4_has_the_order_of_the_group() {
287        let g = G4::GENERATOR;
288        assert_eq!(g * G4::ORDER, G4::zero())
289    }
290
291    #[test]
292    fn conjugation_is_inverse_operation() {
293        let g = G::GENERATOR;
294        assert_eq!(&g.clone() + &g.conjugate(), G::zero())
295    }
296
297    #[test]
298    fn subgroup_generator_has_correct_order() {
299        let generator_n = G::get_generator_of_subgroup(7);
300        assert_eq!(generator_n.repeated_double(7), G::zero());
301    }
302}
lambdaworks_math/circle/point.rs

lambdaworks_math/circle/
point.rs
