primitives/algebra/field/binary/
gf2_ext.rs

1use core::iter::{Product, Sum};
2use std::{
3    cmp::Ordering,
4    fmt::Debug,
5    hash::{Hash, Hasher},
6    marker::PhantomData,
7    mem::MaybeUninit,
8    ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
9    str,
10};
11
12use derive_more::{AsMut, AsRef};
13use ff::Field;
14use hybrid_array::{Array, ArraySize, AssocArraySize};
15use itertools::{izip, Itertools};
16use itybity::ToBits;
17use num_traits::{One, Zero};
18use rand::RngCore;
19use serde::{Deserialize, Serialize};
20use serde_with::serde_as;
21use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};
22use typenum::{Prod, Unsigned, U64, U8};
23
24use crate::{
25    algebra::{
26        field::{
27            binary::Gf2,
28            exponentiation::{pow2_minus_1, pow2_pow},
29            FieldExtension,
30        },
31        ops::{AccReduce, DefaultDotProduct, DotProduct, IntoWide, MulAccReduce, ReduceWide},
32        uniform_bytes::FromUniformBytes,
33    },
34    errors::PrimitiveError,
35    izip_eq,
36    random::{CryptoRngCore, Random},
37    types::{HeapArray, Positive},
38    utils::{codec::InPlaceCodec, IntoExactSizeIterator},
39};
40
41#[serde_as]
42#[derive(Clone, Copy, Debug, Eq, AsRef, AsMut, Serialize, Deserialize)]
43#[repr(transparent)]
44pub struct Gf2Ext<P: Gf2ExtParams, const LIMBS: usize> {
45    #[serde_as(as = "[_; LIMBS]")]
46    pub(crate) data: [u64; LIMBS],
47    _id: PhantomData<P>,
48}
49
50impl<P: Gf2ExtParams, const LIMBS: usize> AsRef<[u8]> for Gf2Ext<P, LIMBS> {
51    fn as_ref(&self) -> &[u8] {
52        // SAFETY: This is safe because:
53        // 1. We're only reading the bytes
54        // 2. The memory layout of [u64; LIMBS] is well-defined
55        // 3. The slice length is exactly LIMBS * 8 bytes
56        unsafe {
57            std::slice::from_raw_parts(
58                self.data.as_ptr() as *const u8,
59                LIMBS * std::mem::size_of::<u64>(),
60            )
61        }
62    }
63}
64
65impl<P: Gf2ExtParams, const LIMBS: usize> AsMut<[u8]> for Gf2Ext<P, LIMBS> {
66    fn as_mut(&mut self) -> &mut [u8] {
67        // SAFETY: This is safe because:
68        // 1. We have exclusive access to the bytes
69        // 2. The memory layout of [u64; LIMBS] is well-defined
70        // 3. The slice length is exactly LIMBS * 8 bytes
71        unsafe {
72            std::slice::from_raw_parts_mut(
73                self.data.as_mut_ptr() as *mut u8,
74                LIMBS * std::mem::size_of::<u64>(),
75            )
76        }
77    }
78}
79
80impl<P: Gf2ExtParams, const LIMBS: usize> PartialEq<Self> for Gf2Ext<P, LIMBS> {
81    fn eq(&self, other: &Self) -> bool {
82        self.cmp(other) == Ordering::Equal
83    }
84}
85
86impl<P: Gf2ExtParams, const LIMBS: usize> PartialOrd<Self> for Gf2Ext<P, LIMBS> {
87    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
88        Some(self.cmp(other))
89    }
90}
91
92impl<P: Gf2ExtParams, const LIMBS: usize> Ord for Gf2Ext<P, LIMBS> {
93    fn cmp(&self, other: &Self) -> Ordering {
94        self.data.cmp(&other.data)
95    }
96}
97
98impl<P: Gf2ExtParams, const LIMBS: usize> Hash for Gf2Ext<P, LIMBS> {
99    fn hash<H: Hasher>(&self, state: &mut H) {
100        let bytes: &[u8] = self.as_ref();
101        bytes.iter().for_each(|x| {
102            x.hash(state);
103        });
104    }
105}
106
107// Datatype which can store a dot product result without modulus reduction
108#[derive(Clone, Copy)]
109pub struct Gf2LimbsWide<const LIMBS: usize> {
110    pub(crate) low: [u64; LIMBS],
111    pub(crate) high: [u64; LIMBS],
112}
113
114pub trait Gf2ExtParams: Copy + Debug + Eq + Sync + Send + Unpin + 'static {
115    /// The extension degree, a multiple of 64
116    type Degree: ArraySize + Positive;
117
118    /// Number of bytes needed for the extension, a multiple of 8
119    type Bytes: ArraySize + Positive;
120    //  Modulus polynomial non-zero coefficients (x^0 is not included) positions
121    const POLY_MOD_ONES: &[usize];
122}
123
124impl<P: Gf2ExtParams, const LIMBS: usize> Gf2Ext<P, LIMBS> {
125    pub const fn new(data: [u64; LIMBS]) -> Self {
126        Self {
127            data,
128            _id: PhantomData,
129        }
130    }
131
132    const ZERO: Self = Self::new([0u64; LIMBS]);
133    const ONE: Self = Self::new({
134        let mut tmp = [0u64; LIMBS];
135        tmp[0] = 1;
136        tmp
137    });
138}
139
140impl<P: Gf2ExtParams, const LIMBS: usize> Gf2Ext<P, LIMBS> {
141    pub fn as_mut_ne_bytes_slice(&mut self) -> &mut [u8] {
142        bytemuck::bytes_of_mut(&mut self.data)
143    }
144
145    pub fn as_ne_bytes_slice(&self) -> &[u8] {
146        bytemuck::bytes_of(&self.data)
147    }
148
149    pub fn from_limbs(val: [u64; LIMBS]) -> Self {
150        Self::new(val)
151    }
152
153    pub fn from_u64(val: u64) -> Self {
154        let mut tmp = [0u64; LIMBS];
155        tmp[0] = val;
156        Self::from_limbs(tmp)
157    }
158
159    pub fn from_u128(val: u128) -> Self {
160        let mut tmp = [0u64; LIMBS];
161        tmp[0] = val as u64;
162        tmp[1] = (val >> 64) as u64;
163        Self::from_limbs(tmp)
164    }
165}
166
167impl<P: Gf2ExtParams, const LIMBS: usize> Default for Gf2Ext<P, LIMBS> {
168    fn default() -> Self {
169        Self::ZERO
170    }
171}
172
173impl<const LIMBS: usize> Default for Gf2LimbsWide<LIMBS> {
174    fn default() -> Self {
175        Self {
176            low: [0u64; LIMBS],
177            high: [0u64; LIMBS],
178        }
179    }
180}
181
182// === Conversion traits
183
184impl<P: Gf2ExtParams, const LIMBS: usize> From<bool> for Gf2Ext<P, LIMBS> {
185    #[inline]
186    fn from(value: bool) -> Self {
187        Self::from_u64(value as u64)
188    }
189}
190
191impl<P: Gf2ExtParams, const LIMBS: usize> From<u8> for Gf2Ext<P, LIMBS> {
192    #[inline]
193    fn from(value: u8) -> Self {
194        Self::from_u64(value as u64)
195    }
196}
197
198impl<P: Gf2ExtParams, const LIMBS: usize> From<u16> for Gf2Ext<P, LIMBS> {
199    #[inline]
200    fn from(value: u16) -> Self {
201        Self::from_u64(value as u64)
202    }
203}
204
205impl<P: Gf2ExtParams, const LIMBS: usize> From<u32> for Gf2Ext<P, LIMBS> {
206    #[inline]
207    fn from(value: u32) -> Self {
208        Self::from_u64(value as u64)
209    }
210}
211
212impl<P: Gf2ExtParams, const LIMBS: usize> From<u64> for Gf2Ext<P, LIMBS> {
213    #[inline]
214    fn from(value: u64) -> Self {
215        Self::from_u64(value)
216    }
217}
218
219impl<P: Gf2ExtParams, const LIMBS: usize> From<u128> for Gf2Ext<P, LIMBS> {
220    #[inline]
221    fn from(value: u128) -> Self {
222        Self::from_u128(value)
223    }
224}
225
226// === Implementation of Field trait methods
227
228impl<P: Gf2ExtParams, const LIMBS: usize> Gf2Ext<P, LIMBS> {
229    /// The extension degree k in GF(2^k).
230    const DEGREE_BITS: u32 = (LIMBS * 64) as u32;
231}
232
233/// Spreads the 32 bits of `x` into the even bit positions of a `u64` (a zero between each input
234/// bit) — the square of a GF(2) polynomial half-word, since char-2 squaring has no cross terms.
235#[inline]
236fn spread_bits(x: u32) -> u64 {
237    let mut x = u64::from(x);
238    x = (x | (x << 16)) & 0x0000_FFFF_0000_FFFF;
239    x = (x | (x << 8)) & 0x00FF_00FF_00FF_00FF;
240    x = (x | (x << 4)) & 0x0F0F_0F0F_0F0F_0F0F;
241    x = (x | (x << 2)) & 0x3333_3333_3333_3333;
242    x = (x | (x << 1)) & 0x5555_5555_5555_5555;
243    x
244}
245
246impl<P: Gf2ExtParams, const LIMBS: usize> Field for Gf2Ext<P, LIMBS>
247where
248    Gf2Ext<P, LIMBS>: MulWide<Output = Gf2LimbsWide<LIMBS>>,
249{
250    const ZERO: Self = Self::ZERO;
251    const ONE: Self = Self::ONE;
252
253    fn random(mut rng: impl RngCore) -> Self {
254        let mut tmp = Self::default();
255        rng.fill_bytes(tmp.as_mut_ne_bytes_slice());
256        tmp
257    }
258
259    fn square(&self) -> Self {
260        // Char-2 squaring has no cross terms: spread each limb's bits with interleaved zeros and
261        // reduce, instead of a full carry-less multiply. This is the hot operation of the
262        // `invert`/`sqrt` addition chains (~k sequential squarings each).
263        let mut wide = Gf2LimbsWide {
264            low: [0u64; LIMBS],
265            high: [0u64; LIMBS],
266        };
267        for (i, limb) in self.data.iter().enumerate() {
268            let (lo_half, hi_half) = (spread_bits(*limb as u32), spread_bits((*limb >> 32) as u32));
269            // Input limb i occupies wide limbs 2i and 2i+1.
270            for (offset, word) in [(0, lo_half), (1, hi_half)] {
271                let k = 2 * i + offset;
272                if k < LIMBS {
273                    wide.low[k] = word;
274                } else {
275                    wide.high[k - LIMBS] = word;
276                }
277            }
278        }
279        Self::reduce_mod_order(wide)
280    }
281
282    fn double(&self) -> Self {
283        self + self
284    }
285
286    fn invert(&self) -> CtOption<Self> {
287        // Fermat: x⁻¹ = x^(2^k − 2) = (x^(2^(k−1) − 1))², with k the extension degree.
288        let root = pow2_minus_1(*self, Self::DEGREE_BITS - 1);
289        CtOption::new(root.square(), !self.ct_eq(&Self::ZERO))
290    }
291
292    fn sqrt_ratio(num: &Self, div: &Self) -> (Choice, Self) {
293        // Char 2: squaring is a bijection, so every element has a unique square root and the
294        // "nonsquare" branch of the ff contract is unreachable. Per that contract, the result is
295        // valid unless `div` is zero while `num` is not.
296        //
297        // sqrt(num/div) = sqrt(num) · sqrt(div⁻¹), and sqrt(div⁻¹) = div^(2^(k−1) − 1): one
298        // addition chain instead of a full inversion followed by a second exponentiation.
299        let is_valid = !div.ct_eq(&Self::ZERO) | num.ct_eq(&Self::ZERO);
300        let root =
301            pow2_pow(*num, Self::DEGREE_BITS - 1) * pow2_minus_1(*div, Self::DEGREE_BITS - 1);
302        (is_valid, root)
303    }
304
305    fn sqrt(&self) -> CtOption<Self> {
306        // Char 2: sqrt(x) = x^(2^(k−1)) (inverse Frobenius); every element is a square.
307        CtOption::new(pow2_pow(*self, Self::DEGREE_BITS - 1), Choice::from(1))
308    }
309}
310
311impl<P: Gf2ExtParams, const LIMBS: usize> ConditionallySelectable for Gf2Ext<P, LIMBS> {
312    #[inline]
313    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
314        Self::from_limbs(std::array::from_fn(|k| {
315            u64::conditional_select(&a.data[k], &b.data[k], choice)
316        }))
317    }
318}
319
320impl<P: Gf2ExtParams, const LIMBS: usize> ConstantTimeEq for Gf2Ext<P, LIMBS> {
321    fn ct_eq(&self, other: &Self) -> Choice {
322        izip!(self.data, other.data).fold(1u8.into(), |r, ab| r & ab.0.ct_eq(&ab.1))
323    }
324}
325
326// === Implementation of arithmetic operators === //
327
328// Negation
329
330#[macros::op_variants(borrowed)]
331impl<P: Gf2ExtParams, const LIMBS: usize> Neg for Gf2Ext<P, LIMBS> {
332    type Output = Gf2Ext<P, LIMBS>;
333
334    #[inline]
335    fn neg(self) -> Self::Output {
336        self
337    }
338}
339
340// Addition
341
342#[macros::op_variants(owned, borrowed, flipped_commutative)]
343impl<P: Gf2ExtParams, const LIMBS: usize> Add<&Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS> {
344    type Output = Gf2Ext<P, LIMBS>;
345
346    #[inline]
347    #[allow(clippy::op_ref)]
348    fn add(mut self, rhs: &Self::Output) -> Self::Output {
349        self += rhs;
350        self
351    }
352}
353
354#[macros::op_variants(owned)]
355impl<P: Gf2ExtParams, const LIMBS: usize> AddAssign<&Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS> {
356    #[allow(clippy::suspicious_op_assign_impl)]
357    fn add_assign(&mut self, rhs: &Self) {
358        izip!(&mut self.data, rhs.data).for_each(|(a, b)| *a ^= b);
359    }
360}
361
362// Subtraction
363
364#[macros::op_variants(owned, borrowed, flipped)]
365impl<P: Gf2ExtParams, const LIMBS: usize> Sub<&Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS> {
366    type Output = Gf2Ext<P, LIMBS>;
367
368    #[inline]
369    #[allow(clippy::suspicious_arithmetic_impl)]
370    fn sub(self, rhs: &Self::Output) -> Self::Output {
371        self + rhs
372    }
373}
374
375#[macros::op_variants(owned)]
376impl<P: Gf2ExtParams, const LIMBS: usize> SubAssign<&Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS> {
377    #[inline]
378    #[allow(clippy::suspicious_op_assign_impl)]
379    fn sub_assign(&mut self, rhs: &Self) {
380        *self += rhs;
381    }
382}
383
384// Multiplication
385
386#[macros::op_variants(owned, borrowed)]
387impl<P: Gf2ExtParams, const LIMBS: usize> Mul<&Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS>
388where
389    Gf2Ext<P, LIMBS>: MulWide<Output = Gf2LimbsWide<LIMBS>>,
390{
391    type Output = Gf2Ext<P, LIMBS>;
392
393    #[inline]
394    fn mul(mut self, rhs: &Self::Output) -> Self::Output {
395        self *= rhs;
396        self
397    }
398}
399
400impl<P: Gf2ExtParams, const LIMBS: usize> Mul<Gf2Ext<P, LIMBS>> for &Gf2Ext<P, LIMBS>
401where
402    Gf2Ext<P, LIMBS>: MulWide<Output = Gf2LimbsWide<LIMBS>>,
403{
404    type Output = Gf2Ext<P, LIMBS>;
405
406    #[inline]
407    fn mul(self, rhs: Self::Output) -> Self::Output {
408        rhs * self
409    }
410}
411
412impl<P: Gf2ExtParams, const LIMBS: usize> MulAssign<&Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS>
413where
414    Gf2Ext<P, LIMBS>: MulAssign,
415{
416    #[inline]
417    fn mul_assign(&mut self, rhs: &Gf2Ext<P, LIMBS>) {
418        *self *= *rhs;
419    }
420}
421
422impl<P: Gf2ExtParams, const LIMBS: usize> MulAssign<Gf2> for Gf2Ext<P, LIMBS>
423where
424    Gf2Ext<P, LIMBS>: MulAssign,
425{
426    #[inline]
427    fn mul_assign(&mut self, rhs: Gf2) {
428        self.data
429            .iter_mut()
430            .for_each(|limb: &mut u64| *limb *= rhs.0 as u64)
431    }
432}
433
434impl<P: Gf2ExtParams, const LIMBS: usize> MulAssign<&Gf2> for Gf2Ext<P, LIMBS>
435where
436    Gf2Ext<P, LIMBS>: MulAssign,
437{
438    #[inline]
439    fn mul_assign(&mut self, rhs: &Gf2) {
440        self.data
441            .iter_mut()
442            .for_each(|limb: &mut u64| *limb *= rhs.0 as u64)
443    }
444}
445
446impl<P: Gf2ExtParams, const LIMBS: usize> MulAssign for Gf2Ext<P, LIMBS>
447where
448    Gf2Ext<P, LIMBS>: MulWide<Output = Gf2LimbsWide<LIMBS>>,
449    Gf2Ext<P, LIMBS>: IntoWide<Gf2LimbsWide<LIMBS>>,
450{
451    fn mul_assign(&mut self, rhs: Self) {
452        let res_wide = self.mul_wide(rhs);
453        *self = Self::reduce_mod_order(res_wide)
454    }
455}
456
457impl<P: Gf2ExtParams, const LIMBS: usize> Sum for Gf2Ext<P, LIMBS> {
458    #[inline]
459    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
460        iter.fold(Gf2Ext::ZERO, |a, b| a + b)
461    }
462}
463
464impl<'a, P: Gf2ExtParams, const LIMBS: usize> Sum<&'a Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS> {
465    #[inline]
466    fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
467        iter.fold(Gf2Ext::ZERO, |a, b| a + b)
468    }
469}
470
471impl<P: Gf2ExtParams, const LIMBS: usize> Product for Gf2Ext<P, LIMBS>
472where
473    Gf2Ext<P, LIMBS>: MulWide<Output = Gf2LimbsWide<LIMBS>>,
474{
475    #[inline]
476    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
477        iter.fold(Gf2Ext::ONE, |a, b| a * b)
478    }
479}
480
481impl<'a, P: Gf2ExtParams, const LIMBS: usize> Product<&'a Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS>
482where
483    Gf2Ext<P, LIMBS>: MulWide<Output = Gf2LimbsWide<LIMBS>>,
484{
485    #[inline]
486    fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
487        iter.fold(Gf2Ext::ONE, |a, b| a * b)
488    }
489}
490
491// === Implementation of FieldExtension trait methods
492impl<P: Gf2ExtParams, const LIMBS: usize> FieldExtension for Gf2Ext<P, LIMBS>
493where
494    Gf2Ext<P, LIMBS>: MulWide<Output = Gf2LimbsWide<LIMBS>>,
495    [u8; LIMBS]: AssocArraySize,
496    <[u8; LIMBS] as AssocArraySize>::Size: ArraySize + Positive + Mul<U8> + Mul<U64>,
497    Prod<<[u8; LIMBS] as AssocArraySize>::Size, U8>: ArraySize + Positive,
498    Prod<<[u8; LIMBS] as AssocArraySize>::Size, U64>: ArraySize + Positive,
499{
500    type Subfield = Gf2;
501
502    type Degree = P::Degree;
503    type FieldBitSize = Prod<<[u8; LIMBS] as AssocArraySize>::Size, U64>;
504    type FieldBytesSize = Prod<<[u8; LIMBS] as AssocArraySize>::Size, U8>;
505
506    fn to_subfield_elements(&self) -> Array<Self::Subfield, Self::Degree> {
507        let mut res = Array::default();
508        izip_eq!(&mut res, self.data.iter_lsb0()).for_each(|(elem, bit)| {
509            *elem = Gf2::from(bit);
510        });
511        res
512    }
513
514    fn from_subfield_elements(elems: Array<Self::Subfield, Self::Degree>) -> Self {
515        let mut data = [0u64; LIMBS];
516        for (i, elem) in elems.into_iter().enumerate() {
517            let limb_idx = i / 64;
518            let bit_idx = i % 64;
519            data[limb_idx] |= (bool::from(elem) as u64) << bit_idx;
520        }
521        Self::new(data)
522    }
523
524    fn to_le_bytes(&self) -> Array<u8, Self::FieldBytesSize> {
525        Array::from_iter(
526            (0..LIMBS)
527                .cartesian_product((0..64).step_by(8))
528                .map(|(limb, shift)| ((self.data[limb] >> shift) & 0xFF) as u8),
529        )
530    }
531
532    fn from_le_bytes(bytes: &[u8]) -> Option<Self> {
533        if bytes.len() != Self::FieldBytesSize::USIZE {
534            return None;
535        }
536
537        let mut it = bytes.chunks_exact(8).take(LIMBS);
538        Some(Self::new(std::array::from_fn(|_| {
539            u64::from_le_bytes(it.next().unwrap().try_into().unwrap())
540        })))
541    }
542
543    fn mul_by_subfield(&self, other: &Self::Subfield) -> Self {
544        *self * other
545    }
546
547    fn generator() -> Self {
548        Self::from_u64(2u64) // encoding of variable X
549    }
550
551    // Fast linear-orthomorphism for GF2 extensions of even degrees from "Minimizing the Two-Round
552    // Even-Mansour Cipher" by Chen et al.
553    fn linear_orthomorphism(&self) -> Self {
554        let mut res = Self::default();
555        for i in 0..LIMBS / 2 {
556            res.data[i] = self.data[i] ^ self.data[LIMBS - i - 1];
557            res.data[LIMBS - i - 1] = self.data[i];
558        }
559        if LIMBS % 2 == 1 {
560            let k = LIMBS / 2;
561            let (tl, th) = (self.data[k] as u32, (self.data[k] >> 32) as u32);
562
563            let (rl, rh) = (tl ^ th, tl);
564            res.data[k] = rl as u64 + ((rh as u64) << 32);
565        }
566
567        res
568    }
569}
570
571impl<P: Gf2ExtParams, const LIMBS: usize> Random for Gf2Ext<P, LIMBS> {
572    fn random(mut rng: impl CryptoRngCore) -> Self {
573        let mut tmp = Self::default();
574        rng.fill_bytes(tmp.as_mut_ne_bytes_slice());
575        tmp
576    }
577
578    fn random_array<M: Positive>(mut rng: impl CryptoRngCore) -> HeapArray<Self, M> {
579        let mut buf = HeapArray::<Self, M>::default().into_box_bytes();
580        rng.fill_bytes(&mut buf);
581        HeapArray::from_box_bytes(buf)
582    }
583}
584
585unsafe impl<P: Gf2ExtParams, const LIMBS: usize> bytemuck::Zeroable for Gf2Ext<P, LIMBS> {
586    fn zeroed() -> Self {
587        Self::ZERO
588    }
589}
590unsafe impl<P: Gf2ExtParams, const LIMBS: usize> bytemuck::Pod for Gf2Ext<P, LIMBS> {}
591
592// SAFETY: every `[u64; LIMBS]` bit pattern is a valid `Gf2Ext` (no canonical-form constraint,
593// unlike prime fields), and `write_le_bytes`/`read_le_bytes` encode each limb as a little-endian
594// `u64`, back to back (architecture-independent). `write_le_bytes` initializes every output byte
595// and the round-trip is unbiased.
596unsafe impl<P: Gf2ExtParams, const LIMBS: usize> InPlaceCodec for Gf2Ext<P, LIMBS> {
597    const ENCODED_SIZE: usize = LIMBS * 8;
598
599    fn write_le_bytes(&self, out: &mut [MaybeUninit<u8>]) {
600        for (chunk, limb) in out.chunks_exact_mut(8).zip(self.data) {
601            let bytes = limb.to_le_bytes();
602            // SAFETY: `chunk.len() == 8 == bytes.len()`; `copy_nonoverlapping` initializes every
603            // byte of `chunk` without reading it.
604            unsafe {
605                std::ptr::copy_nonoverlapping(bytes.as_ptr(), chunk.as_mut_ptr().cast::<u8>(), 8);
606            }
607        }
608    }
609
610    fn read_le_bytes(bytes: &[u8]) -> Result<Self, PrimitiveError> {
611        let mut data = [0u64; LIMBS];
612        for (limb, chunk) in data.iter_mut().zip(bytes.chunks_exact(8)) {
613            let chunk = chunk
614                .try_into()
615                .map_err(|_| PrimitiveError::InvalidSize(Self::ENCODED_SIZE, bytes.len()))?;
616            *limb = u64::from_le_bytes(chunk);
617        }
618        Ok(Self::new(data))
619    }
620}
621
622impl<P: Gf2ExtParams, const LIMBS: usize> Mul<Gf2> for Gf2Ext<P, LIMBS> {
623    type Output = Self;
624
625    #[allow(clippy::suspicious_arithmetic_impl)]
626    fn mul(mut self, rhs: Gf2) -> Self::Output {
627        // Transform 0/1 value into a bit-mask 00..0/11..1
628        let m = (-(rhs.0 as i64)) as u64;
629        self.data.iter_mut().for_each(|v: &mut u64| *v &= m);
630        self
631    }
632}
633
634impl<'a, P: Gf2ExtParams, const LIMBS: usize> Mul<&'a Gf2> for Gf2Ext<P, LIMBS> {
635    type Output = Self;
636
637    #[inline]
638    fn mul(self, rhs: &'a Gf2) -> Self::Output {
639        self * *rhs
640    }
641}
642
643// Lazy multiplication and modulus reduction
644
645/// Add gf2 polynomials encoded in Gf2LimbsWide<LIMBS>
646impl<const LIMBS: usize> AddAssign for Gf2LimbsWide<LIMBS> {
647    fn add_assign(&mut self, rhs: Self) {
648        izip!(&mut self.low, rhs.low).for_each(|(a, b)| *a ^= b);
649        izip!(&mut self.high, rhs.high).for_each(|(a, b)| *a ^= b);
650    }
651}
652
653// Wide type for Gf2Ext x Gf2Ext multiplication
654impl<P: Gf2ExtParams, const LIMBS: usize> IntoWide<Gf2LimbsWide<LIMBS>> for Gf2Ext<P, LIMBS> {
655    #[inline]
656    fn to_wide(&self) -> Gf2LimbsWide<LIMBS> {
657        Gf2LimbsWide {
658            low: self.data,
659            high: [0u64; LIMBS],
660        }
661    }
662
663    #[inline]
664    fn zero_wide() -> Gf2LimbsWide<LIMBS> {
665        Default::default()
666    }
667}
668
669impl<P: Gf2ExtParams, const LIMBS: usize> ReduceWide<Gf2LimbsWide<LIMBS>> for Gf2Ext<P, LIMBS> {
670    /// Reduce a GF2 polynomial of 2*LIMBS down to LIMBS.
671    /// * `poly` - polynomial to reduce
672    fn reduce_mod_order(a: Gf2LimbsWide<LIMBS>) -> Self {
673        let Gf2LimbsWide { mut low, mut high } = a;
674
675        let ones = P::POLY_MOD_ONES;
676
677        // Use a macro (instead of a function) to avoid rust borrowing rules in case `$inp` aliases
678        // with `$out_high`
679        macro_rules! reduce_1step {
680            ($out_low:expr, $out_high:expr, $inp:expr) => {
681                for k in ones {
682                    $out_high ^= $inp >> (64 - k);
683                }
684                $out_low ^= $inp;
685                for k in ones {
686                    $out_low ^= $inp << k;
687                }
688            };
689        }
690
691        reduce_1step!(low[LIMBS - 1], high[0], high[LIMBS - 1]);
692        for i in (0..LIMBS - 1).rev() {
693            reduce_1step!(low[i], low[i + 1], high[i]);
694        }
695
696        Gf2Ext {
697            data: low,
698            _id: PhantomData,
699        }
700    }
701}
702
703// Dot product: Gf2Ext x Gf2Ext
704impl<P: Gf2ExtParams, const LIMBS: usize> MulAccReduce for Gf2Ext<P, LIMBS>
705where
706    Self: MulWide<Output = Gf2LimbsWide<LIMBS>>,
707{
708    type WideType = Gf2LimbsWide<LIMBS>;
709
710    #[inline]
711    fn mul_acc(acc: &mut Self::WideType, a: Self, b: Self) {
712        *acc += a.mul_wide(b)
713    }
714}
715
716impl<P: Gf2ExtParams, const LIMBS: usize> DefaultDotProduct for Gf2Ext<P, LIMBS> where
717    Self: MulAccReduce
718{
719}
720
721// Dot product: Gf2Ext x &Gf2Ext
722impl<'a, P: Gf2ExtParams, const LIMBS: usize> DotProduct<Self, &'a Self> for Gf2Ext<P, LIMBS>
723where
724    Self: DefaultDotProduct,
725{
726    #[inline]
727    fn dot<I1, I2>(a: I1, b: I2) -> Self
728    where
729        I1: IntoExactSizeIterator<Item = Self>,
730        I2: IntoExactSizeIterator<Item = &'a Self>,
731    {
732        Self::dot(a, b.into_iter().copied())
733    }
734}
735
736// Dot product: &Gf2Ext x &Gf2Ext
737impl<'a, 'b, P: Gf2ExtParams, const LIMBS: usize> DotProduct<&'a Self, &'b Self>
738    for Gf2Ext<P, LIMBS>
739where
740    Self: DefaultDotProduct,
741{
742    #[inline]
743    fn dot<I1, I2>(a: I1, b: I2) -> Self
744    where
745        I1: IntoExactSizeIterator<Item = &'a Self>,
746        I2: IntoExactSizeIterator<Item = &'b Self>,
747    {
748        Self::dot(a.into_iter().copied(), b)
749    }
750}
751
752impl<P: Gf2ExtParams, const LIMBS: usize> IntoWide for Gf2Ext<P, LIMBS> {
753    #[inline]
754    fn to_wide(&self) -> Self {
755        *self
756    }
757
758    #[inline]
759    fn zero_wide() -> Self {
760        <Self as IntoWide>::to_wide(&Self::ZERO)
761    }
762}
763
764impl<P: Gf2ExtParams, const LIMBS: usize> ReduceWide for Gf2Ext<P, LIMBS> {
765    #[inline]
766    fn reduce_mod_order(a: Self) -> Self {
767        a
768    }
769}
770
771// Dot product : Gf2Ext, Gf2
772impl<P: Gf2ExtParams, const LIMBS: usize> MulAccReduce<Self, Gf2> for Gf2Ext<P, LIMBS> {
773    type WideType = Self;
774
775    #[inline]
776    fn mul_acc(acc: &mut Self, a: Self, b: Gf2) {
777        *acc += a * b;
778    }
779}
780
781impl<P: Gf2ExtParams, const LIMBS: usize> DefaultDotProduct<Self, Gf2> for Gf2Ext<P, LIMBS> {}
782
783// Dot product : &Gf2Ext, Gf2
784impl<'a, P: Gf2ExtParams, const LIMBS: usize> MulAccReduce<&'a Self, Gf2> for Gf2Ext<P, LIMBS> {
785    type WideType = Self;
786
787    #[inline]
788    fn mul_acc(acc: &mut Self, a: &'a Self, b: Gf2) {
789        Self::mul_acc(acc, *a, b);
790    }
791}
792
793impl<P: Gf2ExtParams, const LIMBS: usize> DefaultDotProduct<&Self, Gf2> for Gf2Ext<P, LIMBS> {}
794
795// Dot product : &Gf2Ext, &Gf2
796impl<'a, 'b, P: Gf2ExtParams, const LIMBS: usize> MulAccReduce<&'a Self, &'b Gf2>
797    for Gf2Ext<P, LIMBS>
798{
799    type WideType = Self;
800
801    #[inline]
802    fn mul_acc(acc: &mut Self, a: &'a Self, b: &'b Gf2) {
803        Self::mul_acc(acc, a, *b);
804    }
805}
806
807impl<P: Gf2ExtParams, const LIMBS: usize> DefaultDotProduct<&Self, &Gf2> for Gf2Ext<P, LIMBS> {}
808
809impl<P: Gf2ExtParams, const LIMBS: usize> AccReduce for Gf2Ext<P, LIMBS> {
810    type WideType = Self;
811
812    fn acc(acc: &mut Self, a: Self) {
813        *acc += a;
814    }
815}
816
817impl<P: Gf2ExtParams, const LIMBS: usize> AccReduce<&Self> for Gf2Ext<P, LIMBS> {
818    type WideType = Self;
819
820    fn acc(acc: &mut Self, a: &Self) {
821        *acc += a;
822    }
823}
824
825pub trait MulWide<Rhs = Self> {
826    type Output;
827    fn mul_wide(self, rhs: Rhs) -> Self::Output;
828}
829
830impl<P: Gf2ExtParams, const LIMBS: usize> FromUniformBytes for Gf2Ext<P, LIMBS>
831where
832    [u8; LIMBS]: AssocArraySize,
833    <[u8; LIMBS] as AssocArraySize>::Size: ArraySize + Positive + Mul<U8> + Mul<U64>,
834    Prod<<[u8; LIMBS] as AssocArraySize>::Size, U8>: ArraySize + Positive,
835{
836    type UniformBytes = Prod<<[u8; LIMBS] as AssocArraySize>::Size, U8>;
837
838    fn from_uniform_bytes(a: &Array<u8, Self::UniformBytes>) -> Self {
839        let mut it = a.chunks_exact(8).take(LIMBS);
840        Self::new(std::array::from_fn(|_| {
841            u64::from_le_bytes(it.next().unwrap().try_into().unwrap())
842        }))
843    }
844}
845
846impl<P: Gf2ExtParams, const LIMBS: usize> Zero for Gf2Ext<P, LIMBS> {
847    fn zero() -> Self {
848        Self::ZERO
849    }
850
851    fn is_zero(&self) -> bool {
852        self.ct_eq(&Self::ZERO).into()
853    }
854}
855
856impl<P: Gf2ExtParams, const LIMBS: usize> One for Gf2Ext<P, LIMBS>
857where
858    Self: Mul<Output = Self>,
859{
860    fn one() -> Self {
861        Self::ONE
862    }
863
864    fn is_one(&self) -> bool {
865        self.ct_eq(&Self::ONE).into()
866    }
867}
868
869// statically dispatch size-dependent MulWide implementation
870macro_rules! impl_wide_mul {
871    ($params:ty, 1) => {
872        impl $crate::algebra::field::binary::gf2_ext::MulWide for Gf2Ext<$params, 1> {
873            type Output = Gf2LimbsWide<1>;
874            fn mul_wide(self, rhs: Self) -> Self::Output {
875                let (low, high) =
876                    $crate::algebra::ops::clmul::carry_less_mul_1limb(self.data, rhs.data);
877                Gf2LimbsWide { low, high }
878            }
879        }
880    };
881    ($params:ty, 2) => {
882        impl $crate::algebra::field::binary::gf2_ext::MulWide for Gf2Ext<$params, 2> {
883            type Output = Gf2LimbsWide<2>;
884            fn mul_wide(self, rhs: Self) -> Self::Output {
885                let (low, high) =
886                    $crate::algebra::ops::clmul::carry_less_mul_2limbs(self.data, rhs.data);
887                Gf2LimbsWide { low, high }
888            }
889        }
890    };
891    ($params:ty, $limbs:literal) => {
892        impl $crate::algebra::field::binary::gf2_ext::MulWide for Gf2Ext<$params, $limbs> {
893            type Output = Gf2LimbsWide<$limbs>;
894            fn mul_wide(self, rhs: Self) -> Self::Output {
895                let (low, high) = $crate::algebra::ops::clmul::carry_less_mul(self.data, rhs.data);
896                Gf2LimbsWide { low, high }
897            }
898        }
899    };
900}
901pub(crate) use impl_wide_mul;
902
903macro_rules! validate_modulus_poly_ones {
904    ([$($val:literal),+ $(,)?]) => ($(
905        static_assertions::const_assert!(($val < 64) & ($val > 0));
906    )*);
907}
908pub(crate) use validate_modulus_poly_ones;
909
910macro_rules! define_gf2_extension {
911    ($ext_name:ident, $ext_params:ident, $limbs:tt, $modulus_poly_ones:tt) => {
912        $crate::algebra::field::binary::gf2_ext::validate_modulus_poly_ones!($modulus_poly_ones);
913
914        #[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
915        pub struct $ext_params;
916
917        pub type $ext_name = $crate::algebra::field::binary::gf2_ext::Gf2Ext<$ext_params, $limbs>;
918
919        // Note: do not move to generic implementation
920        impl $ext_name {
921            /// Casts the field element to a core byte array
922            pub fn into_ne_bytes_array(self) -> [u8; { $limbs * 8 }] {
923                bytemuck::cast(self.data)
924            }
925
926            pub fn from_ne_bytes_array(arr: [u8; { $limbs * 8 }]) -> Self {
927                Self::new(bytemuck::cast(arr))
928            }
929        }
930
931        $crate::algebra::field::binary::gf2_ext::impl_wide_mul!($ext_params, $limbs);
932
933        impl $crate::algebra::field::binary::gf2_ext::Gf2ExtParams for $ext_params {
934            type Degree = typenum::U<{ $limbs * 64 }>;
935            type Bytes = typenum::U<{ $limbs * 8 }>;
936            const POLY_MOD_ONES: &[usize] = &{ $modulus_poly_ones };
937        }
938    };
939}
940
941pub(crate) use define_gf2_extension;
942
943#[cfg(test)]
944mod tests {
945    use super::*;
946
947    const N_TESTS: usize = 1;
948
949    // sage instruction used to find minimal weight modulus polynomials:
950    //  GF(2^128, modulus="minimal_weight", name="x").polynomial()
951    define_gf2_extension!(Gf2_128, Gf2_128Params, 2, [1, 2, 7]);
952    define_gf2_extension!(Gf2_192, Gf2_192Params, 3, [1, 2, 7]);
953    define_gf2_extension!(Gf2_256, Gf2_256Params, 4, [2, 5, 10]);
954    define_gf2_extension!(Gf2_64, Gf2_64Params, 1, [1, 3, 4]);
955
956    #[test]
957    fn test_gf2_ext_operations() {
958        fn gf2_operations_test_case<F: FieldExtension>() {
959            let mut rng = crate::random::test_rng();
960            for _ in 0..N_TESTS {
961                let a: F = Random::random(&mut rng);
962                // a + a = 0
963                assert_eq!(a + a, F::ZERO);
964
965                // a * 234 = 234 * a
966                assert_eq!(a * F::from(234u64), F::from(234u64) * a);
967
968                // a * (a + 234) = a * a + 234 * a
969                assert_eq!(a * (a + F::from(234u64)), a * a + F::from(234u64) * a);
970
971                // a exp (2^degree) = a
972                let mut cumul = a;
973                for _ in 0..(F::Degree::to_usize()) {
974                    cumul *= cumul;
975                }
976                assert_eq!(a, cumul);
977            }
978        }
979
980        gf2_operations_test_case::<Gf2_128>();
981        gf2_operations_test_case::<Gf2_256>();
982        gf2_operations_test_case::<Gf2_192>();
983        gf2_operations_test_case::<Gf2_64>();
984    }
985
986    /// The bit-spreading `square` must agree with the generic multiply.
987    #[test]
988    fn test_gf2_ext_square() {
989        fn square_test_case<F: FieldExtension>() {
990            let mut rng = crate::random::test_rng();
991            assert_eq!(F::ZERO.square(), F::ZERO);
992            assert_eq!(F::ONE.square(), F::ONE);
993            for _ in 0..32 {
994                let a: F = Random::random(&mut rng);
995                assert_eq!(a.square(), a * a);
996            }
997        }
998
999        square_test_case::<Gf2_64>();
1000        square_test_case::<Gf2_128>();
1001        square_test_case::<Gf2_192>();
1002        square_test_case::<Gf2_256>();
1003    }
1004
1005    #[test]
1006    fn test_gf2_ext_invert() {
1007        fn invert_test_case<F: FieldExtension>() {
1008            let mut rng = crate::random::test_rng();
1009
1010            assert!(bool::from(F::ZERO.invert().is_none()));
1011            assert_eq!(F::ONE.invert().unwrap(), F::ONE);
1012            let g = F::generator();
1013            assert_eq!(g * g.invert().unwrap(), F::ONE);
1014
1015            for _ in 0..16 {
1016                let a: F = Random::random(&mut rng);
1017                if bool::from(a.is_zero()) {
1018                    continue;
1019                }
1020                assert_eq!(a * a.invert().unwrap(), F::ONE);
1021            }
1022        }
1023
1024        invert_test_case::<Gf2_64>();
1025        invert_test_case::<Gf2_128>();
1026        invert_test_case::<Gf2_192>();
1027        invert_test_case::<Gf2_256>();
1028    }
1029
1030    #[test]
1031    fn test_gf2_ext_sqrt() {
1032        fn sqrt_test_case<F: FieldExtension>() {
1033            let mut rng = crate::random::test_rng();
1034
1035            assert_eq!(F::ZERO.sqrt().unwrap(), F::ZERO);
1036            assert_eq!(F::ONE.sqrt().unwrap(), F::ONE);
1037
1038            for _ in 0..16 {
1039                let a: F = Random::random(&mut rng);
1040                // Every element of a char-2 field is a square.
1041                let root = a.sqrt().unwrap();
1042                assert_eq!(root * root, a);
1043
1044                // sqrt_ratio contract: div == 0 is invalid unless num == 0.
1045                let (is_valid, root) = F::sqrt_ratio(&a, &F::ONE);
1046                assert!(bool::from(is_valid));
1047                assert_eq!(root * root, a);
1048                let (is_valid, _) = F::sqrt_ratio(&a, &F::ZERO);
1049                assert_eq!(bool::from(is_valid), bool::from(a.is_zero()));
1050
1051                let b: F = Random::random(&mut rng);
1052                if bool::from(b.is_zero()) {
1053                    continue;
1054                }
1055                let (is_valid, root) = F::sqrt_ratio(&a, &b);
1056                assert!(bool::from(is_valid));
1057                assert_eq!(root * root * b, a);
1058            }
1059        }
1060
1061        sqrt_test_case::<Gf2_64>();
1062        sqrt_test_case::<Gf2_128>();
1063        sqrt_test_case::<Gf2_192>();
1064        sqrt_test_case::<Gf2_256>();
1065    }
1066
1067    #[test]
1068    fn test_gf2_128_prod() {
1069        macro_rules! gf2_128_prod_test_case {
1070            ($aval:expr, $bval:expr, $prod_red:expr) => {{
1071                let a: [u64; 2] = $aval;
1072                let b: [u64; 2] = $bval;
1073                let prod_red: [u64; 2] = $prod_red;
1074
1075                {
1076                    let ae = Gf2_128::from_limbs(a);
1077                    let be = Gf2_128::from_limbs(b);
1078                    let prod_red_comp = ae * be;
1079                    assert_eq!(prod_red_comp, Gf2_128::from_limbs(prod_red));
1080                }
1081            }};
1082        }
1083
1084        gf2_128_prod_test_case!(
1085            [0x9f418f3bffd84bba, 0x4a7c605645afdfb1],
1086            [0x80b7bd91cddc5be5, 0x3a97291035e41e1f],
1087            [0x46ca0b600a32c5f7, 0x823a605e0452082a]
1088        );
1089
1090        gf2_128_prod_test_case!(
1091            [0x74ef862bc1b6d333, 0x3a88103b80d97b73],
1092            [0x753f4846eb020b5a, 0x8f108359ea25fa8f],
1093            [0x6947ab52b94f0ef9, 0xb2ec1b5a4553aa6d]
1094        );
1095
1096        gf2_128_prod_test_case!(
1097            [0x6447b3dcaed62649, 0x6e4af40b2ee1b4c1],
1098            [0xbd7a4e12fdb29840, 0x8950f56742015f25],
1099            [0x38ae5eb860021fe9, 0x6f18457f05ac2506]
1100        );
1101    }
1102
1103    #[test]
1104    fn test_gf2_ext_inplace_roundtrip() {
1105        use typenum::U6;
1106
1107        use crate::types::HeapArray;
1108
1109        let array = HeapArray::<Gf2_128, U6>::from_fn(|i| Gf2_128::from_u64(i as u64));
1110        let inplace_ser = array.to_inplace_bytes();
1111
1112        let deserialized = HeapArray::<Gf2_128, U6>::from_inplace_bytes(&inplace_ser).unwrap();
1113        assert_eq!(deserialized, array);
1114
1115        // Wrong length is rejected.
1116        assert!(HeapArray::<Gf2_128, U6>::from_inplace_bytes(&inplace_ser[..1]).is_err());
1117    }
1118}
primitives/algebra/field/binary/gf2_ext.rs

primitives/algebra/field/binary/
gf2_ext.rs
