Uniform binary field arithmetic and primitive element selection at logarithmic width
OpenTimeSpaceMA.GUV.binaryFieldArithmetic_existscomplexity-theorycondensersfinite-fields
For every fixed and all widths , put . Give the field of size and its quadratic extension uniform binary representations. There are deterministic polynomial-time multitape algorithms for addition and multiplication in the larger field, for the labels of zero and the embedded input coefficients corresponding to the two bits, and for selecting the label of an embedded element of multiplicative order . The unary input allows polynomial-time search over field elements of bits. This is the arithmetic needed for a uniform implementation of the folded Reed–Solomon condenser.
Preamble
import Definitions.Def_TimeSpaceMA_GUVBinaryArithmetic
Formal statement
namespace TimeSpaceMA.GUV
theorem binaryFieldArithmetic_exists (a : ℕ) (ha : 0 < a) :
Nonempty (BinaryFieldArithmetic a ha) := by sorry
end TimeSpaceMA.GUVSource
Guruswami, Umans and Vadhan, Unbalanced Expanders and Randomness Extractors from Parvaresh–Vardy Codes, JACM 56(4), 2009, Theorem 6.3. https://www.cs.cmu.edu/~venkatg/pubs/papers/PV-condenser.pdf