1  // Copyright (c) 2025-2026 ACDC Network
  2  // This file is part of the alphavm library.
  3  //
  4  // Alpha Chain | Delta Chain Protocol
  5  // International Monetary Graphite.
  6  //
  7  // Derived from Aleo (https://aleo.org) and ProvableHQ (https://provable.com).
  8  // They built world-class ZK infrastructure. We installed the EASY button.
  9  // Their cryptography: elegant. Our modifications: bureaucracy-compatible.
 10  // Original brilliance: theirs. Robert's Rules: ours. Bugs: definitely ours.
 11  //
 12  // Original Aleo/ProvableHQ code subject to Apache 2.0 https://www.apache.org/licenses/LICENSE-2.0
 13  // All modifications and new work: CC0 1.0 Universal Public Domain Dedication.
 14  // No rights reserved. No permission required. No warranty. No refunds.
 15  //
 16  // https://creativecommons.org/publicdomain/zero/1.0/
 17  // SPDX-License-Identifier: CC0-1.0
 18  
 19  use crate::{Field, LegendreSymbol, One, PrimeField, SquareRootField, Zero};
 20  use alphavm_utilities::{
 21      rand::Uniform,
 22      serialize::{SerializationError, *},
 23      FromBytes,
 24      ToBits,
 25      ToBytes,
 26  };
 27  
 28  use rand::{
 29      distributions::{Distribution, Standard},
 30      Rng,
 31  };
 32  use serde::{Deserialize, Serialize};
 33  use std::{
 34      cmp::{Ord, Ordering, PartialOrd},
 35      fmt::Debug,
 36      hash::Hash,
 37      io::{Read, Result as IoResult, Write},
 38      ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign},
 39  };
 40  
 41  pub trait Fp2Parameters:
 42      'static + Copy + Clone + Default + Debug + PartialEq + Eq + Hash + Serialize + for<'a> Deserialize<'a> + Send + Sync
 43  {
 44      type Fp: PrimeField;
 45  
 46      /// Coefficients for the Frobenius automorphism.
 47      const FROBENIUS_COEFF_FP2_C1: [Self::Fp; 2];
 48  
 49      const NONRESIDUE: Self::Fp;
 50  
 51      const QUADRATIC_NONRESIDUE: (Self::Fp, Self::Fp);
 52  
 53      #[inline(always)]
 54      fn mul_fp_by_nonresidue(fe: &Self::Fp) -> Self::Fp {
 55          Self::NONRESIDUE * fe
 56      }
 57  }
 58  
 59  #[derive(Copy, Clone, Debug, Default, PartialEq, Eq, Hash, Serialize, Deserialize)]
 60  pub struct Fp2<P: Fp2Parameters> {
 61      pub c0: P::Fp,
 62      pub c1: P::Fp,
 63  }
 64  
 65  impl<P: Fp2Parameters> Fp2<P> {
 66      /// Initializes a `Fp2` element from two `Fp` elements.
 67      pub const fn new(c0: P::Fp, c1: P::Fp) -> Self {
 68          Fp2 { c0, c1 }
 69      }
 70  }
 71  
 72  impl<P: Fp2Parameters> Fp2<P> {
 73      /// Norm of Fp2 over Fp: Norm(a) = a.x^2 - beta * a.y^2
 74      pub fn norm(&self) -> P::Fp {
 75          let t0 = self.c0.square();
 76          let mut t1 = self.c1.square();
 77          t1 = -P::mul_fp_by_nonresidue(&t1);
 78          t1.add_assign(t0);
 79          t1
 80      }
 81  
 82      pub fn mul_by_fp(&mut self, element: &P::Fp) {
 83          self.c0.mul_assign(element);
 84          self.c1.mul_assign(element);
 85      }
 86  }
 87  
 88  impl<P: Fp2Parameters> Zero for Fp2<P> {
 89      fn zero() -> Self {
 90          Fp2::new(P::Fp::zero(), P::Fp::zero())
 91      }
 92  
 93      fn is_zero(&self) -> bool {
 94          self.c0.is_zero() && self.c1.is_zero()
 95      }
 96  }
 97  impl<P: Fp2Parameters> One for Fp2<P> {
 98      fn one() -> Self {
 99          Fp2::new(P::Fp::one(), P::Fp::zero())
100      }
101  
102      fn is_one(&self) -> bool {
103          self.c0.is_one() && self.c1.is_zero()
104      }
105  }
106  
107  impl<P: Fp2Parameters> Field for Fp2<P> {
108      type BasePrimeField = P::Fp;
109  
110      fn from_base_prime_field(other: Self::BasePrimeField) -> Self {
111          Self::new(other, P::Fp::zero())
112      }
113  
114      #[inline]
115      fn characteristic<'a>() -> &'a [u64] {
116          P::Fp::characteristic()
117      }
118  
119      fn double(&self) -> Self {
120          let mut result = *self;
121          result.double_in_place();
122          result
123      }
124  
125      fn double_in_place(&mut self) {
126          self.c0.double_in_place();
127          self.c1.double_in_place();
128      }
129  
130      fn square(&self) -> Self {
131          let mut result = *self;
132          result.square_in_place();
133          result
134      }
135  
136      #[inline]
137      #[allow(clippy::collapsible_if)]
138      fn from_random_bytes_with_flags<F: Flags>(bytes: &[u8]) -> Option<(Self, F)> {
139          let split_at = bytes.len() / 2;
140          if let Some(c0) = P::Fp::from_random_bytes(&bytes[..split_at]) {
141              if let Some((c1, flags)) = P::Fp::from_random_bytes_with_flags::<F>(&bytes[split_at..]) {
142                  return Some((Fp2::new(c0, c1), flags));
143              }
144          }
145          None
146      }
147  
148      #[inline]
149      fn from_random_bytes(bytes: &[u8]) -> Option<Self> {
150          Self::from_random_bytes_with_flags::<EmptyFlags>(bytes).map(|f| f.0)
151      }
152  
153      fn square_in_place(&mut self) -> &mut Self {
154          // v0 = c0 - c1
155          let mut v0 = self.c0 - self.c1;
156          // v3 = c0 - beta * c1
157          let v3 = self.c0 - P::mul_fp_by_nonresidue(&self.c1);
158          // v2 = c0 * c1
159          let v2 = self.c0 * self.c1;
160  
161          // v0 = (v0 * v3) + v2
162          v0 *= &v3;
163          v0 += &v2;
164  
165          self.c1 = v2.double();
166          self.c0 = v0 + P::mul_fp_by_nonresidue(&v2);
167  
168          self
169      }
170  
171      fn inverse(&self) -> Option<Self> {
172          if self.is_zero() {
173              None
174          } else {
175              // Guide to Pairing-based Cryptography, Algorithm 5.19.
176              // v0 = c0.square()
177              let mut v0 = self.c0.square();
178              // v1 = c1.square()
179              let v1 = self.c1.square();
180              // v0 = v0 - beta * v1
181              v0 -= &P::mul_fp_by_nonresidue(&v1);
182              v0.inverse().map(|v1| {
183                  let c0 = self.c0 * v1;
184                  let c1 = -(self.c1 * v1);
185                  Self::new(c0, c1)
186              })
187          }
188      }
189  
190      fn inverse_in_place(&mut self) -> Option<&mut Self> {
191          if let Some(inverse) = self.inverse() {
192              *self = inverse;
193              Some(self)
194          } else {
195              None
196          }
197      }
198  
199      fn frobenius_map(&mut self, power: usize) {
200          self.c1.mul_assign(&P::FROBENIUS_COEFF_FP2_C1[power % 2]);
201      }
202  }
203  
204  impl<P: Fp2Parameters> SquareRootField for Fp2<P>
205  where
206      P::Fp: SquareRootField,
207  {
208      fn legendre(&self) -> LegendreSymbol {
209          self.norm().legendre()
210      }
211  
212      fn sqrt(&self) -> Option<Self> {
213          use crate::LegendreSymbol::*;
214          if self.c1.is_zero() {
215              return self.c0.sqrt().map(|c0| Self::new(c0, P::Fp::zero()));
216          }
217          match self.legendre() {
218              // Square root based on the complex method. See
219              // https://eprint.iacr.org/2012/685.pdf (page 15, algorithm 8)
220              Zero => Some(*self),
221              QuadraticNonResidue => None,
222              QuadraticResidue => {
223                  let two_inv = P::Fp::half();
224                  let alpha = self.norm().sqrt().expect("We are in the QR case, the norm should have a square root");
225                  let mut delta = (alpha + self.c0) * two_inv;
226                  if delta.legendre().is_qnr() {
227                      delta -= &alpha;
228                  }
229                  let c0 = delta.sqrt().expect("Delta must have a square root");
230                  let c0_inv = c0.inverse().expect("c0 must have an inverse");
231                  Some(Self::new(c0, self.c1 * two_inv * c0_inv))
232              }
233          }
234      }
235  
236      fn sqrt_in_place(&mut self) -> Option<&mut Self> {
237          (*self).sqrt().map(|sqrt| {
238              *self = sqrt;
239              self
240          })
241      }
242  }
243  
244  /// `Fp2` elements are ordered lexicographically.
245  impl<P: Fp2Parameters> Ord for Fp2<P> {
246      #[inline(always)]
247      fn cmp(&self, other: &Self) -> Ordering {
248          match self.c1.cmp(&other.c1) {
249              Ordering::Greater => Ordering::Greater,
250              Ordering::Less => Ordering::Less,
251              Ordering::Equal => self.c0.cmp(&other.c0),
252          }
253      }
254  }
255  
256  impl<P: Fp2Parameters> PartialOrd for Fp2<P> {
257      #[inline(always)]
258      fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
259          Some(self.cmp(other))
260      }
261  }
262  
263  impl<P: Fp2Parameters> From<u128> for Fp2<P> {
264      fn from(other: u128) -> Self {
265          Self::new(other.into(), P::Fp::zero())
266      }
267  }
268  
269  impl<P: Fp2Parameters> From<u64> for Fp2<P> {
270      fn from(other: u64) -> Self {
271          Self::new(other.into(), P::Fp::zero())
272      }
273  }
274  
275  impl<P: Fp2Parameters> From<u32> for Fp2<P> {
276      fn from(other: u32) -> Self {
277          Self::new(other.into(), P::Fp::zero())
278      }
279  }
280  
281  impl<P: Fp2Parameters> From<u16> for Fp2<P> {
282      fn from(other: u16) -> Self {
283          Self::new(other.into(), P::Fp::zero())
284      }
285  }
286  
287  impl<P: Fp2Parameters> From<u8> for Fp2<P> {
288      fn from(other: u8) -> Self {
289          Self::new(other.into(), P::Fp::zero())
290      }
291  }
292  
293  impl<P: Fp2Parameters> ToBits for Fp2<P> {
294      fn write_bits_le(&self, vec: &mut Vec<bool>) {
295          self.c0.write_bits_le(vec);
296          self.c1.write_bits_le(vec);
297      }
298  
299      fn write_bits_be(&self, vec: &mut Vec<bool>) {
300          self.c0.write_bits_be(vec);
301          self.c1.write_bits_be(vec);
302      }
303  }
304  
305  impl<P: Fp2Parameters> ToBytes for Fp2<P> {
306      #[inline]
307      fn write_le<W: Write>(&self, mut writer: W) -> IoResult<()> {
308          self.c0.write_le(&mut writer)?;
309          self.c1.write_le(writer)
310      }
311  }
312  
313  impl<P: Fp2Parameters> FromBytes for Fp2<P> {
314      #[inline]
315      fn read_le<R: Read>(mut reader: R) -> IoResult<Self> {
316          let c0 = P::Fp::read_le(&mut reader)?;
317          let c1 = P::Fp::read_le(reader)?;
318          Ok(Fp2::new(c0, c1))
319      }
320  }
321  
322  impl<P: Fp2Parameters> Neg for Fp2<P> {
323      type Output = Self;
324  
325      #[inline]
326      fn neg(self) -> Self {
327          let mut res = self;
328          res.c0 = res.c0.neg();
329          res.c1 = res.c1.neg();
330          res
331      }
332  }
333  
334  impl<P: Fp2Parameters> Distribution<Fp2<P>> for Standard {
335      #[inline]
336      fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Fp2<P> {
337          Fp2::new(Uniform::rand(rng), Uniform::rand(rng))
338      }
339  }
340  
341  impl_add_sub_from_field_ref!(Fp2, Fp2Parameters);
342  impl_mul_div_from_field_ref!(Fp2, Fp2Parameters);
343  
344  impl<P: Fp2Parameters> Add<&'_ Fp2<P>> for Fp2<P> {
345      type Output = Self;
346  
347      #[inline]
348      fn add(self, other: &Self) -> Self {
349          let mut result = self;
350          result.add_assign(other);
351          result
352      }
353  }
354  
355  impl<P: Fp2Parameters> Sub<&'_ Fp2<P>> for Fp2<P> {
356      type Output = Self;
357  
358      #[inline]
359      fn sub(self, other: &Self) -> Self {
360          let mut result = self;
361          result.sub_assign(&other);
362          result
363      }
364  }
365  
366  impl<P: Fp2Parameters> Mul<&'_ Fp2<P>> for Fp2<P> {
367      type Output = Self;
368  
369      #[inline]
370      fn mul(self, other: &Self) -> Self {
371          let mut result = self;
372          result.mul_assign(&other);
373          result
374      }
375  }
376  
377  impl<P: Fp2Parameters> Div<&'_ Fp2<P>> for Fp2<P> {
378      type Output = Self;
379  
380      #[inline]
381      fn div(self, other: &Self) -> Self {
382          let mut result = self;
383          result.mul_assign(&other.inverse().unwrap());
384          result
385      }
386  }
387  
388  impl<P: Fp2Parameters> AddAssign<&'_ Self> for Fp2<P> {
389      #[inline]
390      fn add_assign(&mut self, other: &Self) {
391          self.c0.add_assign(other.c0);
392          self.c1.add_assign(other.c1);
393      }
394  }
395  
396  impl<P: Fp2Parameters> SubAssign<&'_ Self> for Fp2<P> {
397      #[inline]
398      fn sub_assign(&mut self, other: &Self) {
399          self.c0.sub_assign(&other.c0);
400          self.c1.sub_assign(&other.c1);
401      }
402  }
403  
404  impl<P: Fp2Parameters> MulAssign<&'_ Self> for Fp2<P> {
405      #[inline]
406      #[allow(clippy::suspicious_op_assign_impl)]
407      fn mul_assign(&mut self, other: &Self) {
408          *self = Self::new(
409              P::Fp::sum_of_products([self.c0, P::mul_fp_by_nonresidue(&self.c1)].iter(), [other.c0, other.c1].iter()),
410              P::Fp::sum_of_products([self.c0, self.c1].iter(), [other.c1, other.c0].iter()),
411          )
412      }
413  }
414  
415  impl<P: Fp2Parameters> DivAssign<&'_ Self> for Fp2<P> {
416      #[inline]
417      fn div_assign(&mut self, other: &Self) {
418          self.mul_assign(&other.inverse().unwrap());
419      }
420  }
421  
422  impl<P: Fp2Parameters> std::fmt::Display for Fp2<P> {
423      fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
424          write!(f, "Fp2({} + {} * u)", self.c0, self.c1)
425      }
426  }
427  
428  impl<P: Fp2Parameters> CanonicalSerializeWithFlags for Fp2<P> {
429      #[inline]
430      fn serialize_with_flags<W: Write, F: Flags>(&self, mut writer: W, flags: F) -> Result<(), SerializationError> {
431          CanonicalSerialize::serialize_uncompressed(&self.c0, &mut writer)?;
432          self.c1.serialize_with_flags(&mut writer, flags)?;
433          Ok(())
434      }
435  
436      fn serialized_size_with_flags<F: Flags>(&self) -> usize {
437          self.c0.uncompressed_size() + self.c1.serialized_size_with_flags::<F>()
438      }
439  }
440  
441  impl<P: Fp2Parameters> CanonicalSerialize for Fp2<P> {
442      #[inline]
443      fn serialize_with_mode<W: Write>(&self, writer: W, _compress: Compress) -> Result<(), SerializationError> {
444          self.serialize_with_flags(writer, EmptyFlags)
445      }
446  
447      #[inline]
448      fn serialized_size(&self, compress: Compress) -> usize {
449          self.c0.serialized_size(compress) + self.c1.serialized_size(compress)
450      }
451  }
452  
453  impl<P: Fp2Parameters> CanonicalDeserializeWithFlags for Fp2<P> {
454      #[inline]
455      fn deserialize_with_flags<R: Read, F: Flags>(mut reader: R) -> Result<(Self, F), SerializationError> {
456          let c0: P::Fp = CanonicalDeserialize::deserialize_uncompressed(&mut reader)?;
457          let (c1, flags): (P::Fp, _) = CanonicalDeserializeWithFlags::deserialize_with_flags(&mut reader)?;
458          Ok((Fp2::new(c0, c1), flags))
459      }
460  }
461  impl<P: Fp2Parameters> Valid for Fp2<P> {
462      fn check(&self) -> Result<(), alphavm_utilities::SerializationError> {
463          Ok(())
464      }
465  
466      fn batch_check<'a>(
467          _batch: impl Iterator<Item = &'a Self> + Send,
468      ) -> Result<(), alphavm_utilities::SerializationError>
469      where
470          Self: 'a,
471      {
472          Ok(())
473      }
474  }
475  
476  impl<P: Fp2Parameters> CanonicalDeserialize for Fp2<P> {
477      #[inline]
478      fn deserialize_with_mode<R: Read>(
479          mut reader: R,
480          compress: Compress,
481          validate: Validate,
482      ) -> Result<Self, SerializationError> {
483          let c0 = P::Fp::deserialize_with_mode(&mut reader, compress, validate)?;
484          let c1 = P::Fp::deserialize_with_mode(&mut reader, compress, validate)?;
485          Ok(Fp2::new(c0, c1))
486      }
487  }