lambdaworks_math/elliptic_curve/montgomery/
point.rs

1use crate::{
2    cyclic_group::IsGroup,
3    elliptic_curve::{
4        point::ProjectivePoint,
5        traits::{EllipticCurveError, FromAffine, IsEllipticCurve},
6    },
7    field::element::FieldElement,
8};
9
10use super::traits::IsMontgomery;
11
12#[derive(Clone, Debug)]
13pub struct MontgomeryProjectivePoint<E: IsEllipticCurve>(ProjectivePoint<E>);
14
15impl<E: IsEllipticCurve + IsMontgomery> MontgomeryProjectivePoint<E> {
16    /// Creates an elliptic curve point giving the projective [x: y: z] coordinates.
17    pub fn new(value: [FieldElement<E::BaseField>; 3]) -> Result<Self, EllipticCurveError> {
18        let (x, y, z) = (&value[0], &value[1], &value[2]);
19
20        if z != &FieldElement::<E::BaseField>::zero()
21            && E::defining_equation_projective(x, y, z) == FieldElement::<E::BaseField>::zero()
22        {
23            Ok(Self(ProjectivePoint::new(value)))
24        // The point at infinity is (0, 1, 0)
25        // We convert every (0, _, 0) into the infinity.
26        } else if x == &FieldElement::<E::BaseField>::zero()
27            && z == &FieldElement::<E::BaseField>::zero()
28        {
29            Ok(Self(ProjectivePoint::new([
30                FieldElement::<E::BaseField>::zero(),
31                FieldElement::<E::BaseField>::one(),
32                FieldElement::<E::BaseField>::zero(),
33            ])))
34        } else {
35            Err(EllipticCurveError::InvalidPoint)
36        }
37    }
38
39    /// Returns the `x` coordinate of the point.
40    pub fn x(&self) -> &FieldElement<E::BaseField> {
41        self.0.x()
42    }
43
44    /// Returns the `y` coordinate of the point.
45    pub fn y(&self) -> &FieldElement<E::BaseField> {
46        self.0.y()
47    }
48
49    /// Returns the `z` coordinate of the point.
50    pub fn z(&self) -> &FieldElement<E::BaseField> {
51        self.0.z()
52    }
53
54    /// Returns a tuple [x, y, z] with the coordinates of the point.
55    pub fn coordinates(&self) -> &[FieldElement<E::BaseField>; 3] {
56        self.0.coordinates()
57    }
58
59    /// Creates the same point in affine coordinates. That is,
60    /// returns [x / z: y / z: 1] where `self` is [x: y: z].
61    /// Panics if `self` is the point at infinity.
62    pub fn to_affine(&self) -> Self {
63        Self(self.0.to_affine())
64    }
65}
66
67impl<E: IsEllipticCurve> PartialEq for MontgomeryProjectivePoint<E> {
68    fn eq(&self, other: &Self) -> bool {
69        self.0 == other.0
70    }
71}
72
73impl<E: IsMontgomery> FromAffine<E::BaseField> for MontgomeryProjectivePoint<E> {
74    fn from_affine(
75        x: FieldElement<E::BaseField>,
76        y: FieldElement<E::BaseField>,
77    ) -> Result<Self, EllipticCurveError> {
78        let coordinates = [x, y, FieldElement::one()];
79        MontgomeryProjectivePoint::new(coordinates)
80    }
81}
82
83impl<E: IsEllipticCurve> Eq for MontgomeryProjectivePoint<E> {}
84
85impl<E: IsMontgomery> IsGroup for MontgomeryProjectivePoint<E> {
86    /// The point at infinity.
87    ///    
88    /// # Safety
89    ///
90    /// - The point `(0, 1, 0)` is a well-defined **neutral element** for Montgomery curves.
91    /// - `unwrap_unchecked()` is used because this point is **always valid**.
92    fn neutral_element() -> Self {
93        // SAFETY:
94        // - `(0, 1, 0)` is **mathematically valid** as the neutral element.
95        // - `unwrap_unchecked()` is safe because this is **a known valid point**.
96        let point = Self::new([
97            FieldElement::zero(),
98            FieldElement::one(),
99            FieldElement::zero(),
100        ]);
101        debug_assert!(point.is_ok());
102        point.unwrap()
103    }
104
105    fn is_neutral_element(&self) -> bool {
106        let pz = self.z();
107        pz == &FieldElement::zero()
108    }
109
110    /// Computes the addition of `self` and `other`.
111    ///
112    /// This implementation follows the addition law for Montgomery curves as described in:
113    /// **Moonmath Manual, Definition 5.2.2.1, Page 94**.
114    ///
115    /// # Safety
116    ///
117    /// - This function assumes that both `self` and `other` are **valid** points on the curve.
118    /// - The resulting point is **guaranteed** to be valid due to the **Montgomery curve addition formula**.
119    /// - `unwrap()` is used because the formula ensures the result remains a valid curve point.
120    fn operate_with(&self, other: &Self) -> Self {
121        // One of them is the neutral element.
122        if self.is_neutral_element() {
123            other.clone()
124        } else if other.is_neutral_element() {
125            self.clone()
126        } else {
127            let [x1, y1, _] = self.to_affine().coordinates().clone();
128            let [x2, y2, _] = other.to_affine().coordinates().clone();
129            // In this case P == -Q
130            if x2 == x1 && &y2 + &y1 == FieldElement::zero() {
131                Self::neutral_element()
132            // The points are the same P == Q
133            } else if self == other {
134                // P = Q = (x, y)
135                // y cant be zero here because if y = 0 then
136                // P = Q = (x, 0) and P = -Q, which is the
137                // previous case.
138                let one = FieldElement::from(1);
139                let (a, b) = (E::a(), E::b());
140
141                let x1a = &a * &x1;
142                let x1_square = &x1 * &x1;
143                let num = &x1_square + &x1_square + x1_square + &x1a + x1a + &one;
144                let den = (&b + &b) * &y1;
145
146                // We are using that den != 0 because b and y1 aren't zero.
147                // b != 0 because the cofficient b of a montgomery elliptic curve has to be different from zero.
148                // y1 != 0 because if not, it woould be the case from above: x2 = x1 and y2 + y1 = 0.
149                let div = unsafe { (num / den).unwrap_unchecked() };
150
151                let new_x = &div * &div * &b - (&x1 + x2) - a;
152                let new_y = div * (x1 - &new_x) - y1;
153
154                // SAFETY:
155                // - The Montgomery addition formula guarantees a **valid** curve point.
156                // - `unwrap()` is safe because the input points are **valid**.
157                let point = Self::new([new_x, new_y, one]);
158                point.unwrap()
159            // In the rest of the cases we have x1 != x2
160            } else {
161                let num = &y2 - &y1;
162                let den = &x2 - &x1;
163
164                let div = unsafe { (num / den).unwrap_unchecked() };
165
166                let new_x = &div * &div * E::b() - (&x1 + &x2) - E::a();
167                let new_y = div * (x1 - &new_x) - y1;
168
169                // SAFETY:
170                // - The result of the Montgomery addition formula is **guaranteed** to be a valid point.
171                // - `unwrap()` is safe because we **control** the inputs.
172                let point = Self::new([new_x, new_y, FieldElement::one()]);
173                point.unwrap()
174            }
175        }
176    }
177
178    /// Returns the additive inverse of the projective point `p`
179    ///
180    /// # Safety
181    ///
182    /// - The negation formula preserves the curve equation.
183    /// - `unwrap()` is safe because negation **does not** create invalid points.
184    fn neg(&self) -> Self {
185        let [px, py, pz] = self.coordinates();
186        // SAFETY:
187        // - Negating `y` maintains the curve structure.
188        // - `unwrap()` is safe because negation **is always valid**.
189        let point = Self::new([px.clone(), -py, pz.clone()]);
190        debug_assert!(point.is_ok());
191        point.unwrap()
192    }
193}
194
195#[cfg(test)]
196mod tests {
197    use crate::{
198        cyclic_group::IsGroup,
199        elliptic_curve::{
200            montgomery::{
201                curves::tiny_jub_jub::TinyJubJubMontgomery, point::MontgomeryProjectivePoint,
202            },
203            traits::{EllipticCurveError, IsEllipticCurve},
204        },
205        field::element::FieldElement,
206    };
207
208    fn create_point(x: u64, y: u64) -> MontgomeryProjectivePoint<TinyJubJubMontgomery> {
209        TinyJubJubMontgomery::create_point_from_affine(FieldElement::from(x), FieldElement::from(y))
210            .unwrap()
211    }
212
213    #[test]
214    fn create_valid_point_works() {
215        let p = TinyJubJubMontgomery::create_point_from_affine(
216            FieldElement::from(9),
217            FieldElement::from(2),
218        )
219        .unwrap();
220        assert_eq!(p.x(), &FieldElement::from(9));
221        assert_eq!(p.y(), &FieldElement::from(2));
222        assert_eq!(p.z(), &FieldElement::from(1));
223    }
224
225    #[test]
226    fn create_invalid_point_returns_invalid_point_error() {
227        let result = TinyJubJubMontgomery::create_point_from_affine(
228            FieldElement::from(5),
229            FieldElement::from(4),
230        );
231        assert_eq!(result.unwrap_err(), EllipticCurveError::InvalidPoint);
232    }
233
234    #[test]
235    fn operate_with_works_for_points_in_tiny_jub_jub() {
236        let p = MontgomeryProjectivePoint::<TinyJubJubMontgomery>::new([
237            FieldElement::from(9),
238            FieldElement::from(2),
239            FieldElement::from(1),
240        ])
241        .unwrap();
242        let q = MontgomeryProjectivePoint::<TinyJubJubMontgomery>::new([
243            FieldElement::from(7),
244            FieldElement::from(12),
245            FieldElement::from(1),
246        ])
247        .unwrap();
248        let expected = MontgomeryProjectivePoint::<TinyJubJubMontgomery>::new([
249            FieldElement::from(10),
250            FieldElement::from(3),
251            FieldElement::from(1),
252        ])
253        .unwrap();
254        assert_eq!(p.operate_with(&q), expected);
255    }
256
257    #[test]
258    fn test_negation_in_montgomery() {
259        let a = create_point(9, 2);
260        let b = create_point(9, 13 - 2);
261
262        assert_eq!(a.neg(), b);
263        assert!(a.operate_with(&b).is_neutral_element());
264    }
265
266    #[test]
267    fn operate_with_works_and_cycles_in_tiny_jub_jub() {
268        let g = create_point(9, 2);
269        assert_eq!(
270            g.operate_with_self(0_u16),
271            MontgomeryProjectivePoint::neutral_element()
272        );
273        assert_eq!(g.operate_with_self(1_u16), create_point(9, 2));
274        assert_eq!(g.operate_with_self(2_u16), create_point(7, 12));
275        assert_eq!(g.operate_with_self(3_u16), create_point(10, 3));
276        assert_eq!(g.operate_with_self(4_u16), create_point(8, 12));
277        assert_eq!(g.operate_with_self(5_u16), create_point(1, 9));
278        assert_eq!(g.operate_with_self(6_u16), create_point(5, 1));
279        assert_eq!(g.operate_with_self(7_u16), create_point(4, 9));
280        assert_eq!(g.operate_with_self(8_u16), create_point(2, 9));
281        assert_eq!(g.operate_with_self(9_u16), create_point(3, 5));
282        assert_eq!(g.operate_with_self(10_u16), create_point(0, 0));
283        assert_eq!(g.operate_with_self(11_u16), create_point(3, 8));
284        assert_eq!(g.operate_with_self(12_u16), create_point(2, 4));
285        assert_eq!(g.operate_with_self(13_u16), create_point(4, 4));
286        assert_eq!(g.operate_with_self(14_u16), create_point(5, 12));
287        assert_eq!(g.operate_with_self(15_u16), create_point(1, 4));
288        assert_eq!(g.operate_with_self(16_u16), create_point(8, 1));
289        assert_eq!(g.operate_with_self(17_u16), create_point(10, 10));
290        assert_eq!(g.operate_with_self(18_u16), create_point(7, 1));
291        assert_eq!(g.operate_with_self(19_u16), create_point(9, 11));
292        assert_eq!(
293            g.operate_with_self(20_u16),
294            MontgomeryProjectivePoint::neutral_element()
295        );
296    }
297}
lambdaworks_math/elliptic_curve/montgomery/point.rs

lambdaworks_math/elliptic_curve/montgomery/
point.rs
