1  # BN254 curve field implementations.
  2  #
  3  # Defines the BN254 base and quadratic extension fields used throughout the
  4  # pairing engine.
  5  
  6  # using GrothAlgebra
  7  # using StaticArrays
  8  
  9  # BN254Field is now provided by GrothAlgebra
 10  # Just re-export what we need
 11  const BN254_PRIME = prime(BN254Field)
 12  
 13  """
 14      Fp2Element
 15  
 16  Element of the quadratic extension field Fp2 = Fp[u]/(u² + 1).
 17  Represented as c0 + c1*u where c0, c1 ∈ Fp.
 18  """
 19  struct Fp2Element
 20      coeffs::SVector{2,BN254Field}
 21  
 22      function Fp2Element(c0::BN254Field, c1::BN254Field)
 23          new(SVector(c0, c1))
 24      end
 25  end
 26  
 27  # Convenient constructors
 28  Fp2Element(c0::Integer, c1::Integer) = Fp2Element(bn254_field(c0), bn254_field(c1))
 29  Fp2Element(c0) = Fp2Element(bn254_field(c0), zero(BN254Field))
 30  
 31  # Access components
 32  Base.getindex(a::Fp2Element, i::Int) = a.coeffs[i]
 33  real(a::Fp2Element) = a.coeffs[1]
 34  imag(a::Fp2Element) = a.coeffs[2]
 35  
 36  # Basic operations
 37  Base.zero(::Type{Fp2Element}) = Fp2Element(zero(BN254Field), zero(BN254Field))
 38  Base.one(::Type{Fp2Element}) = Fp2Element(one(BN254Field), zero(BN254Field))
 39  Base.zero(::Fp2Element) = zero(Fp2Element)
 40  Base.one(::Fp2Element) = one(Fp2Element)
 41  
 42  Base.iszero(a::Fp2Element) = iszero(a[1]) && iszero(a[2])
 43  Base.isone(a::Fp2Element) = isone(a[1]) && iszero(a[2])
 44  
 45  # Equality
 46  Base.:(==)(a::Fp2Element, b::Fp2Element) = a.coeffs == b.coeffs
 47  Base.isequal(a::Fp2Element, b::Fp2Element) = isequal(a.coeffs, b.coeffs)
 48  
 49  # Arithmetic operations
 50  Base.:+(a::Fp2Element, b::Fp2Element) = Fp2Element(a[1] + b[1], a[2] + b[2])
 51  Base.:-(a::Fp2Element, b::Fp2Element) = Fp2Element(a[1] - b[1], a[2] - b[2])
 52  Base.:-(a::Fp2Element) = Fp2Element(-a[1], -a[2])
 53  
 54  """
 55      *(a::Fp2Element, b::Fp2Element)
 56  
 57  Multiply two `Fp2Element`s using the relation `u² = -1`.
 58  The product `(a₀ + a₁u)(b₀ + b₁u)` equals `(a₀b₀ - a₁b₁) + (a₀b₁ + a₁b₀)u`.
 59  """
 60  function Base.:*(a::Fp2Element, b::Fp2Element)
 61      # Real part: a0*b0 - a1*b1
 62      c0 = a[1] * b[1] - a[2] * b[2]
 63      # Imaginary part: a0*b1 + a1*b0
 64      c1 = a[1] * b[2] + a[2] * b[1]
 65      return Fp2Element(c0, c1)
 66  end
 67  
 68  # Scalar multiplication
 69  Base.:*(a::Fp2Element, k::Integer) = Fp2Element(a[1] * k, a[2] * k)
 70  Base.:*(k::Integer, a::Fp2Element) = a * k
 71  Base.:*(a::Fp2Element, k::BN254Field) = Fp2Element(a[1] * k, a[2] * k)
 72  Base.:*(k::BN254Field, a::Fp2Element) = a * k
 73  
 74  """
 75      conjugate(a::Fp2Element)
 76  
 77  Return the conjugate `a - b*u` of `a + b*u`.
 78  """
 79  conjugate(a::Fp2Element) = Fp2Element(a[1], -a[2])
 80  
 81  """
 82      norm(a::Fp2Element)
 83  
 84  Compute the norm `a² + b²` of `a + b*u`.
 85  """
 86  norm(a::Fp2Element) = a[1]^2 + a[2]^2
 87  
 88  """
 89      inv(a::Fp2Element)
 90  
 91  Compute the multiplicative inverse `(a - b*u) / (a² + b²)`.
 92  """
 93  function Base.inv(a::Fp2Element)
 94      if iszero(a)
 95          throw(DivideError())
 96      end
 97      n = norm(a)
 98      n_inv = inv(n)
 99      conj = conjugate(a)
100      return Fp2Element(conj[1] * n_inv, conj[2] * n_inv)
101  end
102  
103  Base.:/(a::Fp2Element, b::Fp2Element) = a * inv(b)
104  
105  """
106      ^(a::Fp2Element, n::Integer)
107  
108  Raise an `Fp2Element` to the integer power `n` using binary exponentiation.
109  """
110  function Base.:^(a::Fp2Element, n::Integer)
111      if n == 0
112          return one(Fp2Element)
113      elseif n < 0
114          return inv(a)^(-n)
115      end
116  
117      result = one(Fp2Element)
118      base = a
119      exp = n
120  
121      while exp > 0
122          if exp & 1 == 1
123              result = result * base
124          end
125          base = base * base
126          exp >>= 1
127      end
128  
129      return result
130  end
131  
132  """
133      frobenius(a::Fp2Element)
134  
135  Apply the Frobenius endomorphism `(a + b*u) ↦ (a - b*u)` (since `u^p = -u`).
136  """
137  frobenius(a::Fp2Element) = conjugate(a)
138  
139  # Display
140  function Base.show(io::IO, a::Fp2Element)
141      if iszero(a[2])
142          print(io, "Fp2(", a[1].value, ")")
143      else
144          print(io, "Fp2(", a[1].value, " + ", a[2].value, "*u)")
145      end
146  end
147  
148  # Export types and functions
149  export BN254Field, bn254_field, BN254_PRIME
150  export Fp2Element, conjugate, norm, frobenius, real, imag