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

primitives/algebra/field/binary/
gf2_ext.rs
