fp/
f2_element.rs

1//! Base binary field element $\mathbb{F}_2 = \mathbb{Z} /
2//! 2\mathbb{Z}$
3
4
5use crate::field_ops::FieldFromRepr;
6use crate::field_ops::{FieldOps, FieldRandom};
7use core::ops::{Add, Mul, Neg, Sub};
8use crypto_bigint::Uint;
9use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};
10
11/// Element of the finite field $\mathbb{F}_2$
12#[derive(Debug, Eq, PartialEq, Copy, Clone)]
13pub struct F2Element {
14    pub(crate) value: Uint<1>,
15}
16
17// ---------------------------------------------------------------------------
18// Constructors / accessors
19// ---------------------------------------------------------------------------
20
21impl F2Element {
22    /// The constant zero
23    pub const ZERO: Self = Self {
24        value: Uint::<1>::ZERO,
25    };
26
27    /// The constant one
28    pub const ONE: Self = Self {
29        value: Uint::<1>::ONE,
30    };
31
32    /// Create a new element of $\mathbb{F}_2$
33    fn new(x: Uint<1>) -> Self {
34        Self {
35            value: x & Uint::<1>::ONE,
36        }
37    }
38
39    /// Create a new element of $\mathbb{F}_2$ from a `u64`
40    pub fn from_u64(x: u64) -> Self {
41        Self::new(Uint::from(x & 1))
42    }
43
44    /// Get the `Uint<1>` from an element of $\mathbb{F}_2$
45    pub fn value(&self) -> Uint<1> {
46        self.value
47    }
48
49    /// Get the `u8` from an element of $\mathbb{F}_2$
50    pub fn as_u8(&self) -> u8 {
51        self.value.to_words()[0] as u8
52    }
53}
54
55// ---------------------------------------------------------------------------
56// CtOption functionalities
57// ---------------------------------------------------------------------------
58
59impl Default for F2Element {
60    fn default() -> Self {
61        Self::zero()
62    }
63}
64
65impl ConditionallySelectable for F2Element {
66    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
67        Self::new(Uint::<1>::conditional_select(&a.value, &b.value, choice))
68    }
69
70    fn conditional_assign(&mut self, other: &Self, choice: Choice) {
71        self.value.conditional_assign(&other.value, choice)
72    }
73
74    fn conditional_swap(a: &mut Self, b: &mut Self, choice: Choice) {
75        Uint::<1>::conditional_swap(&mut a.value, &mut b.value, choice)
76    }
77}
78
79impl ConstantTimeEq for F2Element {
80    fn ct_eq(&self, other: &Self) -> Choice {
81        Uint::<1>::ct_eq(&self.value, &other.value)
82    }
83
84    fn ct_ne(&self, other: &Self) -> Choice {
85        Uint::<1>::ct_ne(&self.value, &other.value)
86    }
87}
88
89// ---------------------------------------------------------------------------
90// Operator overloads
91// ---------------------------------------------------------------------------
92
93impl Add for F2Element {
94    type Output = Self;
95
96    fn add(self, rhs: Self) -> Self {
97        Self::new(self.value ^ rhs.value)
98    }
99}
100
101impl Sub for F2Element {
102    type Output = Self;
103
104    fn sub(self, rhs: Self) -> Self {
105        //subtraction = addition in F_2
106        Self::new(self.value ^ rhs.value)
107    }
108}
109
110impl Mul for F2Element {
111    type Output = Self;
112
113    fn mul(self, rhs: Self) -> Self {
114        Self::new(self.value & rhs.value)
115    }
116}
117
118impl Neg for F2Element {
119    type Output = Self;
120
121    fn neg(self) -> Self {
122        // x = -x for any x in F_2
123        self
124    }
125}
126
127// ---------------------------------------------------------------------------
128// FieldOps implementation
129// ---------------------------------------------------------------------------
130
131impl FieldOps for F2Element {
132    fn zero() -> Self {
133        Self::ZERO
134    }
135    fn one() -> Self {
136        Self::ONE
137    }
138
139    fn from_u64(x: u64) -> Self {
140        Self::from_u64(x)
141    }
142    fn is_zero(&self) -> Choice {
143        Self::ct_eq(self, &Self::zero())
144    }
145    fn is_one(&self) -> Choice {
146        Self::ct_eq(self, &Self::one())
147    }
148    fn negate(&self) -> Self {
149        *self
150    }
151    fn add(&self, rhs: &Self) -> Self {
152        Self::new(self.value ^ rhs.value)
153    }
154    fn sub(&self, rhs: &Self) -> Self {
155        Self::new(self.value ^ rhs.value)
156    }
157    fn mul(&self, rhs: &Self) -> Self {
158        Self::new(self.value & rhs.value)
159    }
160    fn square(&self) -> Self {
161        *self
162    } // x = x^2 for every x in F_2
163    fn double(&self) -> Self {
164        Self::ZERO
165    }
166    fn invert(&self) -> CtOption<Self> {
167        let is_invertible = !self.is_zero();
168        CtOption::new(*self, is_invertible)
169    }
170
171    fn frobenius(&self) -> Self {
172        *self
173    }
174    fn norm(&self) -> Self {
175        *self
176    }
177    fn trace(&self) -> Self {
178        *self
179    }
180
181    fn sqrt(&self) -> CtOption<Self> {
182        let is_non_zero = !self.is_zero();
183        CtOption::new(*self, is_non_zero)
184    }
185
186    fn legendre(&self) -> i8 {
187        self.as_u8() as i8
188    }
189
190    fn characteristic() -> Vec<u64> {
191        vec![2]
192    }
193    fn degree() -> u32 {
194        1
195    }
196}
197
198// ---------------------------------------------------------------------------
199// Pretty Display
200// ---------------------------------------------------------------------------
201
202impl std::fmt::Display for F2Element {
203    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
204        write!(f, "{}", self.as_u8())
205    }
206}
207
208// ---------------------------------------------------------------------------
209// Cryptographically secure random sampling
210// ---------------------------------------------------------------------------
211
212impl FieldRandom for F2Element {
213    fn random(rng: &mut (impl rand::CryptoRng + rand::Rng)) -> Self {
214        let bit = (rng.next_u32() & 1) as u64;
215        Self::from_u64(bit)
216    }
217}
218
219
220
221impl FieldFromRepr for F2Element {
222    type Repr = Uint<1>;
223
224    fn from_repr(x: Self::Repr) -> Self {
225        Self::new(x)
226    }
227}
fp/f2_element.rs

fp/
f2_element.rs
