nautilus_lighter/signing/field/
quintic.rs

1// -------------------------------------------------------------------------------------------------
2//  Copyright (C) 2015-2026 Nautech Systems Pty Ltd. All rights reserved.
3//  https://nautechsystems.io
4//
5//  Licensed under the GNU Lesser General Public License Version 3.0 (the "License");
6//  You may not use this file except in compliance with the License.
7//  You may obtain a copy of the License at https://www.gnu.org/licenses/lgpl-3.0.en.html
8//
9//  Unless required by applicable law or agreed to in writing, software
10//  distributed under the License is distributed on an "AS IS" BASIS,
11//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12//  See the License for the specific language governing permissions and
13//  limitations under the License.
14// -------------------------------------------------------------------------------------------------
15
16//! Quintic extension `Fp5 = GF(p^5)` of the Goldilocks field.
17//!
18//! Elements are represented as `(c0, c1, c2, c3, c4)` over [`Fp`], encoding the
19//! polynomial `c0 + c1*z + c2*z^2 + c3*z^3 + c4*z^4` modulo the irreducible
20//! `z^5 - 3` (so `z^5 ≡ 3` in `Fp5`). Multiplication folds the schoolbook
21//! cross-products with `W = 3` for the wraparound terms and applies Montgomery
22//! reduction once per output coefficient. Inversion uses the Itoh-Tsujii trick
23//! over the Frobenius `phi(x) = x^p`, reducing the work to three Frobenius
24//! applications, two `Fp5` multiplications, and one `Fp` inversion.
25//!
26//! Arithmetic, inversion, and the [`Fp5::legendre`] descent inherit `Fp`'s
27//! constant-time guarantees. [`Fp5::sqrt`] / [`Fp5::canonical_sqrt`] inherit
28//! the variable-time behaviour of [`Fp::sqrt`] and are intended for the
29//! public-input curve decode path; do not feed them secret operands.
30
31use core::ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign};
32
33use super::goldilocks::Fp;
34
35/// Wraparound constant: `z^5 ≡ W (mod z^5 - W)` with `W = 3`.
36const W: u64 = 3;
37
38/// `d`-th root of unity used by the Frobenius operator, with `d = 5`.
39///
40/// For the irreducible `z^5 - W` and `p ≡ 1 (mod 5)`, the action `phi(z) = z^p`
41/// reduces to `W^((p-1)/5) * z`, so this constant is `W^((p-1)/5) mod p`
42/// (i.e. `3^((p-1)/5)` here, with `W = 3`). Precomputed as a Goldilocks element.
43const DTH_ROOT: u64 = 1_041_288_259_238_279_555;
44
45/// An element of `Fp5 = GF(p^5)`.
46#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
47pub struct Fp5(pub [Fp; 5]);
48
49impl Fp5 {
50    /// Additive identity.
51    pub const ZERO: Self = Self([Fp::ZERO; 5]);
52
53    /// Multiplicative identity.
54    pub const ONE: Self = Self([Fp::ONE, Fp::ZERO, Fp::ZERO, Fp::ZERO, Fp::ZERO]);
55
56    /// Build an element from five `u64` coefficients (low-to-high degree), each reduced mod `p`.
57    #[inline]
58    pub const fn from_u64s_reduce(c: [u64; 5]) -> Self {
59        Self([
60            Fp::from_u64_reduce(c[0]),
61            Fp::from_u64_reduce(c[1]),
62            Fp::from_u64_reduce(c[2]),
63            Fp::from_u64_reduce(c[3]),
64            Fp::from_u64_reduce(c[4]),
65        ])
66    }
67
68    /// Build an element from five canonical `u64` coefficients; returns `None`
69    /// if any coefficient is `>= p`.
70    pub fn from_u64s_canonical(c: [u64; 5]) -> Option<Self> {
71        Some(Self([
72            Fp::from_u64_canonical(c[0])?,
73            Fp::from_u64_canonical(c[1])?,
74            Fp::from_u64_canonical(c[2])?,
75            Fp::from_u64_canonical(c[3])?,
76            Fp::from_u64_canonical(c[4])?,
77        ]))
78    }
79
80    /// Decode an element from 40 little-endian bytes (5 x 8-byte canonical limbs).
81    ///
82    /// Returns `None` if any limb is non-canonical (`>= p`).
83    pub fn try_from_le_bytes(bytes: [u8; 40]) -> Option<Self> {
84        let mut limbs = [0u64; 5];
85        for (i, limb) in limbs.iter_mut().enumerate() {
86            let mut chunk = [0u8; 8];
87            chunk.copy_from_slice(&bytes[i * 8..(i + 1) * 8]);
88            *limb = u64::from_le_bytes(chunk);
89        }
90        Self::from_u64s_canonical(limbs)
91    }
92
93    /// Canonical 40-byte little-endian encoding (5 x 8-byte limbs, low-to-high degree).
94    pub fn to_le_bytes(self) -> [u8; 40] {
95        let mut out = [0u8; 40];
96        for i in 0..5 {
97            out[i * 8..(i + 1) * 8].copy_from_slice(&self.0[i].to_le_bytes());
98        }
99        out
100    }
101
102    /// Test whether the element is zero.
103    #[inline]
104    pub fn is_zero(self) -> bool {
105        self.0[0].is_zero()
106            && self.0[1].is_zero()
107            && self.0[2].is_zero()
108            && self.0[3].is_zero()
109            && self.0[4].is_zero()
110    }
111
112    /// Constant-time equality: returns `0xFFFF_FFFF_FFFF_FFFF` on equality, `0` otherwise.
113    #[inline]
114    pub fn ct_eq(self, rhs: Self) -> u64 {
115        let z = (self.0[0].0 ^ rhs.0[0].0)
116            | (self.0[1].0 ^ rhs.0[1].0)
117            | (self.0[2].0 ^ rhs.0[2].0)
118            | (self.0[3].0 ^ rhs.0[3].0)
119            | (self.0[4].0 ^ rhs.0[4].0);
120        ((z | z.wrapping_neg()) >> 63).wrapping_sub(1)
121    }
122
123    /// Branch-free select: returns `a` when `mask == 0` and `b` when
124    /// `mask == u64::MAX`. Composed coefficient-wise from [`Fp::ct_select`];
125    /// the secret-scalar curve primitives only ever pass full-bit masks.
126    #[inline]
127    #[must_use]
128    pub fn ct_select(mask: u64, a: Self, b: Self) -> Self {
129        Self([
130            Fp::ct_select(mask, a.0[0], b.0[0]),
131            Fp::ct_select(mask, a.0[1], b.0[1]),
132            Fp::ct_select(mask, a.0[2], b.0[2]),
133            Fp::ct_select(mask, a.0[3], b.0[3]),
134            Fp::ct_select(mask, a.0[4], b.0[4]),
135        ])
136    }
137
138    #[inline]
139    fn add_inner(self, rhs: Self) -> Self {
140        Self([
141            self.0[0] + rhs.0[0],
142            self.0[1] + rhs.0[1],
143            self.0[2] + rhs.0[2],
144            self.0[3] + rhs.0[3],
145            self.0[4] + rhs.0[4],
146        ])
147    }
148
149    #[inline]
150    fn sub_inner(self, rhs: Self) -> Self {
151        Self([
152            self.0[0] - rhs.0[0],
153            self.0[1] - rhs.0[1],
154            self.0[2] - rhs.0[2],
155            self.0[3] - rhs.0[3],
156            self.0[4] - rhs.0[4],
157        ])
158    }
159
160    #[inline]
161    fn neg_inner(self) -> Self {
162        Self([-self.0[0], -self.0[1], -self.0[2], -self.0[3], -self.0[4]])
163    }
164
165    #[inline]
166    fn scalar_mul(self, scalar: Fp) -> Self {
167        Self([
168            self.0[0] * scalar,
169            self.0[1] * scalar,
170            self.0[2] * scalar,
171            self.0[3] * scalar,
172            self.0[4] * scalar,
173        ])
174    }
175
176    #[inline]
177    fn mul_inner(self, rhs: Self) -> Self {
178        let w = Fp::from_u64_reduce(W);
179        let a = &self.0;
180        let b = &rhs.0;
181
182        // Schoolbook cross-product with `z^5 = W = 3`.
183        let c0 = a[0] * b[0] + w * (a[1] * b[4] + a[2] * b[3] + a[3] * b[2] + a[4] * b[1]);
184        let c1 = a[0] * b[1] + a[1] * b[0] + w * (a[2] * b[4] + a[3] * b[3] + a[4] * b[2]);
185        let c2 = a[0] * b[2] + a[1] * b[1] + a[2] * b[0] + w * (a[3] * b[4] + a[4] * b[3]);
186        let c3 = a[0] * b[3] + a[1] * b[2] + a[2] * b[1] + a[3] * b[0] + w * (a[4] * b[4]);
187        let c4 = a[0] * b[4] + a[1] * b[3] + a[2] * b[2] + a[3] * b[1] + a[4] * b[0];
188
189        Self([c0, c1, c2, c3, c4])
190    }
191
192    /// Squaring in `Fp5`.
193    #[inline]
194    #[must_use]
195    pub fn square(self) -> Self {
196        self.mul_inner(self)
197    }
198
199    /// Repeated squaring: returns `self^(2^n)`.
200    #[inline]
201    #[must_use]
202    pub fn msquare(self, n: u32) -> Self {
203        let mut x = self;
204        for _ in 0..n {
205            x = x.square();
206        }
207        x
208    }
209
210    /// Frobenius operator: `phi(x) = x^p`.
211    ///
212    /// Acts on `(c0, c1, c2, c3, c4)` as multiplication of each higher-degree
213    /// coefficient by a precomputed power of the `d`-th root of unity in `Fp`.
214    #[inline]
215    fn frobenius(self) -> Self {
216        // Coefficients = `DTH_ROOT^i` for i=0..4 (i=0 fixed at 1).
217        // DTH_ROOT^2 = 15820824984080659046, DTH_ROOT^3 = 211587555138949697,
218        // DTH_ROOT^4 = 1373043270956696022 (matches Pornin and elliottech).
219        Self([
220            self.0[0],
221            self.0[1] * Fp::from_u64_reduce(DTH_ROOT),
222            self.0[2] * Fp::from_u64_reduce(15_820_824_984_080_659_046),
223            self.0[3] * Fp::from_u64_reduce(211_587_555_138_949_697),
224            self.0[4] * Fp::from_u64_reduce(1_373_043_270_956_696_022),
225        ])
226    }
227
228    /// Frobenius applied twice: `x^(p^2)`.
229    #[inline]
230    fn frobenius2(self) -> Self {
231        Self([
232            self.0[0],
233            self.0[1] * Fp::from_u64_reduce(15_820_824_984_080_659_046),
234            self.0[2] * Fp::from_u64_reduce(1_373_043_270_956_696_022),
235            self.0[3] * Fp::from_u64_reduce(DTH_ROOT),
236            self.0[4] * Fp::from_u64_reduce(211_587_555_138_949_697),
237        ])
238    }
239
240    /// Double in `Fp5`: returns `self + self`.
241    #[inline]
242    #[must_use]
243    pub fn double(self) -> Self {
244        self.add_inner(self)
245    }
246
247    /// Sign indicator following the elliottech Go reference convention. Used
248    /// by [`Self::canonical_sqrt`] to fix the sign of square roots.
249    ///
250    /// The latch `sign = sign || (zero && sign_i)` with `sign_i = (limb is
251    /// even)` reproduces the upstream behaviour bit-for-bit, including a
252    /// known wrinkle: an element whose first non-zero coefficient is preceded
253    /// by zero coefficients (e.g. `[0, 1, 0, 0, 0]`) reports `true` because a
254    /// leading zero satisfies `sign_i`. This wrinkle has no observable effect
255    /// on [`super::super::curve`]'s `Point::decode`: a flipped `r` swaps
256    /// `x1`/`x2` contents, the subsequent Legendre check then re-selects the
257    /// same non-square root, and the resulting `x` is identical. Phase E
258    /// Layer 2 oracle tests against the Lighter Python SDK gate any
259    /// divergence from the closed-source mainnet signer.
260    #[must_use]
261    pub fn sgn0(self) -> bool {
262        let mut sign = false;
263        let mut zero = true;
264
265        for limb in &self.0 {
266            let sign_i = (limb.to_u64() & 1) == 0;
267            let zero_i = limb.is_zero();
268            sign = sign || (zero && sign_i);
269            zero = zero && zero_i;
270        }
271        sign
272    }
273
274    /// Legendre symbol of `self` in `Fp5`, returned as a base-field element.
275    ///
276    /// Returns `Fp::ZERO` for the zero element, `Fp::ONE` for non-zero squares,
277    /// and `Fp::MINUS_ONE` for non-squares. Uses the Itoh-Tsujii descent into
278    /// `Fp` followed by Euler's criterion split as `x^(2^63) / x^(2^31)`.
279    #[must_use]
280    pub fn legendre(self) -> Fp {
281        let phi1 = self.frobenius();
282        let phi1_phi2 = phi1 * phi1.frobenius();
283        let xr_minus_1 = phi1_phi2 * phi1_phi2.frobenius2();
284
285        let a = &self.0;
286        let f = &xr_minus_1.0;
287        let w = Fp::from_u64_reduce(W);
288        let xr = a[0] * f[0] + w * (a[1] * f[4] + a[2] * f[3] + a[3] * f[2] + a[4] * f[1]);
289
290        let xr31 = xr.msquare(31);
291        let xr63 = xr31.msquare(32);
292        xr63 * xr31.invert()
293    }
294
295    /// Square root in `Fp5` via descent to `Fp`.
296    ///
297    /// Returns `Some(s)` such that `s^2 == self` when one exists (`Some(ZERO)`
298    /// for the zero input); returns `None` for non-squares. The chosen root is
299    /// arbitrary within the two square roots; use [`Self::canonical_sqrt`] for
300    /// a deterministic sign.
301    #[must_use]
302    pub fn sqrt(self) -> Option<Self> {
303        // Repeated squaring lifts `self` to `Fp`-valued exponents; specifically
304        // `g = self^(1 + p + p^2 + p^3 + p^4)` lives in `Fp`. We compute an
305        // intermediate `e` such that `e^2 * g == self^N` for an odd `N`, take
306        // the square root in `Fp`, and divide back through.
307        let v = self.msquare(31);
308        let d = self * v.msquare(32) * v.invert();
309        let e = (d * d.frobenius2()).frobenius();
310        let f_sq = e.square();
311
312        let a = &self.0;
313        let f = &f_sq.0;
314        let w = Fp::from_u64_reduce(W);
315        let g = a[0] * f[0] + w * (a[1] * f[4] + a[2] * f[3] + a[3] * f[2] + a[4] * f[1]);
316
317        let s = g.sqrt()?;
318        let e_inv = e.invert();
319        Some(Self([s, Fp::ZERO, Fp::ZERO, Fp::ZERO, Fp::ZERO]) * e_inv)
320    }
321
322    /// Canonical-sign square root: same as [`Self::sqrt`], with the result
323    /// negated whenever its first non-zero coefficient is even (per [`Self::sgn0`]).
324    #[must_use]
325    pub fn canonical_sqrt(self) -> Option<Self> {
326        let s = self.sqrt()?;
327        if s.sgn0() { Some(-s) } else { Some(s) }
328    }
329
330    /// Multiplicative inverse via Itoh-Tsujii. Returns `Fp5::ZERO` on input zero.
331    ///
332    /// With `r = 1 + p + p^2 + p^3 + p^4`, the value `x^r` lands in the base
333    /// field `Fp`, so we compute `x^(r-1)` cheaply via Frobenius, recover
334    /// `x^r = x_0 * x^(r-1)|_0` inside `Fp`, and divide. The branch-free
335    /// shape preserves the module's constant-time contract: a zero input
336    /// flows through the Frobenius cascade as zero and `Fp::invert(0) = 0`
337    /// folds back into a zero result without an early return.
338    #[must_use]
339    pub fn invert(self) -> Self {
340        let phi1 = self.frobenius();
341        let phi1_phi2 = phi1 * phi1.frobenius();
342        let xr_minus_1 = phi1_phi2 * phi1_phi2.frobenius2();
343
344        // `xr` lives in `Fp` (degree-zero coefficient of `self * xr_minus_1`).
345        let a = &self.0;
346        let f = &xr_minus_1.0;
347        let w = Fp::from_u64_reduce(W);
348        let xr = a[0] * f[0] + w * (a[1] * f[4] + a[2] * f[3] + a[3] * f[2] + a[4] * f[1]);
349
350        xr_minus_1.scalar_mul(xr.invert())
351    }
352
353    /// Exponentiation by an unsigned 64-bit integer, via right-to-left square-and-multiply.
354    #[must_use]
355    pub fn pow(self, mut exp: u64) -> Self {
356        let mut result = Self::ONE;
357        let mut base = self;
358
359        while exp != 0 {
360            if exp & 1 == 1 {
361                result *= base;
362            }
363            base = base.square();
364            exp >>= 1;
365        }
366        result
367    }
368}
369
370impl Default for Fp5 {
371    #[inline]
372    fn default() -> Self {
373        Self::ZERO
374    }
375}
376
377impl Add for Fp5 {
378    type Output = Self;
379    #[inline]
380    fn add(self, rhs: Self) -> Self {
381        self.add_inner(rhs)
382    }
383}
384
385impl AddAssign for Fp5 {
386    #[inline]
387    fn add_assign(&mut self, rhs: Self) {
388        *self = self.add_inner(rhs);
389    }
390}
391
392impl Sub for Fp5 {
393    type Output = Self;
394    #[inline]
395    fn sub(self, rhs: Self) -> Self {
396        self.sub_inner(rhs)
397    }
398}
399
400impl SubAssign for Fp5 {
401    #[inline]
402    fn sub_assign(&mut self, rhs: Self) {
403        *self = self.sub_inner(rhs);
404    }
405}
406
407impl Neg for Fp5 {
408    type Output = Self;
409    #[inline]
410    fn neg(self) -> Self {
411        self.neg_inner()
412    }
413}
414
415impl Mul for Fp5 {
416    type Output = Self;
417    #[inline]
418    fn mul(self, rhs: Self) -> Self {
419        self.mul_inner(rhs)
420    }
421}
422
423impl MulAssign for Fp5 {
424    #[inline]
425    fn mul_assign(&mut self, rhs: Self) {
426        *self = self.mul_inner(rhs);
427    }
428}
429
430#[cfg(test)]
431mod tests {
432    use proptest::prelude::*;
433    use rstest::rstest;
434    use serde::Deserialize;
435
436    use super::*;
437    use crate::signing::{
438        field::MODULUS,
439        fixtures::{arb_fp5, arb_fp5_nonzero, hex_to_bytes},
440    };
441
442    const VECTORS_JSON: &str = include_str!(concat!(
443        env!("CARGO_MANIFEST_DIR"),
444        "/test_data/signing_field_quintic_vectors.json",
445    ));
446
447    #[derive(Debug, Deserialize)]
448    struct Vectors {
449        vectors: Vec<Vector>,
450    }
451
452    #[derive(Debug, Deserialize)]
453    struct Vector {
454        a: String,
455        b: String,
456        e: String,
457        add: String,
458        sub: String,
459        mul: String,
460        neg_a: String,
461        inv_a: String,
462        pow_a_e: String,
463        a_eq_b: bool,
464    }
465
466    fn decode_le40(hex: &str) -> [u8; 40] {
467        let bytes = hex_to_bytes(hex);
468        assert_eq!(bytes.len(), 40, "expected 40 bytes, was {}", bytes.len());
469        let mut out = [0u8; 40];
470        out.copy_from_slice(&bytes);
471        out
472    }
473
474    fn parse_u64(s: &str) -> u64 {
475        if let Some(stripped) = s.strip_prefix("0x") {
476            u64::from_str_radix(stripped, 16).unwrap()
477        } else {
478            s.parse::<u64>().unwrap()
479        }
480    }
481
482    #[rstest]
483    fn round_trip_le_bytes_canonical() {
484        let v = Fp5::from_u64s_reduce([1, 2, 3, 4, 5]);
485        let bytes = v.to_le_bytes();
486        assert_eq!(Fp5::try_from_le_bytes(bytes).unwrap(), v);
487    }
488
489    #[rstest]
490    fn one_is_multiplicative_identity() {
491        let v = Fp5::from_u64s_reduce([7, 11, 13, 17, 19]);
492        assert_eq!(v * Fp5::ONE, v);
493        assert_eq!(Fp5::ONE * v, v);
494    }
495
496    #[rstest]
497    fn invert_zero_returns_zero() {
498        assert_eq!(Fp5::ZERO.invert(), Fp5::ZERO);
499    }
500
501    #[rstest]
502    fn invert_round_trip() {
503        let v = Fp5::from_u64s_reduce([7, 11, 13, 17, 19]);
504        assert_eq!(v * v.invert(), Fp5::ONE);
505    }
506
507    #[rstest]
508    fn double_matches_self_addition() {
509        let v = Fp5::from_u64s_reduce([1, 2, 3, 4, 5]);
510        assert_eq!(v.double(), v + v);
511    }
512
513    #[rstest]
514    fn ct_select_picks_branch_by_mask() {
515        let a = Fp5::from_u64s_reduce([1, 2, 3, 4, 5]);
516        let b = Fp5::from_u64s_reduce([10, 20, 30, 40, 50]);
517        assert_eq!(Fp5::ct_select(0, a, b), a);
518        assert_eq!(Fp5::ct_select(u64::MAX, a, b), b);
519    }
520
521    #[rstest]
522    fn legendre_classifies_squares() {
523        let v = Fp5::from_u64s_reduce([7, 11, 13, 17, 19]);
524        let v_sq = v.square();
525        assert_eq!(v_sq.legendre(), Fp::ONE);
526        assert_eq!(Fp5::ZERO.legendre(), Fp::ZERO);
527    }
528
529    #[rstest]
530    fn sqrt_round_trip_for_squares() {
531        let v = Fp5::from_u64s_reduce([7, 11, 13, 17, 19]);
532        let v_sq = v.square();
533        let s = v_sq.sqrt().expect("v_sq is a square by construction");
534        assert_eq!(s.square(), v_sq);
535    }
536
537    #[rstest]
538    fn canonical_sqrt_picks_odd_first_limb() {
539        let v = Fp5::from_u64s_reduce([7, 11, 13, 17, 19]);
540        let v_sq = v.square();
541        let s = v_sq
542            .canonical_sqrt()
543            .expect("v_sq is a square by construction");
544        assert_eq!(s.square(), v_sq);
545        assert!(!s.sgn0(), "canonical_sqrt result must have sgn0 == false");
546    }
547
548    /// `from_u64s_canonical` rejects any non-canonical limb (`>= MODULUS`),
549    /// for each of the five limb positions in turn.
550    #[rstest]
551    #[case(0)]
552    #[case(1)]
553    #[case(2)]
554    #[case(3)]
555    #[case(4)]
556    fn from_u64s_canonical_rejects_non_canonical_limb(#[case] limb_index: usize) {
557        let mut limbs = [1u64, 2, 3, 4, 5];
558        limbs[limb_index] = MODULUS;
559        assert!(
560            Fp5::from_u64s_canonical(limbs).is_none(),
561            "limb {limb_index} == MODULUS must be rejected",
562        );
563
564        limbs[limb_index] = u64::MAX;
565        assert!(
566            Fp5::from_u64s_canonical(limbs).is_none(),
567            "limb {limb_index} == u64::MAX must be rejected",
568        );
569    }
570
571    proptest! {
572        /// `Fp5` addition is commutative.
573        #[rstest]
574        fn prop_add_commutative(a in arb_fp5(), b in arb_fp5()) {
575            prop_assert_eq!(a + b, b + a);
576        }
577
578        /// `Fp5` addition is associative.
579        #[rstest]
580        fn prop_add_associative(a in arb_fp5(), b in arb_fp5(), c in arb_fp5()) {
581            prop_assert_eq!((a + b) + c, a + (b + c));
582        }
583
584        /// Multiplication distributes over addition.
585        #[rstest]
586        fn prop_distributive(a in arb_fp5(), b in arb_fp5(), c in arb_fp5()) {
587            prop_assert_eq!(a * (b + c), a * b + a * c);
588        }
589
590        /// Multiplication is commutative.
591        #[rstest]
592        fn prop_mul_commutative(a in arb_fp5(), b in arb_fp5()) {
593            prop_assert_eq!(a * b, b * a);
594        }
595
596        /// Multiplication is associative.
597        #[rstest]
598        fn prop_mul_associative(a in arb_fp5(), b in arb_fp5(), c in arb_fp5()) {
599            prop_assert_eq!((a * b) * c, a * (b * c));
600        }
601
602        /// `a + (-a) == 0`.
603        #[rstest]
604        fn prop_neg_round_trip(a in arb_fp5()) {
605            prop_assert_eq!(a + (-a), Fp5::ZERO);
606        }
607
608        /// `a - b == a + (-b)`.
609        #[rstest]
610        fn prop_sub_via_add_neg(a in arb_fp5(), b in arb_fp5()) {
611            prop_assert_eq!(a - b, a + (-b));
612        }
613
614        /// `(a + b) - b == a`.
615        #[rstest]
616        fn prop_sub_round_trip(a in arb_fp5(), b in arb_fp5()) {
617            prop_assert_eq!((a + b) - b, a);
618        }
619
620        /// Squaring matches self-multiplication.
621        #[rstest]
622        fn prop_square_matches_self_mul(a in arb_fp5()) {
623            prop_assert_eq!(a.square(), a * a);
624        }
625
626        /// `double` matches self addition.
627        #[rstest]
628        fn prop_double_matches_self_addition(a in arb_fp5()) {
629            prop_assert_eq!(a.double(), a + a);
630        }
631
632        /// `a * a.invert() == 1` for any non-zero element.
633        #[rstest]
634        fn prop_invert_round_trip(a in arb_fp5_nonzero()) {
635            prop_assert_eq!(a * a.invert(), Fp5::ONE);
636        }
637
638        /// `(a^2).sqrt()^2 == a^2`: sqrt of any known square round-trips.
639        #[rstest]
640        fn prop_sqrt_round_trip(a in arb_fp5()) {
641            let sq = a.square();
642            let s = sq.sqrt().expect("squares are quadratic residues");
643            prop_assert_eq!(s.square(), sq);
644        }
645
646        /// `canonical_sqrt(a^2)^2 == a^2`: the canonicalised root squares
647        /// back to the input. The result's `sgn0` is NOT asserted here:
648        /// when the root falls into the documented leading-zero wrinkle on
649        /// `sgn0` (both root and its negation report `true`), `canonical_sqrt`
650        /// returns the negated root which still reports `true`. That branch
651        /// has no observable effect on `Point::decode` per the doc on
652        /// `Fp5::sgn0`, and the byte-equality oracle vectors pin the wider
653        /// behaviour end-to-end.
654        #[rstest]
655        fn prop_canonical_sqrt_round_trip(a in arb_fp5_nonzero()) {
656            let sq = a.square();
657            let s = sq.canonical_sqrt().expect("squares are quadratic residues");
658            prop_assert_eq!(s.square(), sq);
659        }
660
661        /// `canonical_sqrt` is deterministic: invoking it twice on the same
662        /// input produces the same root.
663        #[rstest]
664        fn prop_canonical_sqrt_deterministic(a in arb_fp5_nonzero()) {
665            let sq = a.square();
666            prop_assert_eq!(sq.canonical_sqrt(), sq.canonical_sqrt());
667        }
668
669        /// The Lighter-style sign latch is anti-symmetric for any element
670        /// whose first coefficient is non-zero: exactly one of `x` and
671        /// `-x` reports `sgn0 == true`. Pins the latch contract on the
672        /// no-leading-zero branch documented at `Fp5::sgn0`. (The wrinkle
673        /// where `c[0] == 0` makes both `x` and `-x` report `true` is
674        /// excluded from this strategy by construction; the doc on
675        /// `Fp5::sgn0` notes the wrinkle has no observable effect on the
676        /// curve `decode` path that consumes this primitive.)
677        #[rstest]
678        fn prop_sgn0_negation_anti_symmetric(
679            a in arb_fp5_nonzero().prop_filter("c0 nonzero", |x| !x.0[0].is_zero()),
680        ) {
681            prop_assert_ne!(a.sgn0(), (-a).sgn0());
682        }
683
684        /// `Fp5` Legendre symbol is multiplicative: `legendre(a*b) ==
685        /// legendre(a) * legendre(b)` for non-zero operands.
686        #[rstest]
687        fn prop_legendre_multiplicative(a in arb_fp5_nonzero(), b in arb_fp5_nonzero()) {
688            let prod = a * b;
689            prop_assume!(!prod.is_zero());
690            prop_assert_eq!(prod.legendre(), a.legendre() * b.legendre());
691        }
692
693        /// Squares produce Legendre `+1`.
694        #[rstest]
695        fn prop_legendre_square_is_one(a in arb_fp5_nonzero()) {
696            prop_assert_eq!(a.square().legendre(), Fp::ONE);
697        }
698
699        /// `frobenius` applied five times is the identity (since `phi(x) = x^p`
700        /// and `Fp5` has order `p^5 - 1`, `phi^5 = id`).
701        #[rstest]
702        fn prop_frobenius_iter_five_is_identity(a in arb_fp5()) {
703            let phi5 = a.frobenius().frobenius().frobenius().frobenius().frobenius();
704            prop_assert_eq!(phi5, a);
705        }
706
707        /// Frobenius is a ring homomorphism over multiplication.
708        #[rstest]
709        fn prop_frobenius_multiplicative(a in arb_fp5(), b in arb_fp5()) {
710            prop_assert_eq!((a * b).frobenius(), a.frobenius() * b.frobenius());
711        }
712
713        /// `frobenius2` matches `frobenius` applied twice.
714        #[rstest]
715        fn prop_frobenius2_matches_double_frobenius(a in arb_fp5()) {
716            prop_assert_eq!(a.frobenius2(), a.frobenius().frobenius());
717        }
718
719        /// Canonical bytes round-trip.
720        #[rstest]
721        fn prop_le_bytes_round_trip(a in arb_fp5()) {
722            let bytes = a.to_le_bytes();
723            prop_assert_eq!(Fp5::try_from_le_bytes(bytes).unwrap(), a);
724        }
725
726        /// `ct_select` picks `a` for mask 0 and `b` for mask u64::MAX.
727        #[rstest]
728        fn prop_ct_select_picks_branch(a in arb_fp5(), b in arb_fp5()) {
729            prop_assert_eq!(Fp5::ct_select(0, a, b), a);
730            prop_assert_eq!(Fp5::ct_select(u64::MAX, a, b), b);
731        }
732
733        /// `ct_eq` agrees with `==`.
734        #[rstest]
735        fn prop_ct_eq_matches_partial_eq(a in arb_fp5(), b in arb_fp5()) {
736            let ct = a.ct_eq(b);
737            if a == b {
738                prop_assert_eq!(ct, u64::MAX);
739            } else {
740                prop_assert_eq!(ct, 0);
741            }
742        }
743    }
744
745    #[rstest]
746    fn matches_go_reference_vectors() {
747        let suite: Vectors = serde_json::from_str(VECTORS_JSON).expect("parse vectors");
748        assert!(!suite.vectors.is_empty(), "vector file is empty");
749
750        for (i, v) in suite.vectors.iter().enumerate() {
751            let a = Fp5::try_from_le_bytes(decode_le40(&v.a))
752                .unwrap_or_else(|| panic!("vector {i}: decode a"));
753            let b = Fp5::try_from_le_bytes(decode_le40(&v.b))
754                .unwrap_or_else(|| panic!("vector {i}: decode b"));
755            let e = parse_u64(&v.e);
756
757            assert_eq!(
758                (a + b).to_le_bytes(),
759                decode_le40(&v.add),
760                "vector {i}: add"
761            );
762            assert_eq!(
763                (a - b).to_le_bytes(),
764                decode_le40(&v.sub),
765                "vector {i}: sub"
766            );
767            assert_eq!(
768                (a * b).to_le_bytes(),
769                decode_le40(&v.mul),
770                "vector {i}: mul"
771            );
772            assert_eq!((-a).to_le_bytes(), decode_le40(&v.neg_a), "vector {i}: neg");
773            assert_eq!(
774                a.invert().to_le_bytes(),
775                decode_le40(&v.inv_a),
776                "vector {i}: inv"
777            );
778            assert_eq!(
779                a.pow(e).to_le_bytes(),
780                decode_le40(&v.pow_a_e),
781                "vector {i}: pow"
782            );
783            assert_eq!(a == b, v.a_eq_b, "vector {i}: eq");
784        }
785    }
786}
nautilus_lighter/signing/field/quintic.rs

nautilus_lighter/signing/field/
quintic.rs
