## Abstract

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_{p2}. 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}.

Original language | English (US) |
---|---|

Pages (from-to) | 291-309 |

Number of pages | 19 |

Journal | Theoretical Computer Science |

Volume | 112 |

Issue number | 2 |

DOIs | |

State | Published - May 10 1993 |

Externally published | Yes |