Encoded arithmetic in a binary field and its quadratic extension
DefinitionTimeSpaceMA_GUVBinaryArithmeticcomplexity-theorycondensersfinite-fields
Specifies binary labels for a finite field and its quadratic extension, a field embedding, and a primitive element of the smaller field. It requires uniform polynomial-time coded addition and multiplication, the two input coefficient labels, zero, and the embedded primitive element.
Definition code
import Definitions.Def_TimeSpaceMA_GUVFoldedEvaluator
namespace TimeSpaceMA.GUV
open Turing.MultiTapeTM Turing.MultiTapeTM.ComputableTidilyInPolyTime Polynomial
abbrev FieldWord (a : ℕ) (n : ℕ) := Fin (2^(2*halfSeed a n))
abbrev FieldBinInput := ℕ × ℕ × ℕ
abbrev encFieldBinInput : FieldBinInput ↪ List Bool :=
encPair encUnary (encPair encNat encNat)
abbrev FieldCoeffInput := ℕ × Bool
abbrev encFieldCoeffInput : FieldCoeffInput ↪ List Bool := encPair encUnary encBool
/-- A presentation of binary extension fields with coded arithmetic.
Syntactic operations return natural numbers, clipped by the caller to the field
word width. The primitive is represented after embedding into the larger field. -/
structure BinaryFieldArithmetic (a : ℕ) (ha : 0 < a) where
K : ℕ → Type
F : ℕ → Type
fieldK (n : ℕ) : Field (K n)
fieldF (n : ℕ) : Field (F n)
charF (n : ℕ) : CharP (F n) 2
codeK (n : ℕ) : Fin (2 ^ halfSeed a n) ≃ K n
codeF (n : ℕ) : FieldWord a n ≃ F n
embed (n : ℕ) : K n →+* F n
primitive (n : ℕ) : K n
primitive_order (n : ℕ) (hn : 1 ≤ n) : orderOf (primitive n) = 2^halfSeed a n - 1
add : FieldBinInput → ℕ
mul : FieldBinInput → ℕ
coeff : FieldCoeffInput → ℕ
zero : ℕ → ℕ
generator : ℕ → ℕ
add_native : ComputableInPolyTime add encFieldBinInput encNat
mul_native : ComputableInPolyTime mul encFieldBinInput encNat
coeff_native : ComputableInPolyTime coeff encFieldCoeffInput encNat
zero_native : ComputableInPolyTime zero encUnary encNat
generator_native : ComputableInPolyTime generator encUnary encNat
add_correct (n : ℕ) (hn : 1 ≤ n) (x y : FieldWord a n) :
add (n,x.val,y.val) % 2^(2*halfSeed a n) = ((codeF n).symm (codeF n x + codeF n y)).val
mul_correct (n : ℕ) (hn : 1 ≤ n) (x y : FieldWord a n) :
mul (n,x.val,y.val) % 2^(2*halfSeed a n) = ((codeF n).symm (codeF n x * codeF n y)).val
coeff_correct (n : ℕ) (hn : 1 ≤ n) (b : Bool) :
coeff (n,b) % 2^(2*halfSeed a n) =
((codeF n).symm (embed n (codeK n ⟨b.toNat,
(show b.toNat < 2 from by cases b <;> decide).trans_le
(Nat.le_pow (Nat.mul_pos ha (Nat.size_pos.mpr hn)))⟩))).val
zero_correct (n : ℕ) (hn : 1 ≤ n) :
zero n % 2^(2*halfSeed a n) = ((codeF n).symm 0).val
generator_correct (n : ℕ) (hn : 1 ≤ n) :
generator n % 2^(2*halfSeed a n) = ((codeF n).symm (embed n (primitive n))).val
end TimeSpaceMA.GUV