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
263impl<P: Gf2ExtParams, const LIMBS: usize> Neg for &Gf2Ext<P, LIMBS> {
264    type Output = Gf2Ext<P, LIMBS>;
265
266    #[inline]
267    fn neg(self) -> Self::Output {
268        *self
269    }
270}
271
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
281impl<P: Gf2ExtParams, const LIMBS: usize> Add<&Gf2Ext<P, LIMBS>> for &Gf2Ext<P, LIMBS> {
282    type Output = Gf2Ext<P, LIMBS>;
283
284    #[inline]
285    fn add(self, rhs: &Self::Output) -> Self::Output {
286        let mut res = *self;
287        res += rhs;
288        res
289    }
290}
291
292impl<P: Gf2ExtParams, const LIMBS: usize> Add<&Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS> {
293    type Output = Gf2Ext<P, LIMBS>;
294
295    #[inline]
296    #[allow(clippy::op_ref)]
297    fn add(mut self, rhs: &Self::Output) -> Self::Output {
298        self += rhs;
299        self
300    }
301}
302
303impl<P: Gf2ExtParams, const LIMBS: usize> Add<Gf2Ext<P, LIMBS>> for &Gf2Ext<P, LIMBS> {
304    type Output = Gf2Ext<P, LIMBS>;
305
306    #[inline]
307    fn add(self, rhs: Self::Output) -> Self::Output {
308        rhs + self
309    }
310}
311
312impl<P: Gf2ExtParams, const LIMBS: usize> Add for Gf2Ext<P, LIMBS> {
313    type Output = Gf2Ext<P, LIMBS>;
314
315    #[inline]
316    #[allow(clippy::op_ref)]
317    fn add(self, rhs: Self::Output) -> Self::Output {
318        self + &rhs
319    }
320}
321
322impl<P: Gf2ExtParams, const LIMBS: usize> AddAssign for Gf2Ext<P, LIMBS> {
323    #[inline]
324    fn add_assign(&mut self, rhs: Self) {
325        *self += &rhs;
326    }
327}
328
329impl<P: Gf2ExtParams, const LIMBS: usize> AddAssign<&Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS> {
330    #[allow(clippy::suspicious_op_assign_impl)]
331    fn add_assign(&mut self, rhs: &Self) {
332        izip!(&mut self.data, rhs.data).for_each(|(a, b)| *a ^= b);
333    }
334}
335
336impl<P: Gf2ExtParams, const LIMBS: usize> Sub<&Gf2Ext<P, LIMBS>> for &Gf2Ext<P, LIMBS> {
337    type Output = Gf2Ext<P, LIMBS>;
338
339    #[inline]
340    #[allow(clippy::suspicious_arithmetic_impl)]
341    fn sub(self, rhs: &Self::Output) -> Self::Output {
342        self + rhs
343    }
344}
345
346impl<P: Gf2ExtParams, const LIMBS: usize> Sub<&Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS> {
347    type Output = Gf2Ext<P, LIMBS>;
348
349    #[inline]
350    #[allow(clippy::suspicious_arithmetic_impl)]
351    fn sub(self, rhs: &Self::Output) -> Self::Output {
352        self + rhs
353    }
354}
355
356impl<P: Gf2ExtParams, const LIMBS: usize> Sub<Gf2Ext<P, LIMBS>> for &Gf2Ext<P, LIMBS> {
357    type Output = Gf2Ext<P, LIMBS>;
358
359    #[inline]
360    #[allow(clippy::suspicious_arithmetic_impl)]
361    fn sub(self, rhs: Self::Output) -> Self::Output {
362        self + rhs
363    }
364}
365
366impl<P: Gf2ExtParams, const LIMBS: usize> Sub for Gf2Ext<P, LIMBS> {
367    type Output = Gf2Ext<P, LIMBS>;
368
369    #[inline]
370    #[allow(clippy::suspicious_arithmetic_impl)]
371    fn sub(self, rhs: Self::Output) -> Self::Output {
372        self + rhs
373    }
374}
375
376impl<P: Gf2ExtParams, const LIMBS: usize> SubAssign for Gf2Ext<P, LIMBS> {
377    #[inline]
378    #[allow(clippy::suspicious_op_assign_impl)]
379    fn sub_assign(&mut self, rhs: Self) {
380        *self += rhs;
381    }
382}
383
384impl<P: Gf2ExtParams, const LIMBS: usize> SubAssign<&Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS> {
385    #[inline]
386    #[allow(clippy::suspicious_op_assign_impl)]
387    fn sub_assign(&mut self, rhs: &Self) {
388        *self += rhs;
389    }
390}
391
392impl<P: Gf2ExtParams, const LIMBS: usize> Mul<&Gf2Ext<P, LIMBS>> for &Gf2Ext<P, LIMBS>
393where
394    Gf2Ext<P, LIMBS>: MulWide<Output = Gf2LimbsWide<LIMBS>>,
395{
396    type Output = Gf2Ext<P, LIMBS>;
397
398    #[inline]
399    fn mul(self, rhs: &Gf2Ext<P, LIMBS>) -> Self::Output {
400        let mut tmp = *self;
401        tmp *= rhs;
402        tmp
403    }
404}
405
406impl<P: Gf2ExtParams, const LIMBS: usize> Mul<&Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS>
407where
408    Gf2Ext<P, LIMBS>: MulWide<Output = Gf2LimbsWide<LIMBS>>,
409{
410    type Output = Gf2Ext<P, LIMBS>;
411
412    #[inline]
413    fn mul(mut self, rhs: &Self::Output) -> Self::Output {
414        self *= rhs;
415        self
416    }
417}
418
419impl<P: Gf2ExtParams, const LIMBS: usize> Mul<Gf2Ext<P, LIMBS>> for &Gf2Ext<P, LIMBS>
420where
421    Gf2Ext<P, LIMBS>: MulWide<Output = Gf2LimbsWide<LIMBS>>,
422{
423    type Output = Gf2Ext<P, LIMBS>;
424
425    #[inline]
426    fn mul(self, rhs: Self::Output) -> Self::Output {
427        rhs * self
428    }
429}
430
431impl<P: Gf2ExtParams, const LIMBS: usize> Mul for Gf2Ext<P, LIMBS>
432where
433    Gf2Ext<P, LIMBS>: MulWide<Output = Gf2LimbsWide<LIMBS>>,
434{
435    type Output = Gf2Ext<P, LIMBS>;
436
437    #[inline]
438    #[allow(clippy::op_ref)]
439    fn mul(self, rhs: Self::Output) -> Self::Output {
440        self * &rhs
441    }
442}
443
444impl<P: Gf2ExtParams, const LIMBS: usize> MulAssign<&Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS>
445where
446    Gf2Ext<P, LIMBS>: MulAssign,
447{
448    #[inline]
449    fn mul_assign(&mut self, rhs: &Gf2Ext<P, LIMBS>) {
450        *self *= *rhs;
451    }
452}
453
454impl<P: Gf2ExtParams, const LIMBS: usize> MulAssign<Gf2> for Gf2Ext<P, LIMBS>
455where
456    Gf2Ext<P, LIMBS>: MulAssign,
457{
458    #[inline]
459    fn mul_assign(&mut self, rhs: Gf2) {
460        self.data
461            .iter_mut()
462            .for_each(|limb: &mut u64| *limb *= rhs.0 as u64)
463    }
464}
465
466impl<P: Gf2ExtParams, const LIMBS: usize> MulAssign<&Gf2> for Gf2Ext<P, LIMBS>
467where
468    Gf2Ext<P, LIMBS>: MulAssign,
469{
470    #[inline]
471    fn mul_assign(&mut self, rhs: &Gf2) {
472        self.data
473            .iter_mut()
474            .for_each(|limb: &mut u64| *limb *= rhs.0 as u64)
475    }
476}
477
478impl<P: Gf2ExtParams, const LIMBS: usize> MulAssign for Gf2Ext<P, LIMBS>
479where
480    Gf2Ext<P, LIMBS>: MulWide<Output = Gf2LimbsWide<LIMBS>>,
481    Gf2Ext<P, LIMBS>: IntoWide<Gf2LimbsWide<LIMBS>>,
482{
483    fn mul_assign(&mut self, rhs: Self) {
484        let res_wide = self.mul_wide(rhs);
485        *self = Self::reduce_mod_order(res_wide)
486    }
487}
488
489impl<P: Gf2ExtParams, const LIMBS: usize> Sum for Gf2Ext<P, LIMBS> {
490    #[inline]
491    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
492        iter.fold(Gf2Ext::ZERO, |a, b| a + b)
493    }
494}
495
496impl<'a, P: Gf2ExtParams, const LIMBS: usize> Sum<&'a Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS> {
497    #[inline]
498    fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
499        iter.fold(Gf2Ext::ZERO, |a, b| a + b)
500    }
501}
502
503impl<P: Gf2ExtParams, const LIMBS: usize> Product for Gf2Ext<P, LIMBS>
504where
505    Gf2Ext<P, LIMBS>: MulWide<Output = Gf2LimbsWide<LIMBS>>,
506{
507    #[inline]
508    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
509        iter.fold(Gf2Ext::ONE, |a, b| a * b)
510    }
511}
512
513impl<'a, P: Gf2ExtParams, const LIMBS: usize> Product<&'a Gf2Ext<P, LIMBS>> for Gf2Ext<P, LIMBS>
514where
515    Gf2Ext<P, LIMBS>: MulWide<Output = Gf2LimbsWide<LIMBS>>,
516{
517    #[inline]
518    fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
519        iter.fold(Gf2Ext::ONE, |a, b| a * b)
520    }
521}
522
523// === Implementation of FieldExtension trait methods
524impl<P: Gf2ExtParams, const LIMBS: usize> FieldExtension for Gf2Ext<P, LIMBS>
525where
526    Gf2Ext<P, LIMBS>: MulWide<Output = Gf2LimbsWide<LIMBS>>,
527    [u8; LIMBS]: AssocArraySize,
528    <[u8; LIMBS] as AssocArraySize>::Size: ArraySize + Positive + Mul<U8> + Mul<U64>,
529    Prod<<[u8; LIMBS] as AssocArraySize>::Size, U8>: ArraySize + Positive,
530    Prod<<[u8; LIMBS] as AssocArraySize>::Size, U64>: ArraySize + Positive,
531{
532    type Subfield = Gf2;
533
534    type Degree = P::Degree;
535    type FieldBitSize = Prod<<[u8; LIMBS] as AssocArraySize>::Size, U64>;
536    type FieldBytesSize = Prod<<[u8; LIMBS] as AssocArraySize>::Size, U8>;
537
538    fn to_subfield_elements(&self) -> impl ExactSizeIterator<Item = Self::Subfield> {
539        self.data.iter_lsb0().take(P::Degree::USIZE).map(Gf2::from)
540    }
541
542    fn from_subfield_elements(elems: &[Self::Subfield]) -> Option<Self> {
543        if elems.len() == P::Degree::to_usize() {
544            let mut iter = elems
545                .chunks_exact(64)
546                .map(|a| u64::from_lsb0_iter(a.iter().map(bool::from)));
547            Some(Self::new(std::array::from_fn(|_| iter.next().unwrap())))
548        } else {
549            None
550        }
551    }
552
553    fn to_le_bytes(&self) -> impl IntoIterator<Item = u8> {
554        (0..LIMBS)
555            .cartesian_product((0..64).step_by(8))
556            .map(|(limb, shift)| ((self.data[limb] >> shift) & 0xFF) as u8)
557    }
558
559    fn from_le_bytes(bytes: &[u8]) -> Option<Self> {
560        if bytes.len() != Self::FieldBytesSize::USIZE {
561            return None;
562        }
563
564        let mut it = bytes.chunks_exact(8).take(LIMBS);
565        Some(Self::new(std::array::from_fn(|_| {
566            u64::from_le_bytes(it.next().unwrap().try_into().unwrap())
567        })))
568    }
569
570    fn mul_by_subfield(&self, other: &Self::Subfield) -> Self {
571        *self * other
572    }
573
574    fn generator() -> Self {
575        Self::from_u64(2u64) // encoding of variable X
576    }
577
578    // ** Note: ** Starting from N = 256 the performance gains are minor
579    fn random_elements<M: Positive>(mut rng: impl RngCore) -> HeapArray<Self, M> {
580        let mut buf = HeapArray::<Self, M>::default().into_box_bytes();
581        rng.fill_bytes(&mut buf);
582        HeapArray::from_box_bytes(buf)
583    }
584
585    // Fast linear-orthomorphism for GF2 extensions of even degrees from "Minimizing the Two-Round
586    // Even-Mansour Cipher" by Chen et al.
587    fn linear_orthomorphism(&self) -> Self {
588        let mut res = Self::default();
589        for i in 0..LIMBS / 2 {
590            res.data[i] = self.data[i] ^ self.data[LIMBS - i - 1];
591            res.data[LIMBS - i - 1] = self.data[i];
592        }
593        if LIMBS % 2 == 1 {
594            let k = LIMBS / 2 + 1;
595            let (tl, th) = (self.data[k] as u32, (self.data[k] >> 32) as u32);
596
597            let (rl, rh) = (tl ^ th, tl);
598            res.data[k] = rl as u64 + ((rh as u64) << 32);
599        }
600
601        res
602    }
603}
604
605unsafe impl<P: Gf2ExtParams, const LIMBS: usize> bytemuck::Zeroable for Gf2Ext<P, LIMBS> {
606    fn zeroed() -> Self {
607        Self::ZERO
608    }
609}
610unsafe impl<P: Gf2ExtParams, const LIMBS: usize> bytemuck::Pod for Gf2Ext<P, LIMBS> {}
611
612impl<P: Gf2ExtParams, const LIMBS: usize> Add<Gf2> for Gf2Ext<P, LIMBS> {
613    type Output = Self;
614
615    #[allow(clippy::suspicious_arithmetic_impl)]
616    fn add(mut self, rhs: Gf2) -> Self::Output {
617        // Transform 0/1 value into a bit-mask 00..0/11..1
618        let m = (-(rhs.0 as i64)) as u64;
619        self.data.iter_mut().for_each(|v: &mut u64| *v ^= m);
620        self
621    }
622}
623
624impl<'a, P: Gf2ExtParams, const LIMBS: usize> Add<&'a Gf2> for Gf2Ext<P, LIMBS> {
625    type Output = Self;
626
627    #[inline]
628    fn add(self, rhs: &'a Gf2) -> Self::Output {
629        self + *rhs
630    }
631}
632
633impl<P: Gf2ExtParams, const LIMBS: usize> Mul<Gf2> for Gf2Ext<P, LIMBS> {
634    type Output = Self;
635
636    #[allow(clippy::suspicious_arithmetic_impl)]
637    fn mul(mut self, rhs: Gf2) -> Self::Output {
638        // Transform 0/1 value into a bit-mask 00..0/11..1
639        let m = (-(rhs.0 as i64)) as u64;
640        self.data.iter_mut().for_each(|v: &mut u64| *v &= m);
641        self
642    }
643}
644
645impl<'a, P: Gf2ExtParams, const LIMBS: usize> Mul<&'a Gf2> for Gf2Ext<P, LIMBS> {
646    type Output = Self;
647
648    #[inline]
649    fn mul(self, rhs: &'a Gf2) -> Self::Output {
650        self * *rhs
651    }
652}
653
654// Lazy multiplication and modulus reduction
655
656/// Add gf2 polynomials encoded in Gf2LimbsWide<LIMBS>
657impl<const LIMBS: usize> AddAssign for Gf2LimbsWide<LIMBS> {
658    fn add_assign(&mut self, rhs: Self) {
659        izip!(&mut self.low, rhs.low).for_each(|(a, b)| *a ^= b);
660        izip!(&mut self.high, rhs.high).for_each(|(a, b)| *a ^= b);
661    }
662}
663
664// Wide type for Gf2Ext x Gf2Ext multiplication
665impl<P: Gf2ExtParams, const LIMBS: usize> IntoWide<Gf2LimbsWide<LIMBS>> for Gf2Ext<P, LIMBS> {
666    #[inline]
667    fn to_wide(&self) -> Gf2LimbsWide<LIMBS> {
668        Gf2LimbsWide {
669            low: self.data,
670            high: [0u64; LIMBS],
671        }
672    }
673
674    #[inline]
675    fn zero_wide() -> Gf2LimbsWide<LIMBS> {
676        Default::default()
677    }
678}
679
680impl<P: Gf2ExtParams, const LIMBS: usize> ReduceWide<Gf2LimbsWide<LIMBS>> for Gf2Ext<P, LIMBS> {
681    /// Reduce a GF2 polynomial of 2*LIMBS down to LIMBS.
682    /// * `poly` - polynomial to reduce
683    fn reduce_mod_order(a: Gf2LimbsWide<LIMBS>) -> Self {
684        let Gf2LimbsWide { mut low, mut high } = a;
685
686        let ones = P::POLY_MOD_ONES;
687
688        // Use a macro (instead of a function) to avoid rust borrowing rules in case `$inp` aliases
689        // with `$out_high`
690        macro_rules! reduce_1step {
691            ($out_low:expr, $out_high:expr, $inp:expr) => {
692                for k in ones {
693                    $out_high ^= $inp >> (64 - k);
694                }
695                $out_low ^= $inp;
696                for k in ones {
697                    $out_low ^= $inp << k;
698                }
699            };
700        }
701
702        reduce_1step!(low[LIMBS - 1], high[0], high[LIMBS - 1]);
703        for i in (0..LIMBS - 1).rev() {
704            reduce_1step!(low[i], low[i + 1], high[i]);
705        }
706
707        Gf2Ext {
708            data: low,
709            _id: PhantomData,
710        }
711    }
712}
713
714// Dot product: Gf2Ext x Gf2Ext
715impl<P: Gf2ExtParams, const LIMBS: usize> MulAccReduce for Gf2Ext<P, LIMBS>
716where
717    Self: MulWide<Output = Gf2LimbsWide<LIMBS>>,
718{
719    type WideType = Gf2LimbsWide<LIMBS>;
720
721    #[inline]
722    fn mul_acc(acc: &mut Self::WideType, a: Self, b: Self) {
723        *acc += a.mul_wide(b)
724    }
725}
726
727impl<P: Gf2ExtParams, const LIMBS: usize> DefaultDotProduct for Gf2Ext<P, LIMBS> where
728    Self: MulAccReduce
729{
730}
731
732// Dot product: Gf2Ext x &Gf2Ext
733impl<'a, P: Gf2ExtParams, const LIMBS: usize> DotProduct<Self, &'a Self> for Gf2Ext<P, LIMBS>
734where
735    Self: DefaultDotProduct,
736{
737    #[inline]
738    fn dot<I1, I2>(a: I1, b: I2) -> Self
739    where
740        I1: IntoExactSizeIterator<Item = Self>,
741        I2: IntoExactSizeIterator<Item = &'a Self>,
742    {
743        Self::dot(a, b.into_iter().copied())
744    }
745}
746
747// Dot product: &Gf2Ext x &Gf2Ext
748impl<'a, 'b, P: Gf2ExtParams, const LIMBS: usize> DotProduct<&'a Self, &'b Self>
749    for Gf2Ext<P, LIMBS>
750where
751    Self: DefaultDotProduct,
752{
753    #[inline]
754    fn dot<I1, I2>(a: I1, b: I2) -> Self
755    where
756        I1: IntoExactSizeIterator<Item = &'a Self>,
757        I2: IntoExactSizeIterator<Item = &'b Self>,
758    {
759        Self::dot(a.into_iter().copied(), b)
760    }
761}
762
763impl<P: Gf2ExtParams, const LIMBS: usize> IntoWide for Gf2Ext<P, LIMBS> {
764    #[inline]
765    fn to_wide(&self) -> Self {
766        *self
767    }
768
769    #[inline]
770    fn zero_wide() -> Self {
771        <Self as IntoWide>::to_wide(&Self::ZERO)
772    }
773}
774
775impl<P: Gf2ExtParams, const LIMBS: usize> ReduceWide for Gf2Ext<P, LIMBS> {
776    #[inline]
777    fn reduce_mod_order(a: Self) -> Self {
778        a
779    }
780}
781
782// Dot product : Gf2Ext, Gf2
783impl<P: Gf2ExtParams, const LIMBS: usize> MulAccReduce<Self, Gf2> for Gf2Ext<P, LIMBS> {
784    type WideType = Self;
785
786    #[inline]
787    fn mul_acc(acc: &mut Self, a: Self, b: Gf2) {
788        *acc += a * b;
789    }
790}
791
792impl<P: Gf2ExtParams, const LIMBS: usize> DefaultDotProduct<Self, Gf2> for Gf2Ext<P, LIMBS> {}
793
794// Dot product : &Gf2Ext, Gf2
795impl<'a, P: Gf2ExtParams, const LIMBS: usize> MulAccReduce<&'a Self, Gf2> for Gf2Ext<P, LIMBS> {
796    type WideType = Self;
797
798    #[inline]
799    fn mul_acc(acc: &mut Self, a: &'a Self, b: Gf2) {
800        Self::mul_acc(acc, *a, b);
801    }
802}
803
804impl<P: Gf2ExtParams, const LIMBS: usize> DefaultDotProduct<&Self, Gf2> for Gf2Ext<P, LIMBS> {}
805
806// Dot product : &Gf2Ext, &Gf2
807impl<'a, 'b, P: Gf2ExtParams, const LIMBS: usize> MulAccReduce<&'a Self, &'b Gf2>
808    for Gf2Ext<P, LIMBS>
809{
810    type WideType = Self;
811
812    #[inline]
813    fn mul_acc(acc: &mut Self, a: &'a Self, b: &'b Gf2) {
814        Self::mul_acc(acc, a, *b);
815    }
816}
817
818impl<P: Gf2ExtParams, const LIMBS: usize> DefaultDotProduct<&Self, &Gf2> for Gf2Ext<P, LIMBS> {}
819
820impl<P: Gf2ExtParams, const LIMBS: usize> AccReduce for Gf2Ext<P, LIMBS> {
821    type WideType = Self;
822
823    fn acc(acc: &mut Self, a: Self) {
824        *acc += a;
825    }
826}
827
828impl<P: Gf2ExtParams, const LIMBS: usize> AccReduce<&Self> for Gf2Ext<P, LIMBS> {
829    type WideType = Self;
830
831    fn acc(acc: &mut Self, a: &Self) {
832        *acc += a;
833    }
834}
835
836pub trait MulWide<Rhs = Self> {
837    type Output;
838    fn mul_wide(self, rhs: Rhs) -> Self::Output;
839}
840
841impl<P: Gf2ExtParams, const LIMBS: usize> FromUniformBytes for Gf2Ext<P, LIMBS>
842where
843    [u8; LIMBS]: AssocArraySize,
844    <[u8; LIMBS] as AssocArraySize>::Size: ArraySize + Positive + Mul<U8> + Mul<U64>,
845    Prod<<[u8; LIMBS] as AssocArraySize>::Size, U8>: ArraySize + Positive,
846{
847    type UniformBytes = Prod<<[u8; LIMBS] as AssocArraySize>::Size, U8>;
848
849    fn from_uniform_bytes(a: &Array<u8, Self::UniformBytes>) -> Self {
850        let mut it = a.chunks_exact(8).take(LIMBS);
851        Self::new(std::array::from_fn(|_| {
852            u64::from_le_bytes(it.next().unwrap().try_into().unwrap())
853        }))
854    }
855}
856
857// statically dispatch size-dependent MulWide implementation
858macro_rules! impl_wide_mul {
859    ($params:ty, 1) => {
860        impl $crate::algebra::field::binary::gf2_ext::MulWide for Gf2Ext<$params, 1> {
861            type Output = Gf2LimbsWide<1>;
862            fn mul_wide(self, rhs: Self) -> Self::Output {
863                let (low, high) =
864                    $crate::algebra::ops::clmul::carry_less_mul_1limb(self.data, rhs.data);
865                Gf2LimbsWide { low, high }
866            }
867        }
868    };
869    ($params:ty, 2) => {
870        impl $crate::algebra::field::binary::gf2_ext::MulWide for Gf2Ext<$params, 2> {
871            type Output = Gf2LimbsWide<2>;
872            fn mul_wide(self, rhs: Self) -> Self::Output {
873                let (low, high) =
874                    $crate::algebra::ops::clmul::carry_less_mul_2limbs(self.data, rhs.data);
875                Gf2LimbsWide { low, high }
876            }
877        }
878    };
879    ($params:ty, $limbs:literal) => {
880        impl $crate::algebra::field::binary::gf2_ext::MulWide for Gf2Ext<$params, $limbs> {
881            type Output = Gf2LimbsWide<$limbs>;
882            fn mul_wide(self, rhs: Self) -> Self::Output {
883                let (low, high) = $crate::algebra::ops::clmul::carry_less_mul(self.data, rhs.data);
884                Gf2LimbsWide { low, high }
885            }
886        }
887    };
888}
889pub(crate) use impl_wide_mul;
890
891macro_rules! validate_modulus_poly_ones {
892    ([$($val:literal),+ $(,)?]) => ($(
893        static_assertions::const_assert!(($val < 64) & ($val > 0));
894    )*);
895}
896pub(crate) use validate_modulus_poly_ones;
897
898macro_rules! define_gf2_extension {
899    ($ext_name:ident, $ext_params:ident, $limbs:tt, $modulus_poly_ones:tt) => {
900        $crate::algebra::field::binary::gf2_ext::validate_modulus_poly_ones!($modulus_poly_ones);
901
902        #[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
903        pub struct $ext_params;
904
905        pub type $ext_name = $crate::algebra::field::binary::gf2_ext::Gf2Ext<$ext_params, $limbs>;
906
907        // Note: do not move to generic implementation
908        impl $ext_name {
909            /// Casts the field element to a core byte array
910            pub fn into_ne_bytes_array(self) -> [u8; { $limbs * 8 }] {
911                bytemuck::cast(self.data)
912            }
913
914            pub fn from_ne_bytes_array(arr: [u8; { $limbs * 8 }]) -> Self {
915                Self::new(bytemuck::cast(arr))
916            }
917        }
918
919        $crate::algebra::field::binary::gf2_ext::impl_wide_mul!($ext_params, $limbs);
920
921        impl $crate::algebra::field::binary::gf2_ext::Gf2ExtParams for $ext_params {
922            type Degree = typenum::U<{ $limbs * 64 }>;
923            type Bytes = typenum::U<{ $limbs * 8 }>;
924            const POLY_MOD_ONES: &[usize] = &{ $modulus_poly_ones };
925        }
926    };
927}
928
929pub(crate) use define_gf2_extension;
930
931#[cfg(test)]
932mod tests {
933    use super::*;
934
935    const N_TESTS: usize = 1;
936
937    // sage instruction used to find minimal weight modulus polynomials:
938    //  GF(2^128, modulus="minimal_weight", name="x").polynomial()
939    define_gf2_extension!(Gf2_128, Gf2_128Params, 2, [1, 2, 7]);
940    define_gf2_extension!(Gf2_192, Gf2_192Params, 3, [1, 2, 7]);
941    define_gf2_extension!(Gf2_256, Gf2_256Params, 4, [2, 5, 10]);
942    define_gf2_extension!(Gf2_64, Gf2_64Params, 1, [1, 3, 4]);
943
944    #[test]
945    fn test_gf2_ext_operations() {
946        fn gf2_operations_test_case<F: FieldExtension>() {
947            let mut rng = crate::random::test_rng();
948            for _ in 0..N_TESTS {
949                let a = F::random(&mut rng);
950                // a + a = 0
951                assert_eq!(a + a, F::ZERO);
952
953                // a * 234 = 234 * a
954                assert_eq!(a * F::from(234u64), F::from(234u64) * a);
955
956                // a * (a + 234) = a * a + 234 * a
957                assert_eq!(a * (a + F::from(234u64)), a * a + F::from(234u64) * a);
958
959                // a exp (2^degree) = a
960                let mut cumul = a;
961                for _ in 0..(F::Degree::to_usize()) {
962                    cumul *= cumul;
963                }
964                assert_eq!(a, cumul);
965            }
966        }
967
968        gf2_operations_test_case::<Gf2_128>();
969        gf2_operations_test_case::<Gf2_256>();
970        gf2_operations_test_case::<Gf2_192>();
971        gf2_operations_test_case::<Gf2_64>();
972    }
973
974    #[test]
975    fn test_gf2_128_prod() {
976        macro_rules! gf2_128_prod_test_case {
977            ($aval:expr, $bval:expr, $prod_red:expr) => {{
978                let a: [u64; 2] = $aval;
979                let b: [u64; 2] = $bval;
980                let prod_red: [u64; 2] = $prod_red;
981
982                {
983                    let ae = Gf2_128::from_limbs(a);
984                    let be = Gf2_128::from_limbs(b);
985                    let prod_red_comp = ae * be;
986                    assert_eq!(prod_red_comp, Gf2_128::from_limbs(prod_red));
987                }
988            }};
989        }
990
991        gf2_128_prod_test_case!(
992            [0x9f418f3bffd84bba, 0x4a7c605645afdfb1],
993            [0x80b7bd91cddc5be5, 0x3a97291035e41e1f],
994            [0x46ca0b600a32c5f7, 0x823a605e0452082a]
995        );
996
997        gf2_128_prod_test_case!(
998            [0x74ef862bc1b6d333, 0x3a88103b80d97b73],
999            [0x753f4846eb020b5a, 0x8f108359ea25fa8f],
1000            [0x6947ab52b94f0ef9, 0xb2ec1b5a4553aa6d]
1001        );
1002
1003        gf2_128_prod_test_case!(
1004            [0x6447b3dcaed62649, 0x6e4af40b2ee1b4c1],
1005            [0xbd7a4e12fdb29840, 0x8950f56742015f25],
1006            [0x38ae5eb860021fe9, 0x6f18457f05ac2506]
1007        );
1008    }
1009}
primitives/algebra/field/binary/gf2_ext.rs

primitives/algebra/field/binary/
gf2_ext.rs
