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

primitives/algebra/field/binary/
gf2_ext.rs
