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

primitives/algebra/field/binary/
gf2_ext.rs
