Skip to main content

nautilus_lighter/signing/curve/
scalar.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//! Scalar field of the ECgFp5 curve.
17//!
18//! Operates modulo the prime group order `n`, a 319-bit prime stored as five
19//! 64-bit little-endian limbs in non-Montgomery form. Encoding/decoding and
20//! addition/subtraction work directly on the limbs; multiplication uses
21//! Montgomery form internally with the precomputed constants `R^2 mod n` and
22//! `-1/n[0] mod 2^64`.
23//!
24//! All arithmetic primitives execute as branch-free limb-wise sequences so
25//! timing reveals nothing about secret operands. The variable-time operations are
26//! confined to encode/decode-style boundaries (`from_le_bytes_reduce`) and the
27//! signed-window recoding used by the variable-time scalar multiplication.
28
29use core::ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign};
30
31use crate::signing::field::Fp5;
32
33/// Number of 64-bit limbs in a scalar.
34pub const LIMBS: usize = 5;
35
36/// Canonical 40-byte little-endian encoding length for a scalar.
37pub const SCALAR_BYTES: usize = LIMBS * 8;
38
39/// Group order `n` of the ECgFp5 curve, a 319-bit prime.
40///
41/// `n = 1067993516717146951041484916571792702745057740581727230159139685185762082554198619328292418486241`
42pub const ORDER: Scalar = Scalar([
43    0xE80F_D996_948B_FFE1,
44    0xE888_5C39_D724_A09C,
45    0x7FFF_FFE6_CFB8_0639,
46    0x7FFF_FFF1_0000_0016,
47    0x7FFF_FFFD_8000_0007,
48]);
49
50/// `-1 / n[0] mod 2^64`, the precomputed Montgomery reduction multiplier.
51const N0I: u64 = 0xD78B_EF72_057B_7BDF;
52
53/// `R^2 mod n` with `R = 2^320`. Multiplying by this lifts a value into
54/// Montgomery form via [`Scalar::monty_mul`].
55const R2: Scalar = Scalar([
56    0xA010_01DC_E33D_C739,
57    0x6C32_28D3_3F62_ACCF,
58    0xD1D7_96CC_91CF_8525,
59    0xAADF_FF5D_1574_C1D8,
60    0x4ACA_13B2_8CA2_51F5,
61]);
62
63/// A scalar in the ECgFp5 curve's scalar field, stored in non-Montgomery form
64/// as five 64-bit little-endian limbs.
65///
66/// Canonical instances (`< n`) round-trip through every public operation. The
67/// arithmetic primitives `add` / `sub` / `mul` require canonical inputs;
68/// `from_le_bytes_reduce` handles the wider input range produced by hashing.
69#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
70pub struct Scalar(pub [u64; LIMBS]);
71
72impl Scalar {
73    /// Additive identity.
74    pub const ZERO: Self = Self([0; LIMBS]);
75
76    /// Multiplicative identity.
77    pub const ONE: Self = Self([1, 0, 0, 0, 0]);
78
79    /// Build a scalar from five raw 64-bit limbs without any reduction.
80    ///
81    /// The caller is responsible for ensuring the value is canonical when it
82    /// will subsequently feed the modular `Add`, `Sub`, `Neg`, or `Mul`
83    /// operators.
84    #[inline]
85    #[must_use]
86    pub const fn from_limbs(limbs: [u64; LIMBS]) -> Self {
87        Self(limbs)
88    }
89
90    /// Return the underlying limbs in little-endian order.
91    #[inline]
92    #[must_use]
93    pub const fn to_limbs(self) -> [u64; LIMBS] {
94        self.0
95    }
96
97    /// Test whether this scalar is canonical (`self < n`).
98    #[must_use]
99    pub fn is_canonical(self) -> bool {
100        for i in (0..LIMBS).rev() {
101            if self.0[i] < ORDER.0[i] {
102                return true;
103            }
104
105            if self.0[i] > ORDER.0[i] {
106                return false;
107            }
108        }
109        false
110    }
111
112    /// Test whether the scalar is zero.
113    #[inline]
114    #[must_use]
115    pub const fn is_zero(self) -> bool {
116        let mut acc: u64 = 0;
117        let mut i = 0;
118
119        while i < LIMBS {
120            acc |= self.0[i];
121            i += 1;
122        }
123        acc == 0
124    }
125
126    /// Canonical 40-byte little-endian encoding (5 x 8-byte limbs).
127    #[must_use]
128    pub fn to_le_bytes(self) -> [u8; SCALAR_BYTES] {
129        let mut out = [0u8; SCALAR_BYTES];
130
131        for (i, limb) in self.0.iter().enumerate() {
132            out[i * 8..(i + 1) * 8].copy_from_slice(&limb.to_le_bytes());
133        }
134        out
135    }
136
137    /// Decode 40 little-endian bytes, reducing modulo `n` if the encoded value
138    /// exceeds the canonical range. Mirrors the upstream Lighter routine.
139    #[must_use]
140    pub fn from_le_bytes_reduce(bytes: [u8; SCALAR_BYTES]) -> Self {
141        let mut limbs = [0u64; LIMBS];
142
143        for (i, slot) in limbs.iter_mut().enumerate() {
144            let mut chunk = [0u8; 8];
145            chunk.copy_from_slice(&bytes[i * 8..(i + 1) * 8]);
146            *slot = u64::from_le_bytes(chunk);
147        }
148
149        let s = Self(limbs);
150        if s.is_canonical() {
151            s
152        } else {
153            // The encoded integer is at most `2^320 - 1 < 4 * n`, so at most
154            // two conditional subtractions land us in canonical range.
155            let (s1, b1) = s.sub_inner(ORDER);
156            let s_after1 = if b1 != 0 { s } else { s1 };
157            let (s2, b2) = s_after1.sub_inner(ORDER);
158            if b2 != 0 { s_after1 } else { s2 }
159        }
160    }
161
162    /// Branch-free constant-time select: returns `a0` when `c == 0` and `a1`
163    /// when `c == u64::MAX`.
164    #[inline]
165    #[must_use]
166    pub const fn select(c: u64, a0: Self, a1: Self) -> Self {
167        Self([
168            a0.0[0] ^ (c & (a0.0[0] ^ a1.0[0])),
169            a0.0[1] ^ (c & (a0.0[1] ^ a1.0[1])),
170            a0.0[2] ^ (c & (a0.0[2] ^ a1.0[2])),
171            a0.0[3] ^ (c & (a0.0[3] ^ a1.0[3])),
172            a0.0[4] ^ (c & (a0.0[4] ^ a1.0[4])),
173        ])
174    }
175
176    /// Raw 320-bit addition with no modular reduction.
177    #[inline]
178    #[must_use]
179    pub fn add_inner(self, rhs: Self) -> Self {
180        let mut r = [0u64; LIMBS];
181        let mut carry: u8 = 0;
182
183        for (i, slot) in r.iter_mut().enumerate() {
184            let (t1, c1) = self.0[i].overflowing_add(rhs.0[i]);
185            let (t2, c2) = t1.overflowing_add(u64::from(carry));
186            *slot = t2;
187            carry = u8::from(c1) | u8::from(c2);
188        }
189        Self(r)
190    }
191
192    /// Raw 320-bit subtraction with no modular reduction. Returns the
193    /// difference and an `0` / `u64::MAX` mask indicating whether the operation
194    /// borrowed beyond the top limb.
195    #[inline]
196    #[must_use]
197    pub fn sub_inner(self, rhs: Self) -> (Self, u64) {
198        let mut r = [0u64; LIMBS];
199        let mut borrow: u8 = 0;
200
201        for (i, slot) in r.iter_mut().enumerate() {
202            let (t1, b1) = self.0[i].overflowing_sub(rhs.0[i]);
203            let (t2, b2) = t1.overflowing_sub(u64::from(borrow));
204            *slot = t2;
205            borrow = u8::from(b1) | u8::from(b2);
206        }
207        let mask = if borrow != 0 { u64::MAX } else { 0 };
208        (Self(r), mask)
209    }
210
211    /// Montgomery multiplication `(self * rhs) / 2^320 mod n`.
212    ///
213    /// `self` MUST be canonical. `rhs` may exceed `n` provided it fits in 320
214    /// bits, mirroring the upstream behavior used to lift values into
215    /// Montgomery form via the `R2` constant.
216    #[must_use]
217    pub fn monty_mul(self, rhs: Self) -> Self {
218        debug_assert!(self.is_canonical(), "Scalar::monty_mul: lhs not canonical",);
219
220        let mut r = [0u64; LIMBS];
221        for m in rhs.0 {
222            let f = (self.0[0].wrapping_mul(m).wrapping_add(r[0])).wrapping_mul(N0I);
223
224            let mut cc1: u64 = 0;
225            let mut cc2: u64 = 0;
226
227            for j in 0..LIMBS {
228                let prod = u128::from(self.0[j]) * u128::from(m);
229                let s1 = prod + u128::from(r[j]) + u128::from(cc1);
230                cc1 = (s1 >> 64) as u64;
231                let s1_lo = s1 as u64;
232
233                let prod_n = u128::from(f) * u128::from(ORDER.0[j]);
234                let s2 = prod_n + u128::from(s1_lo) + u128::from(cc2);
235                cc2 = (s2 >> 64) as u64;
236                let s2_lo = s2 as u64;
237
238                if j > 0 {
239                    r[j - 1] = s2_lo;
240                }
241            }
242            r[LIMBS - 1] = cc1.wrapping_add(cc2);
243        }
244
245        let r0 = Self(r);
246        let (r1, c) = r0.sub_inner(ORDER);
247        Self::select(c, r1, r0)
248    }
249
250    /// Build a scalar from an `Fp5` element via reduction modulo `n`.
251    ///
252    /// Concatenates the five canonical 64-bit limbs of `e` into a 320-bit
253    /// little-endian integer and reduces, matching the upstream behavior of
254    /// `FromGfp5`. Used by the Schnorr binding to derive a scalar from a
255    /// Poseidon2 digest.
256    #[must_use]
257    pub fn from_fp5(e: Fp5) -> Self {
258        let mut bytes = [0u8; SCALAR_BYTES];
259        let encoded = e.to_le_bytes();
260        bytes.copy_from_slice(&encoded);
261        Self::from_le_bytes_reduce(bytes)
262    }
263
264    /// Split the canonical scalar value into 80 little-endian 4-bit nibbles.
265    ///
266    /// Iteration order is least-significant nibble first.
267    #[must_use]
268    pub fn split_to_4_bit_limbs(self) -> [u8; 80] {
269        let mut out = [0u8; 80];
270
271        for i in 0..LIMBS {
272            for j in 0..16 {
273                out[i * 16 + j] = ((self.0[i] >> (j * 4)) & 0xF) as u8;
274            }
275        }
276        out
277    }
278
279    /// Recode the scalar into signed digits for a width-`w` window.
280    ///
281    /// `ss` is filled with `(2^w + 1)`-range signed values (lying in
282    /// `-(2^(w-1)) ..= 2^(w-1)` after carry propagation) so that
283    /// `sum(ss[i] * 2^(w*i)) == self mod 2^(w * len)`. When `w * len >= 320`,
284    /// the recoding spans the entire scalar and the top digit is non-negative.
285    ///
286    /// `w` MUST satisfy `2 <= w <= 10`. This recoding is variable-time and is
287    /// only suitable for non-secret window selection.
288    pub fn recode_signed(self, ss: &mut [i32], w: u32) {
289        recode_signed_from_limbs(&self.0, ss, w);
290    }
291}
292
293/// Recode an arbitrary little-endian limb sequence into signed window digits.
294/// Exposed mainly for testing parity with the upstream code.
295pub fn recode_signed_from_limbs(limbs: &[u64], ss: &mut [i32], w: u32) {
296    debug_assert!((2..=10).contains(&w), "window width must be in 2..=10");
297
298    let mw = (1u32 << w) - 1;
299    let hw = 1u32 << (w - 1);
300
301    let mut acc: u64 = 0;
302    let mut acc_len: i32 = 0;
303    let mut j: usize = 0;
304    let mut cc: u32 = 0;
305    let w_i32 = w as i32;
306
307    for slot in ss.iter_mut() {
308        let bb: u32 = if acc_len < w_i32 {
309            if j < limbs.len() {
310                let nl = limbs[j];
311                j += 1;
312                let bits = ((acc | (nl << acc_len)) as u32) & mw;
313                acc = nl >> (w_i32 - acc_len);
314                acc_len += 64 - w_i32;
315                bits
316            } else {
317                let bits = (acc as u32) & mw;
318                acc = 0;
319                acc_len += 64 - w_i32;
320                bits
321            }
322        } else {
323            let bits = (acc as u32) & mw;
324            acc_len -= w_i32;
325            acc >>= w;
326            bits
327        };
328
329        let sum = bb.wrapping_add(cc);
330        cc = (hw.wrapping_sub(sum)) >> 31;
331        *slot = (sum as i32) - ((cc << w) as i32);
332    }
333}
334
335impl Default for Scalar {
336    #[inline]
337    fn default() -> Self {
338        Self::ZERO
339    }
340}
341
342impl Add for Scalar {
343    type Output = Self;
344
345    fn add(self, rhs: Self) -> Self {
346        debug_assert!(self.is_canonical(), "Scalar add: lhs not canonical");
347        debug_assert!(rhs.is_canonical(), "Scalar add: rhs not canonical");
348
349        let r0 = self.add_inner(rhs);
350        let (r1, c) = r0.sub_inner(ORDER);
351        Self::select(c, r1, r0)
352    }
353}
354
355impl AddAssign for Scalar {
356    fn add_assign(&mut self, rhs: Self) {
357        *self = *self + rhs;
358    }
359}
360
361impl Sub for Scalar {
362    type Output = Self;
363
364    fn sub(self, rhs: Self) -> Self {
365        debug_assert!(self.is_canonical(), "Scalar sub: lhs not canonical");
366        debug_assert!(rhs.is_canonical(), "Scalar sub: rhs not canonical");
367
368        let (r0, c) = self.sub_inner(rhs);
369        let r1 = r0.add_inner(ORDER);
370        Self::select(c, r0, r1)
371    }
372}
373
374impl SubAssign for Scalar {
375    fn sub_assign(&mut self, rhs: Self) {
376        *self = *self - rhs;
377    }
378}
379
380impl Neg for Scalar {
381    type Output = Self;
382
383    fn neg(self) -> Self {
384        debug_assert!(self.is_canonical(), "Scalar neg: input not canonical");
385        Self::ZERO - self
386    }
387}
388
389impl Mul for Scalar {
390    type Output = Self;
391
392    fn mul(self, rhs: Self) -> Self {
393        debug_assert!(self.is_canonical(), "Scalar mul: lhs not canonical");
394        debug_assert!(rhs.is_canonical(), "Scalar mul: rhs not canonical");
395
396        self.monty_mul(R2).monty_mul(rhs)
397    }
398}
399
400impl MulAssign for Scalar {
401    fn mul_assign(&mut self, rhs: Self) {
402        *self = *self * rhs;
403    }
404}
405
406#[cfg(test)]
407mod tests {
408    use proptest::prelude::*;
409    use rstest::rstest;
410
411    use super::*;
412    use crate::signing::fixtures::{arb_scalar, arb_scalar_nonzero};
413
414    #[rstest]
415    fn order_round_trips_through_le_bytes() {
416        let bytes = ORDER.to_le_bytes();
417        // ORDER itself is not canonical (`< n` is false at equality), but the
418        // round-trip-with-reduce should normalize it to zero.
419        let s = Scalar::from_le_bytes_reduce(bytes);
420        assert_eq!(s, Scalar::ZERO);
421    }
422
423    #[rstest]
424    fn add_inner_carries_through_top_limb() {
425        let scalar1 = Scalar([
426            0xFFFF_FFFF_FFFF_FFFF,
427            0xFFFF_FFFF_FFFF_FFFF,
428            0xFFFF_FFFF_FFFF_FFFF,
429            0xFFFF_FFFF_FFFF_FFFF,
430            0xFFFF_FFFF_FFFF_FFFF,
431        ]);
432        let scalar2 = Scalar([
433            0x00FF_FFFF_FFFE_EFFF,
434            12_312_321_312,
435            0xFFFF_FFFF_FFFF_FFFF,
436            0x00FF_FFFF_FACD_FFFF,
437            0xBCAF_FFFF_FFFF_FFFF,
438        ]);
439        let expected = Scalar([
440            0x00FF_FFFF_FFFE_EFFE,
441            0x0000_0002_DDDF_1D20,
442            0xFFFF_FFFF_FFFF_FFFF,
443            0x00FF_FFFF_FACD_FFFF,
444            0xBCAF_FFFF_FFFF_FFFF,
445        ]);
446        assert_eq!(scalar1.add_inner(scalar2), expected);
447    }
448
449    #[rstest]
450    fn sub_inner_signals_borrow() {
451        let scalar1 = Scalar::ZERO;
452        let scalar2 = Scalar([u64::MAX; 5]);
453        let (result, borrow) = scalar1.sub_inner(scalar2);
454        assert_eq!(result, Scalar([1, 0, 0, 0, 0]));
455        assert_eq!(borrow, u64::MAX);
456    }
457
458    #[rstest]
459    fn modular_sub_wraps_through_order() {
460        let scalar1 = Scalar([1, 2, 0, 0, 0]);
461        let scalar2 = Scalar([
462            0xFFFF_FFFF_FFFF_FFFF,
463            0xFFFF_FFFF_FFFF_FFFF,
464            0xFFFF_FFFF_FFFF_FFFF,
465            0xFFFF_FFFF_FFFF_FFFF,
466            0x0FFF_FFFF_FFFF_FFFF,
467        ]);
468        assert!(scalar2.is_canonical());
469
470        let result = scalar1 - scalar2;
471        let expected = Scalar([
472            0xE80F_D996_948B_FFE3,
473            0xE888_5C39_D724_A09E,
474            0x7FFF_FFE6_CFB8_0639,
475            0x7FFF_FFF1_0000_0016,
476            8_070_450_521_510_510_599,
477        ]);
478        assert_eq!(result, expected);
479    }
480
481    #[rstest]
482    fn select_picks_branch_by_mask() {
483        let a0 = Scalar([1, 2, 3, 4, 5]);
484        let a1 = Scalar([
485            0xFFFF_FFFF_FFFF_FFFF,
486            0xFFFF_FFFF_FFFF_FFFE,
487            0xFFFF_FFFF_FFFF_FFFD,
488            0xFFFF_FFFF_FFFF_FFFC,
489            0xFFFF_FFFF_FFFF_FFFB,
490        ]);
491        assert_eq!(Scalar::select(0, a0, a1), a0);
492        assert_eq!(Scalar::select(u64::MAX, a0, a1), a1);
493    }
494
495    #[rstest]
496    fn one_is_multiplicative_identity() {
497        let s = Scalar([
498            0x1234_5678_90AB_CDEF,
499            0xFEDC_BA98_7654_3210,
500            0x0123_4567_89AB_CDEF,
501            0xFEDC_BA98_7654_3210,
502            0x1234_5678_90AB_CDEF,
503        ]);
504        assert!(s.is_canonical());
505        assert_eq!(s * Scalar::ONE, s);
506        assert_eq!(Scalar::ONE * s, s);
507    }
508
509    #[rstest]
510    fn neg_is_additive_inverse() {
511        let s = Scalar([7, 11, 13, 17, 19]);
512        let zero = s + (-s);
513        assert_eq!(zero, Scalar::ZERO);
514    }
515
516    #[rstest]
517    fn split_to_4_bit_limbs_matches_reference_vector() {
518        let scalar = Scalar([
519            6_950_590_877_883_398_434,
520            17_178_336_263_794_770_543,
521            11_012_823_478_139_181_320,
522            16_445_091_359_523_510_936,
523            5_882_925_226_143_600_273,
524        ]);
525
526        let limbs = scalar.split_to_4_bit_limbs();
527        // Spot-check a handful of nibbles against the upstream Go vector.
528        assert_eq!(limbs[0], 2);
529        assert_eq!(limbs[1], 2);
530        assert_eq!(limbs[2], 9);
531        assert_eq!(limbs[16], 15);
532        assert_eq!(limbs[39], 13);
533        assert_eq!(limbs[79], 5);
534
535        // Stronger: the nibble sequence reconstructs the original limbs.
536        assert_eq!(reconstruct_from_4_bit_nibbles(limbs), scalar.0);
537    }
538
539    /// Reconstruct a 5-limb scalar by repacking 80 little-endian 4-bit nibbles
540    /// back into 5 u64s.
541    fn reconstruct_from_4_bit_nibbles(nibbles: [u8; 80]) -> [u64; LIMBS] {
542        let mut out = [0u64; LIMBS];
543        for (i, slot) in out.iter_mut().enumerate() {
544            let mut v: u64 = 0;
545            for j in 0..16 {
546                v |= u64::from(nibbles[i * 16 + j]) << (j * 4);
547            }
548            *slot = v;
549        }
550        out
551    }
552
553    /// Reconstruct the 5-limb scalar value from its signed-window digits via
554    /// `sum(ss[i] * 2^(w*i)) mod 2^320`. Used in tests to pin the recoding
555    /// spec.
556    fn reconstruct_from_signed_digits(ss: &[i32], w: u32) -> [u64; LIMBS] {
557        // 5 + 2 buffer limbs to absorb intermediate overflow before
558        // propagating carries.
559        let mut limbs = [0i128; LIMBS + 2];
560
561        for (i, &d) in ss.iter().enumerate() {
562            let shift = (i as u64) * u64::from(w);
563            if shift >= ((LIMBS + 2) as u64) * 64 {
564                continue;
565            }
566            let limb_idx = (shift / 64) as usize;
567            let bit_off = (shift % 64) as u32;
568            // Each digit lies in roughly `-(2^(w-1)+1) ..= 2^(w-1)+1` and
569            // `bit_off <= 63`, so the shifted value fits in i128.
570            let shifted = (d as i128) << bit_off;
571            let lo_mask: i128 = (1i128 << 64) - 1;
572            limbs[limb_idx] += shifted & lo_mask;
573            if limb_idx + 1 < limbs.len() {
574                limbs[limb_idx + 1] += shifted >> 64;
575            }
576        }
577        let mut out = [0u64; LIMBS];
578        let mut carry: i128 = 0;
579        for (i, slot) in out.iter_mut().enumerate() {
580            let v = limbs[i] + carry;
581            *slot = v as u64;
582            carry = v >> 64;
583        }
584        out
585    }
586
587    #[rstest]
588    fn recode_signed_top_digit_is_nonnegative() {
589        // Using the example from the upstream test, the top digit at index 32
590        // (5-bit window over 5 limbs) is `-1` after carry propagation. The
591        // 66-slot buffer covers the full 320-bit scalar (`64 * 5 = 320`) with
592        // two slack slots so the reconstruction round-trip below has room for
593        // any trailing carry.
594        use crate::signing::field::MODULUS;
595
596        let mut ss = [0i32; 66];
597        let scalar = Scalar([
598            MODULUS - 1,
599            MODULUS - 2,
600            MODULUS - 3,
601            0xFFFF_FFFF_FFFF_FFFF,
602            MODULUS - 5,
603        ]);
604        scalar.recode_signed(&mut ss, 5);
605
606        assert_eq!(ss[6], -4);
607        assert_eq!(ss[19], -2);
608        assert_eq!(ss[25], -8);
609        assert_eq!(ss[32], -1);
610
611        // Stronger: the recoded digits reconstruct the original limbs via
612        // `sum(ss[i] * 2^(w*i)) mod 2^320`.
613        assert_eq!(reconstruct_from_signed_digits(&ss, 5), scalar.0);
614    }
615
616    proptest! {
617        /// Modular addition is commutative.
618        #[rstest]
619        fn prop_add_commutative(a in arb_scalar(), b in arb_scalar()) {
620            prop_assert_eq!(a + b, b + a);
621        }
622
623        /// Modular addition is associative.
624        #[rstest]
625        fn prop_add_associative(a in arb_scalar(), b in arb_scalar(), c in arb_scalar()) {
626            prop_assert_eq!((a + b) + c, a + (b + c));
627        }
628
629        /// `a + (-a) == 0`.
630        #[rstest]
631        fn prop_neg_inverse(a in arb_scalar()) {
632            prop_assert_eq!(a + (-a), Scalar::ZERO);
633        }
634
635        /// `(a + b) - b == a`.
636        #[rstest]
637        fn prop_sub_round_trip(a in arb_scalar(), b in arb_scalar()) {
638            prop_assert_eq!((a + b) - b, a);
639        }
640
641        /// `a - b == a + (-b)`.
642        #[rstest]
643        fn prop_sub_via_add_neg(a in arb_scalar(), b in arb_scalar()) {
644            prop_assert_eq!(a - b, a + (-b));
645        }
646
647        /// Modular multiplication is commutative.
648        #[rstest]
649        fn prop_mul_commutative(a in arb_scalar(), b in arb_scalar()) {
650            prop_assert_eq!(a * b, b * a);
651        }
652
653        /// Modular multiplication is associative.
654        #[rstest]
655        fn prop_mul_associative(a in arb_scalar(), b in arb_scalar(), c in arb_scalar()) {
656            prop_assert_eq!((a * b) * c, a * (b * c));
657        }
658
659        /// Multiplication distributes over addition.
660        #[rstest]
661        fn prop_distributive(a in arb_scalar(), b in arb_scalar(), c in arb_scalar()) {
662            prop_assert_eq!(a * (b + c), a * b + a * c);
663        }
664
665        /// `Scalar::ONE` is the multiplicative identity.
666        #[rstest]
667        fn prop_one_is_identity(a in arb_scalar()) {
668            prop_assert_eq!(a * Scalar::ONE, a);
669            prop_assert_eq!(Scalar::ONE * a, a);
670        }
671
672        /// `Scalar::ZERO` annihilates multiplication.
673        #[rstest]
674        fn prop_zero_annihilates(a in arb_scalar()) {
675            prop_assert_eq!(a * Scalar::ZERO, Scalar::ZERO);
676            prop_assert_eq!(Scalar::ZERO * a, Scalar::ZERO);
677        }
678
679        /// `from_le_bytes_reduce(s.to_le_bytes()) == s` for any canonical
680        /// scalar (idempotency under round-trip).
681        #[rstest]
682        fn prop_from_le_bytes_reduce_idempotent(s in arb_scalar()) {
683            prop_assert_eq!(Scalar::from_le_bytes_reduce(s.to_le_bytes()), s);
684        }
685
686        /// Decoding any 40-byte sequence produces a canonical scalar.
687        #[rstest]
688        fn prop_from_le_bytes_reduce_yields_canonical(bytes in any::<[u8; SCALAR_BYTES]>()) {
689            prop_assert!(Scalar::from_le_bytes_reduce(bytes).is_canonical());
690        }
691
692        /// `is_canonical` matches the hand-rolled limb compare against ORDER.
693        #[rstest]
694        fn prop_is_canonical_matches_lex_compare(s in arb_scalar()) {
695            // Canonical iff `s < ORDER` lex-wise on the limb sequence.
696            let mut expected = false;
697
698            for i in (0..LIMBS).rev() {
699                if s.0[i] < ORDER.0[i] {
700                    expected = true;
701                    break;
702                }
703
704                if s.0[i] > ORDER.0[i] {
705                    expected = false;
706                    break;
707                }
708            }
709            prop_assert_eq!(s.is_canonical(), expected);
710        }
711
712        /// Scalar `select` picks branch by mask.
713        #[rstest]
714        fn prop_select_picks_branch(a in arb_scalar(), b in arb_scalar()) {
715            prop_assert_eq!(Scalar::select(0, a, b), a);
716            prop_assert_eq!(Scalar::select(u64::MAX, a, b), b);
717        }
718
719        /// `recode_signed` reconstructs the canonical 5-limb value via
720        /// `sum(ss[i] * 2^(w*i)) mod 2^320` for every supported window width.
721        #[rstest]
722        fn prop_recode_signed_reconstructs(s in arb_scalar(), w in 2u32..=10) {
723            // 320 bits divided by `w`, rounded up, plus 2 slack slots so the
724            // final carry has somewhere to land regardless of window width.
725            let len = (320usize.div_ceil(w as usize)) + 2;
726            let mut ss = vec![0i32; len];
727            s.recode_signed(&mut ss, w);
728            prop_assert_eq!(reconstruct_from_signed_digits(&ss, w), s.0);
729
730            // Each digit must lie in the signed window range.
731            let bound: i32 = 1 << (w - 1);
732
733            for (i, &d) in ss.iter().enumerate() {
734                prop_assert!(
735                    d >= -bound && d <= bound,
736                    "digit {d} at index {i} outside [-{bound}, {bound}]",
737                );
738            }
739        }
740
741        /// `split_to_4_bit_limbs` and `reconstruct_from_4_bit_nibbles` are
742        /// inverses for any canonical scalar.
743        #[rstest]
744        fn prop_split_to_4_bit_limbs_round_trip(s in arb_scalar()) {
745            prop_assert_eq!(reconstruct_from_4_bit_nibbles(s.split_to_4_bit_limbs()), s.0);
746        }
747
748        /// Every 4-bit nibble lies in `0..=15` for any scalar input.
749        #[rstest]
750        fn prop_split_to_4_bit_limbs_in_range(s in arb_scalar()) {
751            for &nibble in &s.split_to_4_bit_limbs() {
752                prop_assert!(nibble <= 15);
753            }
754        }
755    }
756
757    // `arb_scalar_nonzero` corollary: doubling a non-zero scalar lands on
758    // `2 * s mod n`. Kept in its own block so consumers that import only
759    // `arb_scalar` upstream don't pull the `nonzero` filter unnecessarily.
760    proptest! {
761        #[rstest]
762        fn prop_double_via_add(s in arb_scalar_nonzero()) {
763            prop_assert_eq!(s + s, s * Scalar::from_limbs([2, 0, 0, 0, 0]));
764        }
765    }
766}