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

lambdaworks_math/field/extensions/
cubic.rs
