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    ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
8    str,
9};
10
11use derive_more::{AsMut, AsRef};
12use ff::Field;
13use hybrid_array::{Array, ArraySize, AssocArraySize};
14use itertools::{izip, Itertools};
15use itybity::{FromBitIterator, ToBits};
16use rand::RngCore;
17use serde::{Deserialize, Serialize};
18use serde_with::serde_as;
19use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};
20use typenum::{Prod, Unsigned, U64, U8};
21
22use crate::{
23    algebra::{
24        field::{binary::Gf2, FieldExtension},
25        ops::{AccReduce, DefaultDotProduct, DotProduct, IntoWide, MulAccReduce, ReduceWide},
26        uniform_bytes::FromUniformBytes,
27    },
28    types::{HeapArray, Positive},
29    utils::IntoExactSizeIterator,
30};
31
32#[serde_as]
33#[derive(Clone, Copy, Debug, Eq, AsRef, AsMut, Serialize, Deserialize)]
34#[repr(transparent)]
35pub struct Gf2Ext<P: Gf2ExtParams, const LIMBS: usize> {
36    #[serde_as(as = "[_; LIMBS]")]
37    pub(crate) data: [u64; LIMBS],
38    _id: PhantomData<P>,
39}
40
41impl<P: Gf2ExtParams, const LIMBS: usize> AsRef<[u8]> for Gf2Ext<P, LIMBS> {
42    fn as_ref(&self) -> &[u8] {
43        // SAFETY: This is safe because:
44        // 1. We're only reading the bytes
45        // 2. The memory layout of [u64; LIMBS] is well-defined
46        // 3. The slice length is exactly LIMBS * 8 bytes
47        unsafe {
48            std::slice::from_raw_parts(
49                self.data.as_ptr() as *const u8,
50                LIMBS * std::mem::size_of::<u64>(),
51            )
52        }
53    }
54}
55
56impl<P: Gf2ExtParams, const LIMBS: usize> AsMut<[u8]> for Gf2Ext<P, LIMBS> {
57    fn as_mut(&mut self) -> &mut [u8] {
58        // SAFETY: This is safe because:
59        // 1. We have exclusive access to the bytes
60        // 2. The memory layout of [u64; LIMBS] is well-defined
61        // 3. The slice length is exactly LIMBS * 8 bytes
62        unsafe {
63            std::slice::from_raw_parts_mut(
64                self.data.as_mut_ptr() as *mut u8,
65                LIMBS * std::mem::size_of::<u64>(),
66            )
67        }
68    }
69}
70
71impl<P: Gf2ExtParams, const LIMBS: usize> PartialEq<Self> for Gf2Ext<P, LIMBS> {
72    fn eq(&self, other: &Self) -> bool {
73        self.cmp(other) == Ordering::Equal
74    }
75}
76
77impl<P: Gf2ExtParams, const LIMBS: usize> PartialOrd<Self> for Gf2Ext<P, LIMBS> {
78    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
79        Some(self.cmp(other))
80    }
81}
82
83impl<P: Gf2ExtParams, const LIMBS: usize> Ord for Gf2Ext<P, LIMBS> {
84    fn cmp(&self, other: &Self) -> Ordering {
85        self.data.cmp(&other.data)
86    }
87}
88
89impl<P: Gf2ExtParams, const LIMBS: usize> Hash for Gf2Ext<P, LIMBS> {
90    fn hash<H: Hasher>(&self, state: &mut H) {
91        let bytes: &[u8] = self.as_ref();
92        bytes.iter().for_each(|x| {
93            x.hash(state);
94        });
95    }
96}
97
98// Datatype which can store a dot product result without modulus reduction
99#[derive(Clone, Copy)]
100pub struct Gf2LimbsWide<const LIMBS: usize> {
101    pub(crate) low: [u64; LIMBS],
102    pub(crate) high: [u64; LIMBS],
103}
104
105pub trait Gf2ExtParams: Copy + Debug + Eq + PartialEq + Sync + Send + Unpin + 'static {
106    /// The extension degree, a multiple of 64
107    type Degree: ArraySize + Positive;
108
109    /// Number of bytes needed for the extension, a multiple of 8
110    type Bytes: ArraySize + Positive;
111    //  Modulus polynomial non-zero coefficients (x^0 is not included) positions
112    const POLY_MOD_ONES: &[usize];
113}
114
115impl<P: Gf2ExtParams, const LIMBS: usize> Gf2Ext<P, LIMBS> {
116    pub const fn new(data: [u64; LIMBS]) -> Self {
117        Self {
118            data,
119            _id: PhantomData,
120        }
121    }
122
123    const ZERO: Self = Self::new([0u64; LIMBS]);
124    const ONE: Self = Self::new({
125        let mut tmp = [0u64; LIMBS];
126        tmp[0] = 1;
127        tmp
128    });
129}
130
131impl<P: Gf2ExtParams, const LIMBS: usize> Gf2Ext<P, LIMBS> {
132    pub fn as_mut_ne_bytes_slice(&mut self) -> &mut [u8] {
133        bytemuck::bytes_of_mut(&mut self.data)
134    }
135
136    pub fn as_ne_bytes_slice(&self) -> &[u8] {
137        bytemuck::bytes_of(&self.data)
138    }
139
140    pub fn from_limbs(val: [u64; LIMBS]) -> Self {
141        Self::new(val)
142    }
143
144    pub fn from_u64(val: u64) -> Self {
145        let mut tmp = [0u64; LIMBS];
146        tmp[0] = val;
147        Self::from_limbs(tmp)
148    }
149
150    pub fn from_u128(val: u128) -> Self {
151        let mut tmp = [0u64; LIMBS];
152        tmp[0] = val as u64;
153        tmp[1] = (val >> 64) as u64;
154        Self::from_limbs(tmp)
155    }
156}
157
158impl<P: Gf2ExtParams, const LIMBS: usize> Default for Gf2Ext<P, LIMBS> {
159    fn default() -> Self {
160        Self::ZERO
161    }
162}
163
164impl<const LIMBS: usize> Default for Gf2LimbsWide<LIMBS> {
165    fn default() -> Self {
166        Self {
167            low: [0u64; LIMBS],
168            high: [0u64; LIMBS],
169        }
170    }
171}
172
173// === Conversion traits
174
175impl<P: Gf2ExtParams, const LIMBS: usize> From<bool> for Gf2Ext<P, LIMBS> {
176    #[inline]
177    fn from(value: bool) -> Self {
178        Self::from_u64(value as u64)
179    }
180}
181
182impl<P: Gf2ExtParams, const LIMBS: usize> From<u8> for Gf2Ext<P, LIMBS> {
183    #[inline]
184    fn from(value: u8) -> Self {
185        Self::from_u64(value as u64)
186    }
187}
188
189impl<P: Gf2ExtParams, const LIMBS: usize> From<u16> for Gf2Ext<P, LIMBS> {
190    #[inline]
191    fn from(value: u16) -> Self {
192        Self::from_u64(value as u64)
193    }
194}
195
196impl<P: Gf2ExtParams, const LIMBS: usize> From<u32> for Gf2Ext<P, LIMBS> {
197    #[inline]
198    fn from(value: u32) -> Self {
199        Self::from_u64(value as u64)
200    }
201}
202
203impl<P: Gf2ExtParams, const LIMBS: usize> From<u64> for Gf2Ext<P, LIMBS> {
204    #[inline]
205    fn from(value: u64) -> Self {
206        Self::from_u64(value)
207    }
208}
209
210impl<P: Gf2ExtParams, const LIMBS: usize> From<u128> for Gf2Ext<P, LIMBS> {
211    #[inline]
212    fn from(value: u128) -> Self {
213        Self::from_u128(value)
214    }
215}
216
217// === Implementation of Field trait methods
218
219impl<P: Gf2ExtParams, const LIMBS: usize> Field for Gf2Ext<P, LIMBS>
220where
221    Gf2Ext<P, LIMBS>: MulWide<Output = Gf2LimbsWide<LIMBS>>,
222{
223    const ZERO: Self = Self::ZERO;
224    const ONE: Self = Self::ONE;
225
226    fn random(mut rng: impl RngCore) -> Self {
227        let mut tmp = Self::default();
228        rng.fill_bytes(tmp.as_mut_ne_bytes_slice());
229        tmp
230    }
231
232    fn square(&self) -> Self {
233        self * self
234    }
235
236    fn double(&self) -> Self {
237        self + self
238    }
239
240    fn invert(&self) -> CtOption<Self> {
241        unimplemented!()
242    }
243
244    fn sqrt_ratio(_num: &Self, _div: &Self) -> (Choice, Self) {
245        unimplemented!()
246    }
247}
248
249impl<P: Gf2ExtParams, const LIMBS: usize> ConditionallySelectable for Gf2Ext<P, LIMBS> {
250    #[inline]
251    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
252        Self::from_limbs(std::array::from_fn(|k| {
253            u64::conditional_select(&a.data[k], &b.data[k], choice)
254        }))
255    }
256}
257
258impl<P: Gf2ExtParams, const LIMBS: usize> ConstantTimeEq for Gf2Ext<P, LIMBS> {
259    fn ct_eq(&self, other: &Self) -> Choice {
260        izip!(self.data, other.data).fold(1u8.into(), |r, ab| r & ab.0.ct_eq(&ab.1))
261    }
262}
263
264// === Implementation of arithmetic operators === //
265
266// Negation
267
268#[macros::op_variants(borrowed)]
269impl<P: Gf2ExtParams, const LIMBS: usize> Neg for Gf2Ext<P, LIMBS> {
270    type Output = Gf2Ext<P, LIMBS>;
271
272    #[inline]
273    fn neg(self) -> Self::Output {
274        self
275    }
276}
277
278// Addition
279
280#[macros::op_variants(owned, borrowed, flipped_commutative)]
281impl<P: Gf2ExtParams, const LIMBS: usize> Add<&Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS> {
282    type Output = Gf2Ext<P, LIMBS>;
283
284    #[inline]
285    #[allow(clippy::op_ref)]
286    fn add(mut self, rhs: &Self::Output) -> Self::Output {
287        self += rhs;
288        self
289    }
290}
291
292#[macros::op_variants(owned)]
293impl<P: Gf2ExtParams, const LIMBS: usize> AddAssign<&Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS> {
294    #[allow(clippy::suspicious_op_assign_impl)]
295    fn add_assign(&mut self, rhs: &Self) {
296        izip!(&mut self.data, rhs.data).for_each(|(a, b)| *a ^= b);
297    }
298}
299
300// Subtraction
301
302#[macros::op_variants(owned, borrowed, flipped)]
303impl<P: Gf2ExtParams, const LIMBS: usize> Sub<&Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS> {
304    type Output = Gf2Ext<P, LIMBS>;
305
306    #[inline]
307    #[allow(clippy::suspicious_arithmetic_impl)]
308    fn sub(self, rhs: &Self::Output) -> Self::Output {
309        self + rhs
310    }
311}
312
313#[macros::op_variants(owned)]
314impl<P: Gf2ExtParams, const LIMBS: usize> SubAssign<&Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS> {
315    #[inline]
316    #[allow(clippy::suspicious_op_assign_impl)]
317    fn sub_assign(&mut self, rhs: &Self) {
318        *self += rhs;
319    }
320}
321
322// Multiplication
323
324#[macros::op_variants(owned, borrowed)]
325impl<P: Gf2ExtParams, const LIMBS: usize> Mul<&Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS>
326where
327    Gf2Ext<P, LIMBS>: MulWide<Output = Gf2LimbsWide<LIMBS>>,
328{
329    type Output = Gf2Ext<P, LIMBS>;
330
331    #[inline]
332    fn mul(mut self, rhs: &Self::Output) -> Self::Output {
333        self *= rhs;
334        self
335    }
336}
337
338impl<P: Gf2ExtParams, const LIMBS: usize> Mul<Gf2Ext<P, LIMBS>> for &Gf2Ext<P, LIMBS>
339where
340    Gf2Ext<P, LIMBS>: MulWide<Output = Gf2LimbsWide<LIMBS>>,
341{
342    type Output = Gf2Ext<P, LIMBS>;
343
344    #[inline]
345    fn mul(self, rhs: Self::Output) -> Self::Output {
346        rhs * self
347    }
348}
349
350impl<P: Gf2ExtParams, const LIMBS: usize> MulAssign<&Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS>
351where
352    Gf2Ext<P, LIMBS>: MulAssign,
353{
354    #[inline]
355    fn mul_assign(&mut self, rhs: &Gf2Ext<P, LIMBS>) {
356        *self *= *rhs;
357    }
358}
359
360impl<P: Gf2ExtParams, const LIMBS: usize> MulAssign<Gf2> for Gf2Ext<P, LIMBS>
361where
362    Gf2Ext<P, LIMBS>: MulAssign,
363{
364    #[inline]
365    fn mul_assign(&mut self, rhs: Gf2) {
366        self.data
367            .iter_mut()
368            .for_each(|limb: &mut u64| *limb *= rhs.0 as u64)
369    }
370}
371
372impl<P: Gf2ExtParams, const LIMBS: usize> MulAssign<&Gf2> for Gf2Ext<P, LIMBS>
373where
374    Gf2Ext<P, LIMBS>: MulAssign,
375{
376    #[inline]
377    fn mul_assign(&mut self, rhs: &Gf2) {
378        self.data
379            .iter_mut()
380            .for_each(|limb: &mut u64| *limb *= rhs.0 as u64)
381    }
382}
383
384impl<P: Gf2ExtParams, const LIMBS: usize> MulAssign for Gf2Ext<P, LIMBS>
385where
386    Gf2Ext<P, LIMBS>: MulWide<Output = Gf2LimbsWide<LIMBS>>,
387    Gf2Ext<P, LIMBS>: IntoWide<Gf2LimbsWide<LIMBS>>,
388{
389    fn mul_assign(&mut self, rhs: Self) {
390        let res_wide = self.mul_wide(rhs);
391        *self = Self::reduce_mod_order(res_wide)
392    }
393}
394
395impl<P: Gf2ExtParams, const LIMBS: usize> Sum for Gf2Ext<P, LIMBS> {
396    #[inline]
397    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
398        iter.fold(Gf2Ext::ZERO, |a, b| a + b)
399    }
400}
401
402impl<'a, P: Gf2ExtParams, const LIMBS: usize> Sum<&'a Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS> {
403    #[inline]
404    fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
405        iter.fold(Gf2Ext::ZERO, |a, b| a + b)
406    }
407}
408
409impl<P: Gf2ExtParams, const LIMBS: usize> Product for Gf2Ext<P, LIMBS>
410where
411    Gf2Ext<P, LIMBS>: MulWide<Output = Gf2LimbsWide<LIMBS>>,
412{
413    #[inline]
414    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
415        iter.fold(Gf2Ext::ONE, |a, b| a * b)
416    }
417}
418
419impl<'a, P: Gf2ExtParams, const LIMBS: usize> Product<&'a Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS>
420where
421    Gf2Ext<P, LIMBS>: MulWide<Output = Gf2LimbsWide<LIMBS>>,
422{
423    #[inline]
424    fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
425        iter.fold(Gf2Ext::ONE, |a, b| a * b)
426    }
427}
428
429// === Implementation of FieldExtension trait methods
430impl<P: Gf2ExtParams, const LIMBS: usize> FieldExtension for Gf2Ext<P, LIMBS>
431where
432    Gf2Ext<P, LIMBS>: MulWide<Output = Gf2LimbsWide<LIMBS>>,
433    [u8; LIMBS]: AssocArraySize,
434    <[u8; LIMBS] as AssocArraySize>::Size: ArraySize + Positive + Mul<U8> + Mul<U64>,
435    Prod<<[u8; LIMBS] as AssocArraySize>::Size, U8>: ArraySize + Positive,
436    Prod<<[u8; LIMBS] as AssocArraySize>::Size, U64>: ArraySize + Positive,
437{
438    type Subfield = Gf2;
439
440    type Degree = P::Degree;
441    type FieldBitSize = Prod<<[u8; LIMBS] as AssocArraySize>::Size, U64>;
442    type FieldBytesSize = Prod<<[u8; LIMBS] as AssocArraySize>::Size, U8>;
443
444    fn to_subfield_elements(&self) -> impl ExactSizeIterator<Item = Self::Subfield> {
445        self.data.iter_lsb0().take(P::Degree::USIZE).map(Gf2::from)
446    }
447
448    fn from_subfield_elements(elems: &[Self::Subfield]) -> Option<Self> {
449        if elems.len() == P::Degree::to_usize() {
450            let mut iter = elems
451                .chunks_exact(64)
452                .map(|a| u64::from_lsb0_iter(a.iter().map(bool::from)));
453            Some(Self::new(std::array::from_fn(|_| iter.next().unwrap())))
454        } else {
455            None
456        }
457    }
458
459    fn to_le_bytes(&self) -> impl IntoIterator<Item = u8> {
460        (0..LIMBS)
461            .cartesian_product((0..64).step_by(8))
462            .map(|(limb, shift)| ((self.data[limb] >> shift) & 0xFF) as u8)
463    }
464
465    fn from_le_bytes(bytes: &[u8]) -> Option<Self> {
466        if bytes.len() != Self::FieldBytesSize::USIZE {
467            return None;
468        }
469
470        let mut it = bytes.chunks_exact(8).take(LIMBS);
471        Some(Self::new(std::array::from_fn(|_| {
472            u64::from_le_bytes(it.next().unwrap().try_into().unwrap())
473        })))
474    }
475
476    fn mul_by_subfield(&self, other: &Self::Subfield) -> Self {
477        *self * other
478    }
479
480    fn generator() -> Self {
481        Self::from_u64(2u64) // encoding of variable X
482    }
483
484    // ** Note: ** Starting from N = 256 the performance gains are minor
485    fn random_elements<M: Positive>(mut rng: impl RngCore) -> HeapArray<Self, M> {
486        let mut buf = HeapArray::<Self, M>::default().into_box_bytes();
487        rng.fill_bytes(&mut buf);
488        HeapArray::from_box_bytes(buf)
489    }
490
491    // Fast linear-orthomorphism for GF2 extensions of even degrees from "Minimizing the Two-Round
492    // Even-Mansour Cipher" by Chen et al.
493    fn linear_orthomorphism(&self) -> Self {
494        let mut res = Self::default();
495        for i in 0..LIMBS / 2 {
496            res.data[i] = self.data[i] ^ self.data[LIMBS - i - 1];
497            res.data[LIMBS - i - 1] = self.data[i];
498        }
499        if LIMBS % 2 == 1 {
500            let k = LIMBS / 2;
501            let (tl, th) = (self.data[k] as u32, (self.data[k] >> 32) as u32);
502
503            let (rl, rh) = (tl ^ th, tl);
504            res.data[k] = rl as u64 + ((rh as u64) << 32);
505        }
506
507        res
508    }
509}
510
511unsafe impl<P: Gf2ExtParams, const LIMBS: usize> bytemuck::Zeroable for Gf2Ext<P, LIMBS> {
512    fn zeroed() -> Self {
513        Self::ZERO
514    }
515}
516unsafe impl<P: Gf2ExtParams, const LIMBS: usize> bytemuck::Pod for Gf2Ext<P, LIMBS> {}
517
518impl<P: Gf2ExtParams, const LIMBS: usize> Add<Gf2> for Gf2Ext<P, LIMBS> {
519    type Output = Self;
520
521    #[allow(clippy::suspicious_arithmetic_impl)]
522    fn add(mut self, rhs: Gf2) -> Self::Output {
523        // Transform 0/1 value into a bit-mask 00..0/11..1
524        let m = (-(rhs.0 as i64)) as u64;
525        self.data.iter_mut().for_each(|v: &mut u64| *v ^= m);
526        self
527    }
528}
529
530impl<'a, P: Gf2ExtParams, const LIMBS: usize> Add<&'a Gf2> for Gf2Ext<P, LIMBS> {
531    type Output = Self;
532
533    #[inline]
534    fn add(self, rhs: &'a Gf2) -> Self::Output {
535        self + *rhs
536    }
537}
538
539impl<P: Gf2ExtParams, const LIMBS: usize> Mul<Gf2> for Gf2Ext<P, LIMBS> {
540    type Output = Self;
541
542    #[allow(clippy::suspicious_arithmetic_impl)]
543    fn mul(mut self, rhs: Gf2) -> Self::Output {
544        // Transform 0/1 value into a bit-mask 00..0/11..1
545        let m = (-(rhs.0 as i64)) as u64;
546        self.data.iter_mut().for_each(|v: &mut u64| *v &= m);
547        self
548    }
549}
550
551impl<'a, P: Gf2ExtParams, const LIMBS: usize> Mul<&'a Gf2> for Gf2Ext<P, LIMBS> {
552    type Output = Self;
553
554    #[inline]
555    fn mul(self, rhs: &'a Gf2) -> Self::Output {
556        self * *rhs
557    }
558}
559
560// Lazy multiplication and modulus reduction
561
562/// Add gf2 polynomials encoded in Gf2LimbsWide<LIMBS>
563impl<const LIMBS: usize> AddAssign for Gf2LimbsWide<LIMBS> {
564    fn add_assign(&mut self, rhs: Self) {
565        izip!(&mut self.low, rhs.low).for_each(|(a, b)| *a ^= b);
566        izip!(&mut self.high, rhs.high).for_each(|(a, b)| *a ^= b);
567    }
568}
569
570// Wide type for Gf2Ext x Gf2Ext multiplication
571impl<P: Gf2ExtParams, const LIMBS: usize> IntoWide<Gf2LimbsWide<LIMBS>> for Gf2Ext<P, LIMBS> {
572    #[inline]
573    fn to_wide(&self) -> Gf2LimbsWide<LIMBS> {
574        Gf2LimbsWide {
575            low: self.data,
576            high: [0u64; LIMBS],
577        }
578    }
579
580    #[inline]
581    fn zero_wide() -> Gf2LimbsWide<LIMBS> {
582        Default::default()
583    }
584}
585
586impl<P: Gf2ExtParams, const LIMBS: usize> ReduceWide<Gf2LimbsWide<LIMBS>> for Gf2Ext<P, LIMBS> {
587    /// Reduce a GF2 polynomial of 2*LIMBS down to LIMBS.
588    /// * `poly` - polynomial to reduce
589    fn reduce_mod_order(a: Gf2LimbsWide<LIMBS>) -> Self {
590        let Gf2LimbsWide { mut low, mut high } = a;
591
592        let ones = P::POLY_MOD_ONES;
593
594        // Use a macro (instead of a function) to avoid rust borrowing rules in case `$inp` aliases
595        // with `$out_high`
596        macro_rules! reduce_1step {
597            ($out_low:expr, $out_high:expr, $inp:expr) => {
598                for k in ones {
599                    $out_high ^= $inp >> (64 - k);
600                }
601                $out_low ^= $inp;
602                for k in ones {
603                    $out_low ^= $inp << k;
604                }
605            };
606        }
607
608        reduce_1step!(low[LIMBS - 1], high[0], high[LIMBS - 1]);
609        for i in (0..LIMBS - 1).rev() {
610            reduce_1step!(low[i], low[i + 1], high[i]);
611        }
612
613        Gf2Ext {
614            data: low,
615            _id: PhantomData,
616        }
617    }
618}
619
620// Dot product: Gf2Ext x Gf2Ext
621impl<P: Gf2ExtParams, const LIMBS: usize> MulAccReduce for Gf2Ext<P, LIMBS>
622where
623    Self: MulWide<Output = Gf2LimbsWide<LIMBS>>,
624{
625    type WideType = Gf2LimbsWide<LIMBS>;
626
627    #[inline]
628    fn mul_acc(acc: &mut Self::WideType, a: Self, b: Self) {
629        *acc += a.mul_wide(b)
630    }
631}
632
633impl<P: Gf2ExtParams, const LIMBS: usize> DefaultDotProduct for Gf2Ext<P, LIMBS> where
634    Self: MulAccReduce
635{
636}
637
638// Dot product: Gf2Ext x &Gf2Ext
639impl<'a, P: Gf2ExtParams, const LIMBS: usize> DotProduct<Self, &'a Self> for Gf2Ext<P, LIMBS>
640where
641    Self: DefaultDotProduct,
642{
643    #[inline]
644    fn dot<I1, I2>(a: I1, b: I2) -> Self
645    where
646        I1: IntoExactSizeIterator<Item = Self>,
647        I2: IntoExactSizeIterator<Item = &'a Self>,
648    {
649        Self::dot(a, b.into_iter().copied())
650    }
651}
652
653// Dot product: &Gf2Ext x &Gf2Ext
654impl<'a, 'b, P: Gf2ExtParams, const LIMBS: usize> DotProduct<&'a Self, &'b Self>
655    for Gf2Ext<P, LIMBS>
656where
657    Self: DefaultDotProduct,
658{
659    #[inline]
660    fn dot<I1, I2>(a: I1, b: I2) -> Self
661    where
662        I1: IntoExactSizeIterator<Item = &'a Self>,
663        I2: IntoExactSizeIterator<Item = &'b Self>,
664    {
665        Self::dot(a.into_iter().copied(), b)
666    }
667}
668
669impl<P: Gf2ExtParams, const LIMBS: usize> IntoWide for Gf2Ext<P, LIMBS> {
670    #[inline]
671    fn to_wide(&self) -> Self {
672        *self
673    }
674
675    #[inline]
676    fn zero_wide() -> Self {
677        <Self as IntoWide>::to_wide(&Self::ZERO)
678    }
679}
680
681impl<P: Gf2ExtParams, const LIMBS: usize> ReduceWide for Gf2Ext<P, LIMBS> {
682    #[inline]
683    fn reduce_mod_order(a: Self) -> Self {
684        a
685    }
686}
687
688// Dot product : Gf2Ext, Gf2
689impl<P: Gf2ExtParams, const LIMBS: usize> MulAccReduce<Self, Gf2> for Gf2Ext<P, LIMBS> {
690    type WideType = Self;
691
692    #[inline]
693    fn mul_acc(acc: &mut Self, a: Self, b: Gf2) {
694        *acc += a * b;
695    }
696}
697
698impl<P: Gf2ExtParams, const LIMBS: usize> DefaultDotProduct<Self, Gf2> for Gf2Ext<P, LIMBS> {}
699
700// Dot product : &Gf2Ext, Gf2
701impl<'a, P: Gf2ExtParams, const LIMBS: usize> MulAccReduce<&'a Self, Gf2> for Gf2Ext<P, LIMBS> {
702    type WideType = Self;
703
704    #[inline]
705    fn mul_acc(acc: &mut Self, a: &'a Self, b: Gf2) {
706        Self::mul_acc(acc, *a, b);
707    }
708}
709
710impl<P: Gf2ExtParams, const LIMBS: usize> DefaultDotProduct<&Self, Gf2> for Gf2Ext<P, LIMBS> {}
711
712// Dot product : &Gf2Ext, &Gf2
713impl<'a, 'b, P: Gf2ExtParams, const LIMBS: usize> MulAccReduce<&'a Self, &'b Gf2>
714    for Gf2Ext<P, LIMBS>
715{
716    type WideType = Self;
717
718    #[inline]
719    fn mul_acc(acc: &mut Self, a: &'a Self, b: &'b Gf2) {
720        Self::mul_acc(acc, a, *b);
721    }
722}
723
724impl<P: Gf2ExtParams, const LIMBS: usize> DefaultDotProduct<&Self, &Gf2> for Gf2Ext<P, LIMBS> {}
725
726impl<P: Gf2ExtParams, const LIMBS: usize> AccReduce for Gf2Ext<P, LIMBS> {
727    type WideType = Self;
728
729    fn acc(acc: &mut Self, a: Self) {
730        *acc += a;
731    }
732}
733
734impl<P: Gf2ExtParams, const LIMBS: usize> AccReduce<&Self> for Gf2Ext<P, LIMBS> {
735    type WideType = Self;
736
737    fn acc(acc: &mut Self, a: &Self) {
738        *acc += a;
739    }
740}
741
742pub trait MulWide<Rhs = Self> {
743    type Output;
744    fn mul_wide(self, rhs: Rhs) -> Self::Output;
745}
746
747impl<P: Gf2ExtParams, const LIMBS: usize> FromUniformBytes for Gf2Ext<P, LIMBS>
748where
749    [u8; LIMBS]: AssocArraySize,
750    <[u8; LIMBS] as AssocArraySize>::Size: ArraySize + Positive + Mul<U8> + Mul<U64>,
751    Prod<<[u8; LIMBS] as AssocArraySize>::Size, U8>: ArraySize + Positive,
752{
753    type UniformBytes = Prod<<[u8; LIMBS] as AssocArraySize>::Size, U8>;
754
755    fn from_uniform_bytes(a: &Array<u8, Self::UniformBytes>) -> Self {
756        let mut it = a.chunks_exact(8).take(LIMBS);
757        Self::new(std::array::from_fn(|_| {
758            u64::from_le_bytes(it.next().unwrap().try_into().unwrap())
759        }))
760    }
761}
762
763// statically dispatch size-dependent MulWide implementation
764macro_rules! impl_wide_mul {
765    ($params:ty, 1) => {
766        impl $crate::algebra::field::binary::gf2_ext::MulWide for Gf2Ext<$params, 1> {
767            type Output = Gf2LimbsWide<1>;
768            fn mul_wide(self, rhs: Self) -> Self::Output {
769                let (low, high) =
770                    $crate::algebra::ops::clmul::carry_less_mul_1limb(self.data, rhs.data);
771                Gf2LimbsWide { low, high }
772            }
773        }
774    };
775    ($params:ty, 2) => {
776        impl $crate::algebra::field::binary::gf2_ext::MulWide for Gf2Ext<$params, 2> {
777            type Output = Gf2LimbsWide<2>;
778            fn mul_wide(self, rhs: Self) -> Self::Output {
779                let (low, high) =
780                    $crate::algebra::ops::clmul::carry_less_mul_2limbs(self.data, rhs.data);
781                Gf2LimbsWide { low, high }
782            }
783        }
784    };
785    ($params:ty, $limbs:literal) => {
786        impl $crate::algebra::field::binary::gf2_ext::MulWide for Gf2Ext<$params, $limbs> {
787            type Output = Gf2LimbsWide<$limbs>;
788            fn mul_wide(self, rhs: Self) -> Self::Output {
789                let (low, high) = $crate::algebra::ops::clmul::carry_less_mul(self.data, rhs.data);
790                Gf2LimbsWide { low, high }
791            }
792        }
793    };
794}
795pub(crate) use impl_wide_mul;
796
797macro_rules! validate_modulus_poly_ones {
798    ([$($val:literal),+ $(,)?]) => ($(
799        static_assertions::const_assert!(($val < 64) & ($val > 0));
800    )*);
801}
802pub(crate) use validate_modulus_poly_ones;
803
804macro_rules! define_gf2_extension {
805    ($ext_name:ident, $ext_params:ident, $limbs:tt, $modulus_poly_ones:tt) => {
806        $crate::algebra::field::binary::gf2_ext::validate_modulus_poly_ones!($modulus_poly_ones);
807
808        #[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
809        pub struct $ext_params;
810
811        pub type $ext_name = $crate::algebra::field::binary::gf2_ext::Gf2Ext<$ext_params, $limbs>;
812
813        // Note: do not move to generic implementation
814        impl $ext_name {
815            /// Casts the field element to a core byte array
816            pub fn into_ne_bytes_array(self) -> [u8; { $limbs * 8 }] {
817                bytemuck::cast(self.data)
818            }
819
820            pub fn from_ne_bytes_array(arr: [u8; { $limbs * 8 }]) -> Self {
821                Self::new(bytemuck::cast(arr))
822            }
823        }
824
825        $crate::algebra::field::binary::gf2_ext::impl_wide_mul!($ext_params, $limbs);
826
827        impl $crate::algebra::field::binary::gf2_ext::Gf2ExtParams for $ext_params {
828            type Degree = typenum::U<{ $limbs * 64 }>;
829            type Bytes = typenum::U<{ $limbs * 8 }>;
830            const POLY_MOD_ONES: &[usize] = &{ $modulus_poly_ones };
831        }
832    };
833}
834
835pub(crate) use define_gf2_extension;
836
837#[cfg(test)]
838mod tests {
839    use super::*;
840
841    const N_TESTS: usize = 1;
842
843    // sage instruction used to find minimal weight modulus polynomials:
844    //  GF(2^128, modulus="minimal_weight", name="x").polynomial()
845    define_gf2_extension!(Gf2_128, Gf2_128Params, 2, [1, 2, 7]);
846    define_gf2_extension!(Gf2_192, Gf2_192Params, 3, [1, 2, 7]);
847    define_gf2_extension!(Gf2_256, Gf2_256Params, 4, [2, 5, 10]);
848    define_gf2_extension!(Gf2_64, Gf2_64Params, 1, [1, 3, 4]);
849
850    #[test]
851    fn test_gf2_ext_operations() {
852        fn gf2_operations_test_case<F: FieldExtension>() {
853            let mut rng = crate::random::test_rng();
854            for _ in 0..N_TESTS {
855                let a = F::random(&mut rng);
856                // a + a = 0
857                assert_eq!(a + a, F::ZERO);
858
859                // a * 234 = 234 * a
860                assert_eq!(a * F::from(234u64), F::from(234u64) * a);
861
862                // a * (a + 234) = a * a + 234 * a
863                assert_eq!(a * (a + F::from(234u64)), a * a + F::from(234u64) * a);
864
865                // a exp (2^degree) = a
866                let mut cumul = a;
867                for _ in 0..(F::Degree::to_usize()) {
868                    cumul *= cumul;
869                }
870                assert_eq!(a, cumul);
871            }
872        }
873
874        gf2_operations_test_case::<Gf2_128>();
875        gf2_operations_test_case::<Gf2_256>();
876        gf2_operations_test_case::<Gf2_192>();
877        gf2_operations_test_case::<Gf2_64>();
878    }
879
880    #[test]
881    fn test_gf2_128_prod() {
882        macro_rules! gf2_128_prod_test_case {
883            ($aval:expr, $bval:expr, $prod_red:expr) => {{
884                let a: [u64; 2] = $aval;
885                let b: [u64; 2] = $bval;
886                let prod_red: [u64; 2] = $prod_red;
887
888                {
889                    let ae = Gf2_128::from_limbs(a);
890                    let be = Gf2_128::from_limbs(b);
891                    let prod_red_comp = ae * be;
892                    assert_eq!(prod_red_comp, Gf2_128::from_limbs(prod_red));
893                }
894            }};
895        }
896
897        gf2_128_prod_test_case!(
898            [0x9f418f3bffd84bba, 0x4a7c605645afdfb1],
899            [0x80b7bd91cddc5be5, 0x3a97291035e41e1f],
900            [0x46ca0b600a32c5f7, 0x823a605e0452082a]
901        );
902
903        gf2_128_prod_test_case!(
904            [0x74ef862bc1b6d333, 0x3a88103b80d97b73],
905            [0x753f4846eb020b5a, 0x8f108359ea25fa8f],
906            [0x6947ab52b94f0ef9, 0xb2ec1b5a4553aa6d]
907        );
908
909        gf2_128_prod_test_case!(
910            [0x6447b3dcaed62649, 0x6e4af40b2ee1b4c1],
911            [0xbd7a4e12fdb29840, 0x8950f56742015f25],
912            [0x38ae5eb860021fe9, 0x6f18457f05ac2506]
913        );
914    }
915}
primitives/algebra/field/binary/gf2_ext.rs

primitives/algebra/field/binary/
gf2_ext.rs
