The computational efficacy of finite-field arithmetic

We investigate the computational power of finite-field arithmetic operations as compared to Boolean operations. We pursue this goal in a representation-independent fashion. We define a good representation of the finite fields to be essentially one in which the field arithmetic operations have polynomial-size Boolean circuits. We exhibit a function f{hook}_p on the prime fields with two properties: first, f{hook}_p has a polynomial-size Boolean circuit in any good representation, i.e. f{hook}_p is easy to compute with general operations; second, any function that has polynomial-size Boolean circuits in some good representation also has polynomial-size arithmetic circuits if and only if f{hook}_p has polynomial-size arithmetic circuits. Informally, f{hook}_p is the hardest function to compute with arithmetic that has small Boolean circuits. We reduce the function f{hook}_p to the pair of functions g_p = ∑ k=1 p-1x^k k on the field F_p, and m_p on Z_p². Here m_p is the "modulo p" function defined in the natural way. We show that f{hook}_p has polynomial-size arithmetic circuits if and only if g_p and m_p have polynomial-size arithmetic circuits, the latter being arithmetic circuits over the ring Z_p2. Finally, we establish a connection of f{hook}_p and m_p with the Bernoulli polynomials and determine the coefficients of the unique degree p - 1 polynomial over F_p that computes f{hook}_p.