1  // Copyright (c) 2019-2025 Alpha-Delta Network Inc.
  2  // This file is part of the deltavm 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  
 16  use crate::{Field, Fp2, Fp2Parameters, One, Zero, fp6_3over2::*};
 17  use deltavm_utilities::{FromBytes, ToBits, ToBytes, bititerator::BitIteratorBE, rand::Uniform, serialize::*};
 18  
 19  use rand::{
 20      Rng,
 21      distributions::{Distribution, Standard},
 22  };
 23  use serde::{Deserialize, Serialize};
 24  use 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  
 32  pub 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  
 39  type 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)]
 43  pub struct Fp12<P: Fp12Parameters> {
 44      pub c0: Fp6<P::Fp6Params>,
 45      pub c1: Fp6<P::Fp6Params>,
 46  }
 47  
 48  impl<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  
 55  impl<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  
196  impl<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  
202  impl<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  
209  impl<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  
219  impl<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  
229  impl<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  
334  impl<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  
346  impl_add_sub_from_field_ref!(Fp12, Fp12Parameters);
347  impl_mul_div_from_field_ref!(Fp12, Fp12Parameters);
348  
349  impl<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  
360  impl<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  
371  impl<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  
382  impl<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  
393  impl<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  
401  impl<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  
409  impl<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  
420  impl<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  
427  impl<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  
435  impl<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  
442  impl<P: Fp12Parameters> From<u128> for Fp12<P> {
443      fn from(other: u128) -> Self {
444          Self::new(other.into(), Fp6::zero())
445      }
446  }
447  
448  impl<P: Fp12Parameters> From<u64> for Fp12<P> {
449      fn from(other: u64) -> Self {
450          Self::new(other.into(), Fp6::zero())
451      }
452  }
453  
454  impl<P: Fp12Parameters> From<u32> for Fp12<P> {
455      fn from(other: u32) -> Self {
456          Self::new(other.into(), Fp6::zero())
457      }
458  }
459  
460  impl<P: Fp12Parameters> From<u16> for Fp12<P> {
461      fn from(other: u16) -> Self {
462          Self::new(other.into(), Fp6::zero())
463      }
464  }
465  
466  impl<P: Fp12Parameters> From<u8> for Fp12<P> {
467      fn from(other: u8) -> Self {
468          Self::new(other.into(), Fp6::zero())
469      }
470  }
471  
472  impl<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  
484  impl<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  
492  impl<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  
501  impl<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  
514  impl<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  
526  impl<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  
535  impl<P: Fp12Parameters> Valid for Fp12<P> {
536      fn check(&self) -> Result<(), deltavm_utilities::SerializationError> {
537          Ok(())
538      }
539  
540      fn batch_check<'a>(_batch: impl Iterator<Item = &'a Self>) -> Result<(), deltavm_utilities::SerializationError>
541      where
542          Self: 'a,
543      {
544          Ok(())
545      }
546  }
547  
548  impl<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  }