primitives/algebra/field/binary/
gf2_ext.rs

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

primitives/algebra/field/binary/
gf2_ext.rs
