lambdaworks_math/field/extensions/
quadratic.rs

1use crate::field::element::FieldElement;
2use crate::field::errors::FieldError;
3use crate::field::traits::{IsField, IsSubFieldOf};
4use crate::traits::ByteConversion;
5use core::fmt::Debug;
6use core::marker::PhantomData;
7
8/// A general quadratic extension field over `F`
9/// with quadratic non residue `Q::residue()`
10#[derive(Debug, Clone, PartialEq, Eq)]
11pub struct QuadraticExtensionField<F, T>
12where
13    F: IsField,
14    T: HasQuadraticNonResidue<F>,
15{
16    field: PhantomData<F>,
17    non_residue: PhantomData<T>,
18}
19
20pub type QuadraticExtensionFieldElement<F, T> = FieldElement<QuadraticExtensionField<F, T>>;
21
22/// Trait to fix a quadratic non residue.
23/// Used to construct a quadratic extension field by adding
24/// a square root of `residue()`.
25/// If p is congruent to 3 modulo 4, then -1 is a quadractic non-residue
26/// and can be used here
27pub trait HasQuadraticNonResidue<F: IsField> {
28    fn residue() -> FieldElement<F>;
29}
30
31impl<F, Q> FieldElement<QuadraticExtensionField<F, Q>>
32where
33    F: IsField,
34    Q: Clone + Debug + HasQuadraticNonResidue<F>,
35{
36    pub fn conjugate(&self) -> Self {
37        let [a, b] = self.value();
38        Self::new([a.clone(), -b])
39    }
40}
41
42impl<F> ByteConversion for [FieldElement<F>; 2]
43where
44    F: IsField,
45{
46    #[cfg(feature = "alloc")]
47    fn to_bytes_be(&self) -> alloc::vec::Vec<u8> {
48        unimplemented!()
49    }
50
51    #[cfg(feature = "alloc")]
52    fn to_bytes_le(&self) -> alloc::vec::Vec<u8> {
53        unimplemented!()
54    }
55
56    fn from_bytes_be(_bytes: &[u8]) -> Result<Self, crate::errors::ByteConversionError>
57    where
58        Self: Sized,
59    {
60        unimplemented!()
61    }
62
63    fn from_bytes_le(_bytes: &[u8]) -> Result<Self, crate::errors::ByteConversionError>
64    where
65        Self: Sized,
66    {
67        unimplemented!()
68    }
69}
70
71impl<F, Q> IsField for QuadraticExtensionField<F, Q>
72where
73    F: IsField,
74    Q: Clone + Debug + HasQuadraticNonResidue<F>,
75{
76    type BaseType = [FieldElement<F>; 2];
77
78    /// Returns the component wise addition of `a` and `b`
79    fn add(a: &[FieldElement<F>; 2], b: &[FieldElement<F>; 2]) -> [FieldElement<F>; 2] {
80        [&a[0] + &b[0], &a[1] + &b[1]]
81    }
82
83    /// Returns the multiplication of `a` and `b` using the following
84    /// equation:
85    /// (a0 + a1 * t) * (b0 + b1 * t) = a0 * b0 + a1 * b1 * Q::residue() + (a0 * b1 + a1 * b0) * t
86    /// where `t.pow(2)` equals `Q::residue()`.
87    fn mul(a: &[FieldElement<F>; 2], b: &[FieldElement<F>; 2]) -> [FieldElement<F>; 2] {
88        let q = Q::residue();
89        let a0b0 = &a[0] * &b[0];
90        let a1b1 = &a[1] * &b[1];
91        let z = (&a[0] + &a[1]) * (&b[0] + &b[1]);
92        [&a0b0 + &a1b1 * q, z - a0b0 - a1b1]
93    }
94
95    fn square(a: &[FieldElement<F>; 2]) -> [FieldElement<F>; 2] {
96        let [a0, a1] = a;
97        let v0 = a0 * a1;
98        let c0 = (a0 + a1) * (a0 + Q::residue() * a1) - &v0 - Q::residue() * &v0;
99        let c1 = &v0 + &v0;
100        [c0, c1]
101    }
102
103    /// Returns the component wise subtraction of `a` and `b`
104    fn sub(a: &[FieldElement<F>; 2], b: &[FieldElement<F>; 2]) -> [FieldElement<F>; 2] {
105        [&a[0] - &b[0], &a[1] - &b[1]]
106    }
107
108    /// Returns the component wise negation of `a`
109    fn neg(a: &[FieldElement<F>; 2]) -> [FieldElement<F>; 2] {
110        [-&a[0], -&a[1]]
111    }
112
113    /// Returns the multiplicative inverse of `a`
114    /// This uses the equality `(a0 + a1 * t) * (a0 - a1 * t) = a0.pow(2) - a1.pow(2) * Q::residue()`
115    fn inv(a: &[FieldElement<F>; 2]) -> Result<[FieldElement<F>; 2], FieldError> {
116        let inv_norm = (a[0].pow(2_u64) - Q::residue() * a[1].pow(2_u64)).inv()?;
117        Ok([&a[0] * &inv_norm, -&a[1] * inv_norm])
118    }
119
120    /// Returns the division of `a` and `b`
121    fn div(
122        a: &[FieldElement<F>; 2],
123        b: &[FieldElement<F>; 2],
124    ) -> Result<[FieldElement<F>; 2], FieldError> {
125        let b_inv = &Self::inv(b).map_err(|_| FieldError::DivisionByZero)?;
126        Ok(<Self as IsField>::mul(a, b_inv))
127    }
128
129    /// Returns a boolean indicating whether `a` and `b` are equal component wise.
130    fn eq(a: &[FieldElement<F>; 2], b: &[FieldElement<F>; 2]) -> bool {
131        a[0] == b[0] && a[1] == b[1]
132    }
133
134    /// Returns the additive neutral element of the field extension.
135    fn zero() -> [FieldElement<F>; 2] {
136        [FieldElement::zero(), FieldElement::zero()]
137    }
138
139    /// Returns the multiplicative neutral element of the field extension.
140    fn one() -> [FieldElement<F>; 2] {
141        [FieldElement::one(), FieldElement::zero()]
142    }
143
144    /// Returns the element `x * 1` where 1 is the multiplicative neutral element.
145    fn from_u64(x: u64) -> Self::BaseType {
146        [FieldElement::from(x), FieldElement::zero()]
147    }
148
149    /// Takes as input an element of BaseType and returns the internal representation
150    /// of that element in the field.
151    /// Note: for this case this is simply the identity, because the components
152    /// already have correct representations.
153    fn from_base_type(x: [FieldElement<F>; 2]) -> [FieldElement<F>; 2] {
154        x
155    }
156}
157
158impl<F, Q> IsSubFieldOf<QuadraticExtensionField<F, Q>> for F
159where
160    F: IsField,
161    Q: Clone + Debug + HasQuadraticNonResidue<F>,
162{
163    fn mul(
164        a: &Self::BaseType,
165        b: &<QuadraticExtensionField<F, Q> as IsField>::BaseType,
166    ) -> <QuadraticExtensionField<F, Q> as IsField>::BaseType {
167        let c0 = FieldElement::from_raw(F::mul(a, b[0].value()));
168        let c1 = FieldElement::from_raw(F::mul(a, b[1].value()));
169        [c0, c1]
170    }
171
172    fn add(
173        a: &Self::BaseType,
174        b: &<QuadraticExtensionField<F, Q> as IsField>::BaseType,
175    ) -> <QuadraticExtensionField<F, Q> as IsField>::BaseType {
176        let c0 = FieldElement::from_raw(F::add(a, b[0].value()));
177        [c0, b[1].clone()]
178    }
179
180    fn div(
181        a: &Self::BaseType,
182        b: &<QuadraticExtensionField<F, Q> as IsField>::BaseType,
183    ) -> Result<<QuadraticExtensionField<F, Q> as IsField>::BaseType, FieldError> {
184        let b_inv = <QuadraticExtensionField<F, Q> as IsField>::inv(b)?;
185        Ok(<Self as IsSubFieldOf<QuadraticExtensionField<F, Q>>>::mul(
186            a, &b_inv,
187        ))
188    }
189
190    fn sub(
191        a: &Self::BaseType,
192        b: &<QuadraticExtensionField<F, Q> as IsField>::BaseType,
193    ) -> <QuadraticExtensionField<F, Q> as IsField>::BaseType {
194        let c0 = FieldElement::from_raw(F::sub(a, b[0].value()));
195        let c1 = FieldElement::from_raw(F::neg(b[1].value()));
196        [c0, c1]
197    }
198
199    fn embed(a: Self::BaseType) -> <QuadraticExtensionField<F, Q> as IsField>::BaseType {
200        [FieldElement::from_raw(a), FieldElement::zero()]
201    }
202
203    #[cfg(feature = "alloc")]
204    fn to_subfield_vec(
205        b: <QuadraticExtensionField<F, Q> as IsField>::BaseType,
206    ) -> alloc::vec::Vec<Self::BaseType> {
207        b.into_iter().map(|x| x.to_raw()).collect()
208    }
209}
210
211impl<F: IsField, Q: Clone + Debug + HasQuadraticNonResidue<F>>
212    FieldElement<QuadraticExtensionField<F, Q>>
213{
214}
215
216#[cfg(test)]
217mod tests {
218    use crate::field::fields::u64_prime_field::{U64FieldElement, U64PrimeField};
219
220    const ORDER_P: u64 = 59;
221
222    use super::*;
223
224    #[derive(Debug, Clone)]
225    struct MyQuadraticNonResidue;
226    impl HasQuadraticNonResidue<U64PrimeField<ORDER_P>> for MyQuadraticNonResidue {
227        fn residue() -> FieldElement<U64PrimeField<ORDER_P>> {
228            -FieldElement::one()
229        }
230    }
231
232    type FE = U64FieldElement<ORDER_P>;
233    type MyFieldExtensionBackend =
234        QuadraticExtensionField<U64PrimeField<ORDER_P>, MyQuadraticNonResidue>;
235    #[allow(clippy::upper_case_acronyms)]
236    type FEE = FieldElement<MyFieldExtensionBackend>;
237
238    #[test]
239    fn test_add_1() {
240        let a = FEE::new([FE::new(0), FE::new(3)]);
241        let b = FEE::new([-FE::new(2), FE::new(8)]);
242        let expected_result = FEE::new([FE::new(57), FE::new(11)]);
243        assert_eq!(a + b, expected_result);
244    }
245
246    #[test]
247    fn test_add_2() {
248        let a = FEE::new([FE::new(12), FE::new(5)]);
249        let b = FEE::new([-FE::new(4), FE::new(2)]);
250        let expected_result = FEE::new([FE::new(8), FE::new(7)]);
251        assert_eq!(a + b, expected_result);
252    }
253
254    #[test]
255    fn test_sub_1() {
256        let a = FEE::new([FE::new(0), FE::new(3)]);
257        let b = FEE::new([-FE::new(2), FE::new(8)]);
258        let expected_result = FEE::new([FE::new(2), FE::new(54)]);
259        assert_eq!(a - b, expected_result);
260    }
261
262    #[test]
263    fn test_sub_2() {
264        let a = FEE::new([FE::new(12), FE::new(5)]);
265        let b = FEE::new([-FE::new(4), FE::new(2)]);
266        let expected_result = FEE::new([FE::new(16), FE::new(3)]);
267        assert_eq!(a - b, expected_result);
268    }
269
270    #[test]
271    fn test_mul_1() {
272        let a = FEE::new([FE::new(0), FE::new(3)]);
273        let b = FEE::new([-FE::new(2), FE::new(8)]);
274        let expected_result = FEE::new([FE::new(35), FE::new(53)]);
275        assert_eq!(a * b, expected_result);
276    }
277
278    #[test]
279    fn test_mul_2() {
280        let a = FEE::new([FE::new(12), FE::new(5)]);
281        let b = FEE::new([-FE::new(4), FE::new(2)]);
282        let expected_result = FEE::new([FE::new(1), FE::new(4)]);
283        assert_eq!(a * b, expected_result);
284    }
285
286    #[test]
287    fn test_div_1() {
288        let a = FEE::new([FE::new(0), FE::new(3)]);
289        let b = FEE::new([-FE::new(2), FE::new(8)]);
290        let expected_result = FEE::new([FE::new(42), FE::new(19)]);
291        assert_eq!((a / b).unwrap(), expected_result);
292    }
293
294    #[test]
295    fn test_div_2() {
296        let a = FEE::new([FE::new(12), FE::new(5)]);
297        let b = FEE::new([-FE::new(4), FE::new(2)]);
298        let expected_result = FEE::new([FE::new(4), FE::new(45)]);
299        assert_eq!((a / b).unwrap(), expected_result);
300    }
301
302    #[test]
303    fn test_pow_1() {
304        let a = FEE::new([FE::new(0), FE::new(3)]);
305        let b: u64 = 5;
306        let expected_result = FEE::new([FE::new(0), FE::new(7)]);
307        assert_eq!(a.pow(b), expected_result);
308    }
309
310    #[test]
311    fn test_pow_2() {
312        let a = FEE::new([FE::new(12), FE::new(5)]);
313        let b: u64 = 8;
314        let expected_result = FEE::new([FE::new(52), FE::new(35)]);
315        assert_eq!(a.pow(b), expected_result);
316    }
317
318    #[test]
319    fn test_inv_1() {
320        let a = FEE::new([FE::new(0), FE::new(3)]);
321        let expected_result = FEE::new([FE::new(0), FE::new(39)]);
322        assert_eq!(a.inv().unwrap(), expected_result);
323    }
324
325    #[test]
326    fn test_inv() {
327        let a = FEE::new([FE::new(12), FE::new(5)]);
328        let expected_result = FEE::new([FE::new(28), FE::new(8)]);
329        assert_eq!(a.inv().unwrap(), expected_result);
330    }
331
332    #[test]
333    fn test_conjugate() {
334        let a = FEE::new([FE::new(12), FE::new(5)]);
335        let expected_result = FEE::new([FE::new(12), -FE::new(5)]);
336        assert_eq!(a.conjugate(), expected_result);
337    }
338
339    #[test]
340    fn test_add_as_subfield_1() {
341        let a = -FE::new(2);
342        let b = FEE::new([FE::new(0), FE::new(3)]);
343        let expected_result = FEE::new([FE::new(57), FE::new(3)]);
344        assert_eq!(a + b, expected_result);
345    }
346
347    #[test]
348    fn test_add_as_subfield_2() {
349        let a = -FE::new(4);
350        let b = FEE::new([FE::new(12), FE::new(5)]);
351        let expected_result = FEE::new([FE::new(8), FE::new(5)]);
352        assert_eq!(a + b, expected_result);
353    }
354
355    #[test]
356    fn test_sub_as_subfield_1() {
357        let a = FE::new(0);
358        let b = FEE::new([-FE::new(2), FE::new(8)]);
359        let expected_result = FEE::new([FE::new(2), FE::new(51)]);
360        assert_eq!(a - b, expected_result);
361    }
362
363    #[test]
364    fn test_sub_a_subfield_2() {
365        let a = FE::new(12);
366        let b = FEE::new([-FE::new(4), -FE::new(2)]);
367        let expected_result = FEE::new([FE::new(16), FE::new(2)]);
368        assert_eq!(a - b, expected_result);
369    }
370
371    #[test]
372    fn test_mul_as_subfield_1() {
373        let a = FE::new(2);
374        let b = FEE::new([-FE::new(2), FE::new(8)]);
375        let expected_result = FEE::new([FE::new(55), FE::new(16)]);
376        assert_eq!(a * b, expected_result);
377    }
378
379    #[test]
380    fn test_mul_as_subfield_2() {
381        let a = FE::new(12);
382        let b = FEE::new([-FE::new(4), FE::new(2)]);
383        let expected_result = FEE::new([FE::new(11), FE::new(24)]);
384        assert_eq!(a * b, expected_result);
385    }
386
387    #[test]
388    fn test_div_as_subfield_1() {
389        let a = FE::new(3);
390        let b = FEE::new([-FE::new(2), FE::new(8)]);
391        let expected_result = FEE::new([FE::new(19), FE::new(17)]);
392        assert_eq!((a / b).unwrap(), expected_result);
393    }
394
395    #[test]
396    fn test_div_as_subfield_2() {
397        let a = FE::new(22);
398        let b = FEE::new([FE::new(4), FE::new(2)]);
399        let expected_result = FEE::new([FE::new(28), FE::new(45)]);
400        assert_eq!((a / b).unwrap(), expected_result);
401    }
402}
lambdaworks_math/field/extensions/quadratic.rs

lambdaworks_math/field/extensions/
quadratic.rs
