The Computational Efficacy of Finite Field Arithmetic

Abstract

We show that there exists an interesting non-uniform model of computational complexity within characteristic-two finite fields. This model regards all problems as families of functions whose domain and co-domain are characteristic-two fields. The model is both a structured and a fully general model of computation.

We ask if the same is true when the characteristics of the fields are unbounded. We show that this is equivalent to asking whether arithmetic complexity over the prime fields is a fully general measure of complexity.

We show that this reduces to whether or not a single canonical function is ''easy'' to compute using only modulo p arithmetic.

We show that the arithmetic complexity of the above function is divided between two other canonical functions, the first to be computed modulo p and the second with modulo p^2 arithmetic.

We thus have tied the efficacy of finite field arithmetic to specific questions about the arithmetic complexities of some fundamental functions.