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

primitives/algebra/field/binary/
gf2_ext.rs
