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        Self([
179            self.mul_coefficient_0(rhs),
180            self.mul_coefficient_1(rhs),
181            self.mul_coefficient_2(rhs),
182            self.mul_coefficient_3(rhs),
183            self.mul_coefficient_4(rhs),
184        ])
185    }
186
187    #[inline(always)]
188    fn mul_coefficient_0(self, rhs: Self) -> Fp {
189        let p0 = (self.0[0].0 as u128) * (rhs.0[0].0 as u128);
190        let p1 = (self.0[1].0 as u128) * (rhs.0[4].0 as u128);
191        let p2 = (self.0[2].0 as u128) * (rhs.0[3].0 as u128);
192        let p3 = (self.0[3].0 as u128) * (rhs.0[2].0 as u128);
193        let p4 = (self.0[4].0 as u128) * (rhs.0[1].0 as u128);
194        let hi = (p0 >> 64) + 3 * ((p1 >> 64) + (p2 >> 64) + (p3 >> 64) + (p4 >> 64));
195        let lo = (p0 as u64 as u128)
196            + 3 * (p1 as u64 as u128 + p2 as u64 as u128 + p3 as u64 as u128 + p4 as u64 as u128);
197        Fp::from_montgomery_products(lo, hi)
198    }
199
200    #[inline(always)]
201    fn mul_coefficient_1(self, rhs: Self) -> Fp {
202        let p0 = (self.0[0].0 as u128) * (rhs.0[1].0 as u128);
203        let p1 = (self.0[1].0 as u128) * (rhs.0[0].0 as u128);
204        let p2 = (self.0[2].0 as u128) * (rhs.0[4].0 as u128);
205        let p3 = (self.0[3].0 as u128) * (rhs.0[3].0 as u128);
206        let p4 = (self.0[4].0 as u128) * (rhs.0[2].0 as u128);
207        let hi = (p0 >> 64) + (p1 >> 64) + 3 * ((p2 >> 64) + (p3 >> 64) + (p4 >> 64));
208        let lo = (p0 as u64 as u128)
209            + (p1 as u64 as u128)
210            + 3 * (p2 as u64 as u128 + p3 as u64 as u128 + p4 as u64 as u128);
211        Fp::from_montgomery_products(lo, hi)
212    }
213
214    #[inline(always)]
215    fn mul_coefficient_2(self, rhs: Self) -> Fp {
216        let p0 = (self.0[0].0 as u128) * (rhs.0[2].0 as u128);
217        let p1 = (self.0[1].0 as u128) * (rhs.0[1].0 as u128);
218        let p2 = (self.0[2].0 as u128) * (rhs.0[0].0 as u128);
219        let p3 = (self.0[3].0 as u128) * (rhs.0[4].0 as u128);
220        let p4 = (self.0[4].0 as u128) * (rhs.0[3].0 as u128);
221        let hi = (p0 >> 64) + (p1 >> 64) + (p2 >> 64) + 3 * ((p3 >> 64) + (p4 >> 64));
222        let lo = (p0 as u64 as u128)
223            + (p1 as u64 as u128)
224            + (p2 as u64 as u128)
225            + 3 * (p3 as u64 as u128 + p4 as u64 as u128);
226        Fp::from_montgomery_products(lo, hi)
227    }
228
229    #[inline(always)]
230    fn mul_coefficient_3(self, rhs: Self) -> Fp {
231        let p0 = (self.0[0].0 as u128) * (rhs.0[3].0 as u128);
232        let p1 = (self.0[1].0 as u128) * (rhs.0[2].0 as u128);
233        let p2 = (self.0[2].0 as u128) * (rhs.0[1].0 as u128);
234        let p3 = (self.0[3].0 as u128) * (rhs.0[0].0 as u128);
235        let p4 = (self.0[4].0 as u128) * (rhs.0[4].0 as u128);
236        let hi = (p0 >> 64) + (p1 >> 64) + (p2 >> 64) + (p3 >> 64) + 3 * (p4 >> 64);
237        let lo = (p0 as u64 as u128)
238            + (p1 as u64 as u128)
239            + (p2 as u64 as u128)
240            + (p3 as u64 as u128)
241            + 3 * (p4 as u64 as u128);
242        Fp::from_montgomery_products(lo, hi)
243    }
244
245    #[inline(always)]
246    fn mul_coefficient_4(self, rhs: Self) -> Fp {
247        let p0 = (self.0[0].0 as u128) * (rhs.0[4].0 as u128);
248        let p1 = (self.0[1].0 as u128) * (rhs.0[3].0 as u128);
249        let p2 = (self.0[2].0 as u128) * (rhs.0[2].0 as u128);
250        let p3 = (self.0[3].0 as u128) * (rhs.0[1].0 as u128);
251        let p4 = (self.0[4].0 as u128) * (rhs.0[0].0 as u128);
252        let hi = (p0 >> 64) + (p1 >> 64) + (p2 >> 64) + (p3 >> 64) + (p4 >> 64);
253        let lo = (p0 as u64 as u128)
254            + (p1 as u64 as u128)
255            + (p2 as u64 as u128)
256            + (p3 as u64 as u128)
257            + (p4 as u64 as u128);
258        Fp::from_montgomery_products(lo, hi)
259    }
260
261    /// Squaring in `Fp5`.
262    #[inline]
263    #[must_use]
264    pub fn square(self) -> Self {
265        Self([
266            self.square_coefficient_0(),
267            self.square_coefficient_1(),
268            self.square_coefficient_2(),
269            self.square_coefficient_3(),
270            self.square_coefficient_4(),
271        ])
272    }
273
274    #[inline(always)]
275    fn square_coefficient_0(self) -> Fp {
276        let p0 = (self.0[0].0 as u128) * (self.0[0].0 as u128);
277        let p1 = (self.0[1].0 as u128) * (self.0[4].0 as u128);
278        let p2 = (self.0[2].0 as u128) * (self.0[3].0 as u128);
279        let hi = (p0 >> 64) + 6 * ((p1 >> 64) + (p2 >> 64));
280        let lo = (p0 as u64 as u128) + 6 * (p1 as u64 as u128 + p2 as u64 as u128);
281        Fp::from_montgomery_products(lo, hi)
282    }
283
284    #[inline(always)]
285    fn square_coefficient_1(self) -> Fp {
286        let p0 = (self.0[0].0 as u128) * (self.0[1].0 as u128);
287        let p2 = (self.0[2].0 as u128) * (self.0[4].0 as u128);
288        let p3 = (self.0[3].0 as u128) * (self.0[3].0 as u128);
289        let hi = 2 * (p0 >> 64) + 6 * (p2 >> 64) + 3 * (p3 >> 64);
290        let lo = 2 * (p0 as u64 as u128) + 6 * (p2 as u64 as u128) + 3 * (p3 as u64 as u128);
291        Fp::from_montgomery_products(lo, hi)
292    }
293
294    #[inline(always)]
295    fn square_coefficient_2(self) -> Fp {
296        let p0 = (self.0[0].0 as u128) * (self.0[2].0 as u128);
297        let p1 = (self.0[1].0 as u128) * (self.0[1].0 as u128);
298        let p3 = (self.0[3].0 as u128) * (self.0[4].0 as u128);
299        let hi = 2 * (p0 >> 64) + (p1 >> 64) + 6 * (p3 >> 64);
300        let lo = 2 * (p0 as u64 as u128) + (p1 as u64 as u128) + 6 * (p3 as u64 as u128);
301        Fp::from_montgomery_products(lo, hi)
302    }
303
304    #[inline(always)]
305    fn square_coefficient_3(self) -> Fp {
306        let p0 = (self.0[0].0 as u128) * (self.0[3].0 as u128);
307        let p1 = (self.0[1].0 as u128) * (self.0[2].0 as u128);
308        let p4 = (self.0[4].0 as u128) * (self.0[4].0 as u128);
309        let hi = 2 * ((p0 >> 64) + (p1 >> 64)) + 3 * (p4 >> 64);
310        let lo = 2 * (p0 as u64 as u128 + p1 as u64 as u128) + 3 * (p4 as u64 as u128);
311        Fp::from_montgomery_products(lo, hi)
312    }
313
314    #[inline(always)]
315    fn square_coefficient_4(self) -> Fp {
316        let p0 = (self.0[0].0 as u128) * (self.0[4].0 as u128);
317        let p1 = (self.0[1].0 as u128) * (self.0[3].0 as u128);
318        let p2 = (self.0[2].0 as u128) * (self.0[2].0 as u128);
319        let hi = 2 * ((p0 >> 64) + (p1 >> 64)) + (p2 >> 64);
320        let lo = 2 * (p0 as u64 as u128 + p1 as u64 as u128) + (p2 as u64 as u128);
321        Fp::from_montgomery_products(lo, hi)
322    }
323
324    /// Repeated squaring: returns `self^(2^n)`.
325    #[inline]
326    #[must_use]
327    pub fn msquare(self, n: u32) -> Self {
328        let mut x = self;
329        for _ in 0..n {
330            x = x.square();
331        }
332        x
333    }
334
335    /// Frobenius operator: `phi(x) = x^p`.
336    ///
337    /// Acts on `(c0, c1, c2, c3, c4)` as multiplication of each higher-degree
338    /// coefficient by a precomputed power of the `d`-th root of unity in `Fp`.
339    #[inline]
340    fn frobenius(self) -> Self {
341        // Coefficients = `DTH_ROOT^i` for i=0..4 (i=0 fixed at 1).
342        // DTH_ROOT^2 = 15820824984080659046, DTH_ROOT^3 = 211587555138949697,
343        // DTH_ROOT^4 = 1373043270956696022 (matches Pornin and elliottech).
344        Self([
345            self.0[0],
346            self.0[1] * Fp::from_u64_reduce(DTH_ROOT),
347            self.0[2] * Fp::from_u64_reduce(15_820_824_984_080_659_046),
348            self.0[3] * Fp::from_u64_reduce(211_587_555_138_949_697),
349            self.0[4] * Fp::from_u64_reduce(1_373_043_270_956_696_022),
350        ])
351    }
352
353    /// Frobenius applied twice: `x^(p^2)`.
354    #[inline]
355    fn frobenius2(self) -> Self {
356        Self([
357            self.0[0],
358            self.0[1] * Fp::from_u64_reduce(15_820_824_984_080_659_046),
359            self.0[2] * Fp::from_u64_reduce(1_373_043_270_956_696_022),
360            self.0[3] * Fp::from_u64_reduce(DTH_ROOT),
361            self.0[4] * Fp::from_u64_reduce(211_587_555_138_949_697),
362        ])
363    }
364
365    /// Double in `Fp5`: returns `self + self`.
366    #[inline]
367    #[must_use]
368    pub fn double(self) -> Self {
369        self.add_inner(self)
370    }
371
372    /// Sign indicator following the elliottech Go reference convention. Used
373    /// by [`Self::canonical_sqrt`] to fix the sign of square roots.
374    ///
375    /// The latch `sign = sign || (zero && sign_i)` with `sign_i = (limb is
376    /// even)` reproduces the upstream behaviour bit-for-bit, including a
377    /// known wrinkle: an element whose first non-zero coefficient is preceded
378    /// by zero coefficients (e.g. `[0, 1, 0, 0, 0]`) reports `true` because a
379    /// leading zero satisfies `sign_i`. This wrinkle has no observable effect
380    /// on [`super::super::curve`]'s `Point::decode`: a flipped `r` swaps
381    /// `x1`/`x2` contents, the subsequent Legendre check then re-selects the
382    /// same non-square root, and the resulting `x` is identical. Phase E
383    /// Layer 2 oracle tests against the Lighter Python SDK gate any
384    /// divergence from the closed-source mainnet signer.
385    #[must_use]
386    pub fn sgn0(self) -> bool {
387        let mut sign = false;
388        let mut zero = true;
389
390        for limb in &self.0 {
391            let sign_i = (limb.to_u64() & 1) == 0;
392            let zero_i = limb.is_zero();
393            sign = sign || (zero && sign_i);
394            zero = zero && zero_i;
395        }
396        sign
397    }
398
399    /// Legendre symbol of `self` in `Fp5`, returned as a base-field element.
400    ///
401    /// Returns `Fp::ZERO` for the zero element, `Fp::ONE` for non-zero squares,
402    /// and `Fp::MINUS_ONE` for non-squares. Uses the Itoh-Tsujii descent into
403    /// `Fp` followed by Euler's criterion split as `x^(2^63) / x^(2^31)`.
404    #[must_use]
405    pub fn legendre(self) -> Fp {
406        let phi1 = self.frobenius();
407        let phi1_phi2 = phi1 * phi1.frobenius();
408        let xr_minus_1 = phi1_phi2 * phi1_phi2.frobenius2();
409
410        let a = &self.0;
411        let f = &xr_minus_1.0;
412        let w = Fp::from_u64_reduce(W);
413        let xr = a[0] * f[0] + w * (a[1] * f[4] + a[2] * f[3] + a[3] * f[2] + a[4] * f[1]);
414
415        let xr31 = xr.msquare(31);
416        let xr63 = xr31.msquare(32);
417        xr63 * xr31.invert()
418    }
419
420    /// Square root in `Fp5` via descent to `Fp`.
421    ///
422    /// Returns `Some(s)` such that `s^2 == self` when one exists (`Some(ZERO)`
423    /// for the zero input); returns `None` for non-squares. The chosen root is
424    /// arbitrary within the two square roots; use [`Self::canonical_sqrt`] for
425    /// a deterministic sign.
426    #[must_use]
427    pub fn sqrt(self) -> Option<Self> {
428        // Repeated squaring lifts `self` to `Fp`-valued exponents; specifically
429        // `g = self^(1 + p + p^2 + p^3 + p^4)` lives in `Fp`. We compute an
430        // intermediate `e` such that `e^2 * g == self^N` for an odd `N`, take
431        // the square root in `Fp`, and divide back through.
432        let v = self.msquare(31);
433        let d = self * v.msquare(32) * v.invert();
434        let e = (d * d.frobenius2()).frobenius();
435        let f_sq = e.square();
436
437        let a = &self.0;
438        let f = &f_sq.0;
439        let w = Fp::from_u64_reduce(W);
440        let g = a[0] * f[0] + w * (a[1] * f[4] + a[2] * f[3] + a[3] * f[2] + a[4] * f[1]);
441
442        let s = g.sqrt()?;
443        let e_inv = e.invert();
444        Some(Self([s, Fp::ZERO, Fp::ZERO, Fp::ZERO, Fp::ZERO]) * e_inv)
445    }
446
447    /// Canonical-sign square root: same as [`Self::sqrt`], with the result
448    /// negated whenever its first non-zero coefficient is even (per [`Self::sgn0`]).
449    #[must_use]
450    pub fn canonical_sqrt(self) -> Option<Self> {
451        let s = self.sqrt()?;
452        if s.sgn0() { Some(-s) } else { Some(s) }
453    }
454
455    /// Multiplicative inverse via Itoh-Tsujii. Returns `Fp5::ZERO` on input zero.
456    ///
457    /// With `r = 1 + p + p^2 + p^3 + p^4`, the value `x^r` lands in the base
458    /// field `Fp`, so we compute `x^(r-1)` cheaply via Frobenius, recover
459    /// `x^r = x_0 * x^(r-1)|_0` inside `Fp`, and divide. The branch-free
460    /// shape preserves the module's constant-time contract: a zero input
461    /// flows through the Frobenius cascade as zero and `Fp::invert(0) = 0`
462    /// folds back into a zero result without an early return.
463    #[must_use]
464    pub fn invert(self) -> Self {
465        let phi1 = self.frobenius();
466        let phi1_phi2 = phi1 * phi1.frobenius();
467        let xr_minus_1 = phi1_phi2 * phi1_phi2.frobenius2();
468
469        // `xr` lives in `Fp` (degree-zero coefficient of `self * xr_minus_1`).
470        let a = &self.0;
471        let f = &xr_minus_1.0;
472        let w = Fp::from_u64_reduce(W);
473        let xr = a[0] * f[0] + w * (a[1] * f[4] + a[2] * f[3] + a[3] * f[2] + a[4] * f[1]);
474
475        xr_minus_1.scalar_mul(xr.invert())
476    }
477
478    /// Exponentiation by an unsigned 64-bit integer, via right-to-left square-and-multiply.
479    #[must_use]
480    pub fn pow(self, mut exp: u64) -> Self {
481        let mut result = Self::ONE;
482        let mut base = self;
483
484        while exp != 0 {
485            if exp & 1 == 1 {
486                result *= base;
487            }
488            base = base.square();
489            exp >>= 1;
490        }
491        result
492    }
493}
494
495impl Default for Fp5 {
496    #[inline]
497    fn default() -> Self {
498        Self::ZERO
499    }
500}
501
502impl Add for Fp5 {
503    type Output = Self;
504    #[inline]
505    fn add(self, rhs: Self) -> Self {
506        self.add_inner(rhs)
507    }
508}
509
510impl AddAssign for Fp5 {
511    #[inline]
512    fn add_assign(&mut self, rhs: Self) {
513        *self = self.add_inner(rhs);
514    }
515}
516
517impl Sub for Fp5 {
518    type Output = Self;
519    #[inline]
520    fn sub(self, rhs: Self) -> Self {
521        self.sub_inner(rhs)
522    }
523}
524
525impl SubAssign for Fp5 {
526    #[inline]
527    fn sub_assign(&mut self, rhs: Self) {
528        *self = self.sub_inner(rhs);
529    }
530}
531
532impl Neg for Fp5 {
533    type Output = Self;
534    #[inline]
535    fn neg(self) -> Self {
536        self.neg_inner()
537    }
538}
539
540impl Mul for Fp5 {
541    type Output = Self;
542    #[inline]
543    fn mul(self, rhs: Self) -> Self {
544        self.mul_inner(rhs)
545    }
546}
547
548impl MulAssign for Fp5 {
549    #[inline]
550    fn mul_assign(&mut self, rhs: Self) {
551        *self = self.mul_inner(rhs);
552    }
553}
554
555#[cfg(test)]
556mod tests {
557    use proptest::prelude::*;
558    use rstest::rstest;
559    use serde::Deserialize;
560
561    use super::*;
562    use crate::signing::{
563        field::MODULUS,
564        fixtures::{arb_fp5, arb_fp5_nonzero, hex_to_bytes},
565    };
566
567    const VECTORS_JSON: &str = include_str!(concat!(
568        env!("CARGO_MANIFEST_DIR"),
569        "/test_data/signing_field_quintic_vectors.json",
570    ));
571
572    #[derive(Debug, Deserialize)]
573    struct Vectors {
574        vectors: Vec<Vector>,
575    }
576
577    #[derive(Debug, Deserialize)]
578    struct Vector {
579        a: String,
580        b: String,
581        e: String,
582        add: String,
583        sub: String,
584        mul: String,
585        neg_a: String,
586        inv_a: String,
587        pow_a_e: String,
588        a_eq_b: bool,
589    }
590
591    fn decode_le40(hex: &str) -> [u8; 40] {
592        let bytes = hex_to_bytes(hex);
593        assert_eq!(bytes.len(), 40, "expected 40 bytes, was {}", bytes.len());
594        let mut out = [0u8; 40];
595        out.copy_from_slice(&bytes);
596        out
597    }
598
599    fn parse_u64(s: &str) -> u64 {
600        if let Some(stripped) = s.strip_prefix("0x") {
601            u64::from_str_radix(stripped, 16).unwrap()
602        } else {
603            s.parse::<u64>().unwrap()
604        }
605    }
606
607    #[rstest]
608    fn round_trip_le_bytes_canonical() {
609        let v = Fp5::from_u64s_reduce([1, 2, 3, 4, 5]);
610        let bytes = v.to_le_bytes();
611        assert_eq!(Fp5::try_from_le_bytes(bytes).unwrap(), v);
612    }
613
614    #[rstest]
615    fn one_is_multiplicative_identity() {
616        let v = Fp5::from_u64s_reduce([7, 11, 13, 17, 19]);
617        assert_eq!(v * Fp5::ONE, v);
618        assert_eq!(Fp5::ONE * v, v);
619    }
620
621    #[rstest]
622    fn invert_zero_returns_zero() {
623        assert_eq!(Fp5::ZERO.invert(), Fp5::ZERO);
624    }
625
626    #[rstest]
627    fn invert_round_trip() {
628        let v = Fp5::from_u64s_reduce([7, 11, 13, 17, 19]);
629        assert_eq!(v * v.invert(), Fp5::ONE);
630    }
631
632    #[rstest]
633    fn double_matches_self_addition() {
634        let v = Fp5::from_u64s_reduce([1, 2, 3, 4, 5]);
635        assert_eq!(v.double(), v + v);
636    }
637
638    #[rstest]
639    fn ct_select_picks_branch_by_mask() {
640        let a = Fp5::from_u64s_reduce([1, 2, 3, 4, 5]);
641        let b = Fp5::from_u64s_reduce([10, 20, 30, 40, 50]);
642        assert_eq!(Fp5::ct_select(0, a, b), a);
643        assert_eq!(Fp5::ct_select(u64::MAX, a, b), b);
644    }
645
646    #[rstest]
647    fn legendre_classifies_squares() {
648        let v = Fp5::from_u64s_reduce([7, 11, 13, 17, 19]);
649        let v_sq = v.square();
650        assert_eq!(v_sq.legendre(), Fp::ONE);
651        assert_eq!(Fp5::ZERO.legendre(), Fp::ZERO);
652    }
653
654    #[rstest]
655    fn sqrt_round_trip_for_squares() {
656        let v = Fp5::from_u64s_reduce([7, 11, 13, 17, 19]);
657        let v_sq = v.square();
658        let s = v_sq.sqrt().expect("v_sq is a square by construction");
659        assert_eq!(s.square(), v_sq);
660    }
661
662    #[rstest]
663    fn canonical_sqrt_picks_odd_first_limb() {
664        let v = Fp5::from_u64s_reduce([7, 11, 13, 17, 19]);
665        let v_sq = v.square();
666        let s = v_sq
667            .canonical_sqrt()
668            .expect("v_sq is a square by construction");
669        assert_eq!(s.square(), v_sq);
670        assert!(!s.sgn0(), "canonical_sqrt result must have sgn0 == false");
671    }
672
673    /// `from_u64s_canonical` rejects any non-canonical limb (`>= MODULUS`),
674    /// for each of the five limb positions in turn.
675    #[rstest]
676    #[case(0)]
677    #[case(1)]
678    #[case(2)]
679    #[case(3)]
680    #[case(4)]
681    fn from_u64s_canonical_rejects_non_canonical_limb(#[case] limb_index: usize) {
682        let mut limbs = [1u64, 2, 3, 4, 5];
683        limbs[limb_index] = MODULUS;
684        assert!(
685            Fp5::from_u64s_canonical(limbs).is_none(),
686            "limb {limb_index} == MODULUS must be rejected",
687        );
688
689        limbs[limb_index] = u64::MAX;
690        assert!(
691            Fp5::from_u64s_canonical(limbs).is_none(),
692            "limb {limb_index} == u64::MAX must be rejected",
693        );
694    }
695
696    #[rstest]
697    fn multiplication_matches_schoolbook_at_modulus_boundary() {
698        let value = Fp5::from_u64s_reduce([MODULUS - 1; 5]);
699        let product = value * value;
700        let square = value.square();
701        let expected = schoolbook_product(value, value);
702
703        assert_eq!(product, expected);
704        assert_eq!(square, expected);
705    }
706
707    proptest! {
708        /// `Fp5` addition is commutative.
709        #[rstest]
710        fn prop_add_commutative(a in arb_fp5(), b in arb_fp5()) {
711            prop_assert_eq!(a + b, b + a);
712        }
713
714        /// `Fp5` addition is associative.
715        #[rstest]
716        fn prop_add_associative(a in arb_fp5(), b in arb_fp5(), c in arb_fp5()) {
717            prop_assert_eq!((a + b) + c, a + (b + c));
718        }
719
720        /// Multiplication distributes over addition.
721        #[rstest]
722        fn prop_distributive(a in arb_fp5(), b in arb_fp5(), c in arb_fp5()) {
723            prop_assert_eq!(a * (b + c), a * b + a * c);
724        }
725
726        /// Multiplication is commutative.
727        #[rstest]
728        fn prop_mul_commutative(a in arb_fp5(), b in arb_fp5()) {
729            prop_assert_eq!(a * b, b * a);
730        }
731
732        /// Multiplication is associative.
733        #[rstest]
734        fn prop_mul_associative(a in arb_fp5(), b in arb_fp5(), c in arb_fp5()) {
735            prop_assert_eq!((a * b) * c, a * (b * c));
736        }
737
738        #[rstest]
739        fn prop_mul_matches_schoolbook(a in arb_fp5(), b in arb_fp5()) {
740            prop_assert_eq!(a * b, schoolbook_product(a, b));
741        }
742
743        /// `a + (-a) == 0`.
744        #[rstest]
745        fn prop_neg_round_trip(a in arb_fp5()) {
746            prop_assert_eq!(a + (-a), Fp5::ZERO);
747        }
748
749        /// `a - b == a + (-b)`.
750        #[rstest]
751        fn prop_sub_via_add_neg(a in arb_fp5(), b in arb_fp5()) {
752            prop_assert_eq!(a - b, a + (-b));
753        }
754
755        /// `(a + b) - b == a`.
756        #[rstest]
757        fn prop_sub_round_trip(a in arb_fp5(), b in arb_fp5()) {
758            prop_assert_eq!((a + b) - b, a);
759        }
760
761        /// Squaring matches self-multiplication.
762        #[rstest]
763        fn prop_square_matches_self_mul(a in arb_fp5()) {
764            prop_assert_eq!(a.square(), a * a);
765        }
766
767        /// `double` matches self addition.
768        #[rstest]
769        fn prop_double_matches_self_addition(a in arb_fp5()) {
770            prop_assert_eq!(a.double(), a + a);
771        }
772
773        /// `a * a.invert() == 1` for any non-zero element.
774        #[rstest]
775        fn prop_invert_round_trip(a in arb_fp5_nonzero()) {
776            prop_assert_eq!(a * a.invert(), Fp5::ONE);
777        }
778
779        /// `(a^2).sqrt()^2 == a^2`: sqrt of any known square round-trips.
780        #[rstest]
781        fn prop_sqrt_round_trip(a in arb_fp5()) {
782            let sq = a.square();
783            let s = sq.sqrt().expect("squares are quadratic residues");
784            prop_assert_eq!(s.square(), sq);
785        }
786
787        /// `canonical_sqrt(a^2)^2 == a^2`: the canonicalised root squares
788        /// back to the input. The result's `sgn0` is NOT asserted here:
789        /// when the root falls into the documented leading-zero wrinkle on
790        /// `sgn0` (both root and its negation report `true`), `canonical_sqrt`
791        /// returns the negated root which still reports `true`. That branch
792        /// has no observable effect on `Point::decode` per the doc on
793        /// `Fp5::sgn0`, and the byte-equality oracle vectors pin the wider
794        /// behaviour end-to-end.
795        #[rstest]
796        fn prop_canonical_sqrt_round_trip(a in arb_fp5_nonzero()) {
797            let sq = a.square();
798            let s = sq.canonical_sqrt().expect("squares are quadratic residues");
799            prop_assert_eq!(s.square(), sq);
800        }
801
802        /// `canonical_sqrt` is deterministic: invoking it twice on the same
803        /// input produces the same root.
804        #[rstest]
805        fn prop_canonical_sqrt_deterministic(a in arb_fp5_nonzero()) {
806            let sq = a.square();
807            prop_assert_eq!(sq.canonical_sqrt(), sq.canonical_sqrt());
808        }
809
810        /// The Lighter-style sign latch is anti-symmetric for any element
811        /// whose first coefficient is non-zero: exactly one of `x` and
812        /// `-x` reports `sgn0 == true`. Pins the latch contract on the
813        /// no-leading-zero branch documented at `Fp5::sgn0`. (The wrinkle
814        /// where `c[0] == 0` makes both `x` and `-x` report `true` is
815        /// excluded from this strategy by construction; the doc on
816        /// `Fp5::sgn0` notes the wrinkle has no observable effect on the
817        /// curve `decode` path that consumes this primitive.)
818        #[rstest]
819        fn prop_sgn0_negation_anti_symmetric(
820            a in arb_fp5_nonzero().prop_filter("c0 nonzero", |x| !x.0[0].is_zero()),
821        ) {
822            prop_assert_ne!(a.sgn0(), (-a).sgn0());
823        }
824
825        /// `Fp5` Legendre symbol is multiplicative: `legendre(a*b) ==
826        /// legendre(a) * legendre(b)` for non-zero operands.
827        #[rstest]
828        fn prop_legendre_multiplicative(a in arb_fp5_nonzero(), b in arb_fp5_nonzero()) {
829            let prod = a * b;
830            prop_assume!(!prod.is_zero());
831            prop_assert_eq!(prod.legendre(), a.legendre() * b.legendre());
832        }
833
834        /// Squares produce Legendre `+1`.
835        #[rstest]
836        fn prop_legendre_square_is_one(a in arb_fp5_nonzero()) {
837            prop_assert_eq!(a.square().legendre(), Fp::ONE);
838        }
839
840        /// `frobenius` applied five times is the identity (since `phi(x) = x^p`
841        /// and `Fp5` has order `p^5 - 1`, `phi^5 = id`).
842        #[rstest]
843        fn prop_frobenius_iter_five_is_identity(a in arb_fp5()) {
844            let phi5 = a.frobenius().frobenius().frobenius().frobenius().frobenius();
845            prop_assert_eq!(phi5, a);
846        }
847
848        /// Frobenius is a ring homomorphism over multiplication.
849        #[rstest]
850        fn prop_frobenius_multiplicative(a in arb_fp5(), b in arb_fp5()) {
851            prop_assert_eq!((a * b).frobenius(), a.frobenius() * b.frobenius());
852        }
853
854        /// `frobenius2` matches `frobenius` applied twice.
855        #[rstest]
856        fn prop_frobenius2_matches_double_frobenius(a in arb_fp5()) {
857            prop_assert_eq!(a.frobenius2(), a.frobenius().frobenius());
858        }
859
860        /// Canonical bytes round-trip.
861        #[rstest]
862        fn prop_le_bytes_round_trip(a in arb_fp5()) {
863            let bytes = a.to_le_bytes();
864            prop_assert_eq!(Fp5::try_from_le_bytes(bytes).unwrap(), a);
865        }
866
867        /// `ct_select` picks `a` for mask 0 and `b` for mask u64::MAX.
868        #[rstest]
869        fn prop_ct_select_picks_branch(a in arb_fp5(), b in arb_fp5()) {
870            prop_assert_eq!(Fp5::ct_select(0, a, b), a);
871            prop_assert_eq!(Fp5::ct_select(u64::MAX, a, b), b);
872        }
873
874        /// `ct_eq` agrees with `==`.
875        #[rstest]
876        fn prop_ct_eq_matches_partial_eq(a in arb_fp5(), b in arb_fp5()) {
877            let ct = a.ct_eq(b);
878            if a == b {
879                prop_assert_eq!(ct, u64::MAX);
880            } else {
881                prop_assert_eq!(ct, 0);
882            }
883        }
884    }
885
886    fn schoolbook_product(lhs: Fp5, rhs: Fp5) -> Fp5 {
887        let w = Fp::from_u64_reduce(W);
888        let a = &lhs.0;
889        let b = &rhs.0;
890        Fp5([
891            a[0] * b[0] + w * (a[1] * b[4] + a[2] * b[3] + a[3] * b[2] + a[4] * b[1]),
892            a[0] * b[1] + a[1] * b[0] + w * (a[2] * b[4] + a[3] * b[3] + a[4] * b[2]),
893            a[0] * b[2] + a[1] * b[1] + a[2] * b[0] + w * (a[3] * b[4] + a[4] * b[3]),
894            a[0] * b[3] + a[1] * b[2] + a[2] * b[1] + a[3] * b[0] + w * (a[4] * b[4]),
895            a[0] * b[4] + a[1] * b[3] + a[2] * b[2] + a[3] * b[1] + a[4] * b[0],
896        ])
897    }
898
899    #[rstest]
900    fn matches_go_reference_vectors() {
901        let suite: Vectors = serde_json::from_str(VECTORS_JSON).expect("parse vectors");
902        assert!(!suite.vectors.is_empty(), "vector file is empty");
903
904        for (i, v) in suite.vectors.iter().enumerate() {
905            let a = Fp5::try_from_le_bytes(decode_le40(&v.a))
906                .unwrap_or_else(|| panic!("vector {i}: decode a"));
907            let b = Fp5::try_from_le_bytes(decode_le40(&v.b))
908                .unwrap_or_else(|| panic!("vector {i}: decode b"));
909            let e = parse_u64(&v.e);
910
911            assert_eq!(
912                (a + b).to_le_bytes(),
913                decode_le40(&v.add),
914                "vector {i}: add"
915            );
916            assert_eq!(
917                (a - b).to_le_bytes(),
918                decode_le40(&v.sub),
919                "vector {i}: sub"
920            );
921            assert_eq!(
922                (a * b).to_le_bytes(),
923                decode_le40(&v.mul),
924                "vector {i}: mul"
925            );
926            assert_eq!((-a).to_le_bytes(), decode_le40(&v.neg_a), "vector {i}: neg");
927            assert_eq!(
928                a.invert().to_le_bytes(),
929                decode_le40(&v.inv_a),
930                "vector {i}: inv"
931            );
932            assert_eq!(
933                a.pow(e).to_le_bytes(),
934                decode_le40(&v.pow_a_e),
935                "vector {i}: pow"
936            );
937            assert_eq!(a == b, v.a_eq_b, "vector {i}: eq");
938        }
939    }
940}
nautilus_lighter/signing/field/quintic.rs

nautilus_lighter/signing/field/
quintic.rs
