snarkvm_fields/
fp12_2over3over2.rs

1// Copyright 2024 Aleo Network Foundation
2// This file is part of the snarkVM library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7
8// http://www.apache.org/licenses/LICENSE-2.0
9
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16use crate::{Field, Fp2, Fp2Parameters, One, Zero, fp6_3over2::*};
17use snarkvm_utilities::{FromBytes, ToBits, ToBytes, bititerator::BitIteratorBE, rand::Uniform, serialize::*};
18
19use rand::{
20    Rng,
21    distributions::{Distribution, Standard},
22};
23use serde::{Deserialize, Serialize};
24use std::{
25    cmp::Ordering,
26    fmt::Debug,
27    hash::Hash,
28    io::{Read, Result as IoResult, Write},
29    ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign},
30};
31
32pub trait Fp12Parameters: 'static + Copy + Clone + Debug + Default + PartialEq + Eq + Hash + Send + Sync {
33    type Fp6Params: Fp6Parameters;
34
35    /// Coefficients for the Frobenius automorphism.
36    const FROBENIUS_COEFF_FP12_C1: [Fp2<Fp2Params<Self>>; 12];
37}
38
39type Fp2Params<P> = <<P as Fp12Parameters>::Fp6Params as Fp6Parameters>::Fp2Params;
40
41/// An element of Fp12, represented by c0 + c1 * v
42#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, Hash, Serialize, Deserialize)]
43pub struct Fp12<P: Fp12Parameters> {
44    pub c0: Fp6<P::Fp6Params>,
45    pub c1: Fp6<P::Fp6Params>,
46}
47
48impl<P: Fp12Parameters> Fp12<P> {
49    /// Initializes an element of `Fp12` from two `Fp6` elements.
50    pub const fn new(c0: Fp6<P::Fp6Params>, c1: Fp6<P::Fp6Params>) -> Self {
51        Self { c0, c1 }
52    }
53}
54
55impl<P: Fp12Parameters> Fp12<P> {
56    pub fn conjugate(&mut self) {
57        self.c1 = self.c1.neg();
58    }
59
60    pub fn mul_by_fp(&mut self, element: &<<P::Fp6Params as Fp6Parameters>::Fp2Params as Fp2Parameters>::Fp) {
61        self.c0.mul_by_fp(element);
62        self.c1.mul_by_fp(element);
63    }
64
65    /// Multiply by quadratic nonresidue v.
66    #[inline(always)]
67    pub(crate) fn mul_fp6_by_nonresidue(fe: &Fp6<P::Fp6Params>) -> Fp6<P::Fp6Params> {
68        let new_c0 = P::Fp6Params::mul_fp2_by_nonresidue(&fe.c2);
69        let new_c1 = fe.c0;
70        let new_c2 = fe.c1;
71        Fp6::new(new_c0, new_c1, new_c2)
72    }
73
74    pub fn mul_by_034(&mut self, c0: &Fp2<Fp2Params<P>>, c3: &Fp2<Fp2Params<P>>, c4: &Fp2<Fp2Params<P>>) {
75        let a0 = self.c0.c0 * c0;
76        let a1 = self.c0.c1 * c0;
77        let a2 = self.c0.c2 * c0;
78        let a = Fp6::new(a0, a1, a2);
79        let mut b = self.c1;
80        b.mul_by_01(c3, c4);
81
82        let c0 = *c0 + c3;
83        let c1 = c4;
84        let mut e = self.c0 + self.c1;
85        e.mul_by_01(&c0, c1);
86        self.c1 = e - (a + b);
87        self.c0 = a + Self::mul_fp6_by_nonresidue(&b);
88    }
89
90    pub fn mul_by_014(&mut self, c0: &Fp2<Fp2Params<P>>, c1: &Fp2<Fp2Params<P>>, c4: &Fp2<Fp2Params<P>>) {
91        let mut aa = self.c0;
92        aa.mul_by_01(c0, c1);
93        let mut bb = self.c1;
94        bb.mul_by_1(c4);
95        let mut o = *c1;
96        o.add_assign(c4);
97        self.c1.add_assign(self.c0);
98        self.c1.mul_by_01(c0, &o);
99        self.c1.sub_assign(&aa);
100        self.c1.sub_assign(&bb);
101        self.c0 = bb;
102        self.c0 = Self::mul_fp6_by_nonresidue(&self.c0);
103        self.c0.add_assign(aa);
104    }
105
106    pub fn cyclotomic_square(&self) -> Self {
107        let mut result = Self::zero();
108        let fp2_nr = <P::Fp6Params as Fp6Parameters>::mul_fp2_by_nonresidue;
109
110        let mut z0 = self.c0.c0;
111        let mut z4 = self.c0.c1;
112        let mut z3 = self.c0.c2;
113        let mut z2 = self.c1.c0;
114        let mut z1 = self.c1.c1;
115        let mut z5 = self.c1.c2;
116
117        // t0 + t1*y = (z0 + z1*y)^2 = a^2
118        let mut tmp = z0 * z1;
119        let t0 = (z0 + z1) * (z0 + fp2_nr(&z1)) - tmp - fp2_nr(&tmp);
120        let t1 = tmp.double();
121
122        // t2 + t3*y = (z2 + z3*y)^2 = b^2
123        tmp = z2 * z3;
124        let t2 = (z2 + z3) * (z2 + fp2_nr(&z3)) - tmp - fp2_nr(&tmp);
125        let t3 = tmp.double();
126
127        // t4 + t5*y = (z4 + z5*y)^2 = c^2
128        tmp = z4 * z5;
129        let t4 = (z4 + z5) * (z4 + fp2_nr(&z5)) - tmp - fp2_nr(&tmp);
130        let t5 = tmp.double();
131
132        // for A
133
134        // z0 = 3 * t0 - 2 * z0
135        z0 = t0 - z0;
136        z0 = z0 + z0;
137        result.c0.c0 = z0 + t0;
138
139        // z1 = 3 * t1 + 2 * z1
140        z1 = t1 + z1;
141        z1 = z1 + z1;
142        result.c1.c1 = z1 + t1;
143
144        // for B
145
146        // z2 = 3 * (xi * t5) + 2 * z2
147        tmp = fp2_nr(&t5);
148        z2 = tmp + z2;
149        z2 = z2 + z2;
150        result.c1.c0 = z2 + tmp;
151
152        // z3 = 3 * t4 - 2 * z3
153        z3 = t4 - z3;
154        z3 = z3 + z3;
155        result.c0.c2 = z3 + t4;
156
157        // for C
158
159        // z4 = 3 * t2 - 2 * z4
160        z4 = t2 - z4;
161        z4 = z4 + z4;
162        result.c0.c1 = z4 + t2;
163
164        // z5 = 3 * t3 + 2 * z5
165        z5 = t3 + z5;
166        z5 = z5 + z5;
167        result.c1.c2 = z5 + t3;
168
169        result
170    }
171
172    pub fn cyclotomic_exp<S: AsRef<[u64]>>(&self, exp: S) -> Self {
173        let mut res = Self::one();
174
175        let mut found_one = false;
176
177        for i in BitIteratorBE::new(exp) {
178            if !found_one {
179                if i {
180                    found_one = true;
181                } else {
182                    continue;
183                }
184            }
185
186            res = res.cyclotomic_square();
187
188            if i {
189                res *= self;
190            }
191        }
192        res
193    }
194}
195
196impl<P: Fp12Parameters> std::fmt::Display for Fp12<P> {
197    fn fmt(&self, f: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result {
198        write!(f, "Fp12({} + {} * w)", self.c0, self.c1)
199    }
200}
201
202impl<P: Fp12Parameters> Distribution<Fp12<P>> for Standard {
203    #[inline]
204    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Fp12<P> {
205        Fp12::new(Uniform::rand(rng), Uniform::rand(rng))
206    }
207}
208
209impl<P: Fp12Parameters> Zero for Fp12<P> {
210    fn zero() -> Self {
211        Self::new(Fp6::zero(), Fp6::zero())
212    }
213
214    fn is_zero(&self) -> bool {
215        self.c0.is_zero() && self.c1.is_zero()
216    }
217}
218
219impl<P: Fp12Parameters> One for Fp12<P> {
220    fn one() -> Self {
221        Self::new(Fp6::one(), Fp6::zero())
222    }
223
224    fn is_one(&self) -> bool {
225        self.c0.is_one() && self.c1.is_zero()
226    }
227}
228
229impl<P: Fp12Parameters> Field for Fp12<P> {
230    type BasePrimeField = <Fp6<P::Fp6Params> as Field>::BasePrimeField;
231
232    fn from_base_prime_field(other: Self::BasePrimeField) -> Self {
233        Self::new(Fp6::from_base_prime_field(other), Fp6::zero())
234    }
235
236    #[inline]
237    fn characteristic<'a>() -> &'a [u64] {
238        Fp6::<P::Fp6Params>::characteristic()
239    }
240
241    fn double(&self) -> Self {
242        let mut copy = *self;
243        copy.double_in_place();
244        copy
245    }
246
247    #[inline]
248    fn from_random_bytes_with_flags<F: Flags>(bytes: &[u8]) -> Option<(Self, F)> {
249        let split_at = bytes.len() / 2;
250        if let Some(c0) = Fp6::<P::Fp6Params>::from_random_bytes(&bytes[..split_at]) {
251            if let Some((c1, flags)) = Fp6::<P::Fp6Params>::from_random_bytes_with_flags::<F>(&bytes[split_at..]) {
252                return Some((Fp12::new(c0, c1), flags));
253            }
254        }
255        None
256    }
257
258    #[inline]
259    fn from_random_bytes(bytes: &[u8]) -> Option<Self> {
260        Self::from_random_bytes_with_flags::<EmptyFlags>(bytes).map(|f| f.0)
261    }
262
263    fn double_in_place(&mut self) {
264        self.c0.double_in_place();
265        self.c1.double_in_place();
266    }
267
268    fn frobenius_map(&mut self, power: usize) {
269        self.c0.frobenius_map(power);
270        self.c1.frobenius_map(power);
271
272        self.c1.c0.mul_assign(&P::FROBENIUS_COEFF_FP12_C1[power % 12]);
273        self.c1.c1.mul_assign(&P::FROBENIUS_COEFF_FP12_C1[power % 12]);
274        self.c1.c2.mul_assign(&P::FROBENIUS_COEFF_FP12_C1[power % 12]);
275    }
276
277    fn square(&self) -> Self {
278        let mut copy = *self;
279        copy.square_in_place();
280        copy
281    }
282
283    fn square_in_place(&mut self) -> &mut Self {
284        let mut ab = self.c0;
285        ab.mul_assign(&self.c1);
286        let mut c0c1 = self.c0;
287        c0c1.add_assign(self.c1);
288        let mut c0 = self.c1;
289        c0 = Self::mul_fp6_by_nonresidue(&c0);
290        c0.add_assign(self.c0);
291        c0.mul_assign(&c0c1);
292        c0.sub_assign(&ab);
293        self.c1 = ab;
294        self.c1.add_assign(ab);
295        ab = Self::mul_fp6_by_nonresidue(&ab);
296        c0.sub_assign(&ab);
297        self.c0 = c0;
298        self
299    }
300
301    fn inverse(&self) -> Option<Self> {
302        if self.is_zero() {
303            None
304        } else {
305            let mut c0s = self.c0;
306            c0s.square_in_place();
307            let mut c1s = self.c1;
308            c1s.square_in_place();
309            c1s = Self::mul_fp6_by_nonresidue(&c1s);
310            c0s.sub_assign(&c1s);
311
312            c0s.inverse().map(|t| {
313                let mut tmp = Fp12::new(t, t);
314                tmp.c0.mul_assign(&self.c0);
315                tmp.c1.mul_assign(&self.c1);
316                tmp.c1 = -tmp.c1;
317
318                tmp
319            })
320        }
321    }
322
323    fn inverse_in_place(&mut self) -> Option<&mut Self> {
324        match self.inverse() {
325            Some(inv) => {
326                *self = inv;
327                Some(self)
328            }
329            None => None,
330        }
331    }
332}
333
334impl<P: Fp12Parameters> Neg for Fp12<P> {
335    type Output = Self;
336
337    #[inline]
338    fn neg(self) -> Self {
339        let mut copy = Self::zero();
340        copy.c0 = self.c0.neg();
341        copy.c1 = self.c1.neg();
342        copy
343    }
344}
345
346impl_add_sub_from_field_ref!(Fp12, Fp12Parameters);
347impl_mul_div_from_field_ref!(Fp12, Fp12Parameters);
348
349impl<P: Fp12Parameters> Add<&'_ Self> for Fp12<P> {
350    type Output = Self;
351
352    #[inline]
353    fn add(self, other: &Self) -> Self {
354        let mut result = self;
355        result.add_assign(other);
356        result
357    }
358}
359
360impl<P: Fp12Parameters> Sub<&'_ Self> for Fp12<P> {
361    type Output = Self;
362
363    #[inline]
364    fn sub(self, other: &Self) -> Self {
365        let mut result = self;
366        result.sub_assign(&other);
367        result
368    }
369}
370
371impl<P: Fp12Parameters> Mul<&'_ Self> for Fp12<P> {
372    type Output = Self;
373
374    #[inline]
375    fn mul(self, other: &Self) -> Self {
376        let mut result = self;
377        result.mul_assign(&other);
378        result
379    }
380}
381
382impl<P: Fp12Parameters> Div<&'_ Self> for Fp12<P> {
383    type Output = Self;
384
385    #[inline]
386    fn div(self, other: &Self) -> Self {
387        let mut result = self;
388        result.mul_assign(&other.inverse().unwrap());
389        result
390    }
391}
392
393impl<P: Fp12Parameters> AddAssign<&'_ Self> for Fp12<P> {
394    #[inline]
395    fn add_assign(&mut self, other: &Self) {
396        self.c0.add_assign(other.c0);
397        self.c1.add_assign(other.c1);
398    }
399}
400
401impl<P: Fp12Parameters> SubAssign<&'_ Self> for Fp12<P> {
402    #[inline]
403    fn sub_assign(&mut self, other: &Self) {
404        self.c0.sub_assign(&other.c0);
405        self.c1.sub_assign(&other.c1);
406    }
407}
408
409impl<P: Fp12Parameters> MulAssign<&'_ Self> for Fp12<P> {
410    #[inline]
411    #[allow(clippy::suspicious_op_assign_impl)]
412    fn mul_assign(&mut self, other: &Self) {
413        let v0 = self.c0 * other.c0;
414        let v1 = self.c1 * other.c1;
415        self.c1 = (self.c0 + self.c1) * (other.c0 + other.c1) - v0 - v1;
416        self.c0 = v0 + Self::mul_fp6_by_nonresidue(&v1);
417    }
418}
419
420impl<P: Fp12Parameters> DivAssign<&'_ Self> for Fp12<P> {
421    #[inline]
422    fn div_assign(&mut self, other: &Self) {
423        self.mul_assign(&other.inverse().unwrap());
424    }
425}
426
427impl<P: Fp12Parameters> Ord for Fp12<P> {
428    #[inline(always)]
429    fn cmp(&self, other: &Self) -> Ordering {
430        let c1_cmp = self.c1.cmp(&other.c1);
431        if c1_cmp == Ordering::Equal { self.c0.cmp(&other.c0) } else { c1_cmp }
432    }
433}
434
435impl<P: Fp12Parameters> PartialOrd for Fp12<P> {
436    #[inline(always)]
437    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
438        Some(self.cmp(other))
439    }
440}
441
442impl<P: Fp12Parameters> From<u128> for Fp12<P> {
443    fn from(other: u128) -> Self {
444        Self::new(other.into(), Fp6::zero())
445    }
446}
447
448impl<P: Fp12Parameters> From<u64> for Fp12<P> {
449    fn from(other: u64) -> Self {
450        Self::new(other.into(), Fp6::zero())
451    }
452}
453
454impl<P: Fp12Parameters> From<u32> for Fp12<P> {
455    fn from(other: u32) -> Self {
456        Self::new(other.into(), Fp6::zero())
457    }
458}
459
460impl<P: Fp12Parameters> From<u16> for Fp12<P> {
461    fn from(other: u16) -> Self {
462        Self::new(other.into(), Fp6::zero())
463    }
464}
465
466impl<P: Fp12Parameters> From<u8> for Fp12<P> {
467    fn from(other: u8) -> Self {
468        Self::new(other.into(), Fp6::zero())
469    }
470}
471
472impl<P: Fp12Parameters> ToBits for Fp12<P> {
473    fn write_bits_le(&self, vec: &mut Vec<bool>) {
474        self.c0.write_bits_le(vec);
475        self.c1.write_bits_le(vec);
476    }
477
478    fn write_bits_be(&self, vec: &mut Vec<bool>) {
479        self.c0.write_bits_be(vec);
480        self.c1.write_bits_be(vec);
481    }
482}
483
484impl<P: Fp12Parameters> ToBytes for Fp12<P> {
485    #[inline]
486    fn write_le<W: Write>(&self, mut writer: W) -> IoResult<()> {
487        self.c0.write_le(&mut writer)?;
488        self.c1.write_le(&mut writer)
489    }
490}
491
492impl<P: Fp12Parameters> FromBytes for Fp12<P> {
493    #[inline]
494    fn read_le<R: Read>(mut reader: R) -> IoResult<Self> {
495        let c0 = Fp6::read_le(&mut reader)?;
496        let c1 = Fp6::read_le(&mut reader)?;
497        Ok(Fp12::new(c0, c1))
498    }
499}
500
501impl<P: Fp12Parameters> CanonicalSerializeWithFlags for Fp12<P> {
502    #[inline]
503    fn serialize_with_flags<W: Write, F: Flags>(&self, mut writer: W, flags: F) -> Result<(), SerializationError> {
504        self.c0.serialize_uncompressed(&mut writer)?;
505        self.c1.serialize_with_flags(&mut writer, flags)?;
506        Ok(())
507    }
508
509    fn serialized_size_with_flags<F: Flags>(&self) -> usize {
510        self.c0.uncompressed_size() + self.c1.serialized_size_with_flags::<F>()
511    }
512}
513
514impl<P: Fp12Parameters> CanonicalSerialize for Fp12<P> {
515    #[inline]
516    fn serialize_with_mode<W: Write>(&self, writer: W, _compress: Compress) -> Result<(), SerializationError> {
517        self.serialize_with_flags(writer, EmptyFlags)
518    }
519
520    #[inline]
521    fn serialized_size(&self, compress: Compress) -> usize {
522        self.c0.serialized_size(compress) + self.c1.serialized_size(compress)
523    }
524}
525
526impl<P: Fp12Parameters> CanonicalDeserializeWithFlags for Fp12<P> {
527    #[inline]
528    fn deserialize_with_flags<R: Read, F: Flags>(mut reader: R) -> Result<(Self, F), SerializationError> {
529        let c0 = CanonicalDeserialize::deserialize_uncompressed(&mut reader)?;
530        let (c1, flags) = Fp6::deserialize_with_flags(&mut reader)?;
531        Ok((Self::new(c0, c1), flags))
532    }
533}
534
535impl<P: Fp12Parameters> Valid for Fp12<P> {
536    fn check(&self) -> Result<(), snarkvm_utilities::SerializationError> {
537        Ok(())
538    }
539
540    fn batch_check<'a>(_batch: impl Iterator<Item = &'a Self>) -> Result<(), snarkvm_utilities::SerializationError>
541    where
542        Self: 'a,
543    {
544        Ok(())
545    }
546}
547
548impl<P: Fp12Parameters> CanonicalDeserialize for Fp12<P> {
549    #[inline]
550    fn deserialize_with_mode<R: Read>(
551        mut reader: R,
552        compress: Compress,
553        validate: Validate,
554    ) -> Result<Self, SerializationError> {
555        let c0 = CanonicalDeserialize::deserialize_with_mode(&mut reader, compress, validate)?;
556        let c1 = CanonicalDeserialize::deserialize_with_mode(&mut reader, compress, validate)?;
557        Ok(Fp12::new(c0, c1))
558    }
559}
snarkvm_fields/fp12_2over3over2.rs

snarkvm_fields/
fp12_2over3over2.rs
