The computational efficacy of finite-field arithmetic (Q1210295)

The computational power of finite field arithmetic operations in terms of Boolean operations is investigated. A ``good'' representation of the finite field is one where the arithmetic has polynomial-size Boolean circuits. It is shown that finite-field arithmetic is as powerful as Boolean operations of polynomial size if and only if, in any good representation of field elements as bit strings, there is a polynomial size arithmetic circuit that computes from a field element its representation and vice-versa. A representation with this property is referred to as a strong representation. It is shown that if a strong representation exists then all representations are strong. Consequently the question of arithmetic compared to Boolean operations is reduced to whether a standard representation is strong. This reduces to the case of prime fields for which the standard representation of integers modulo \(p\) is taken. Define the function \[ f_ p(x)=\left( {{x-x^ p} \over p}\right) \bmod p \] where the arithmetic in parenthesis is integer arithmetic. It is shown the efficacy of arithmetic in finite fields is reduced to the arithmetic complexity of \(f_ p\). The function \(f_ p\) is reduced to the pair of functions \(g_ p=\sum_ 1^{p-1} x^ k/k\) on \(F_ p\) and \(m_ p\) on \(F_{p^ 2}\), where \(m_ p\) is the \(\mod p\) function. It is shown that \(f_ p\) has polynomial-size arithmetic circuits if and only if \(g_ p\) and \(m_ p\) have polynomial-size circuits. A connection between \(f_ p\) and \(m_ p\) is made with the Bernoulli polynomials.