Open AccessThe Depth Efficacy of Unbounded: Characteristic Finite Field Arithmetic
Author(s) -
Gudmund Skovbjerg Frandsen,
Carl Sturtivant
Publication year - 1988
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v17i240.7596
Subject(s) - mathematics , finite field , unary operation , polynomial , bounded function , finite field arithmetic , discrete mathematics , integer (computer science) , irreducible polynomial , modulo , prime (order theory) , function (biology) , arithmetic , combinatorics , matrix polynomial , mathematical analysis , computer science , evolutionary biology , programming language , biology
We introduce an arithmetic model of parallel computation. The basic operations are ½ and Š gates over finite fields. Functions computed are unary and increasing input size is modelled by shifting the arithmetic base to a larger field. When only finite fields of bounded characteristic are used, then the above model is fully general for parallel computations in that size and depth of optimal arithmetic solutions are polynomially related to size and depth of general (boolean) solutions. In the case of finite fields of unbounded characteristic, we prove that the existence of a fast parallel (boolean) solution to the problem of powering an integer modulo a prime (and powering a polynomial modulo an irreducible polynomial) in combination with the existence of a fast parallel (arithmetic) solution for the problem of computing a single canonical function, f (x) , in the prime fields, guarantees the full generality of the finite field model of computation. We prove that the function f (x) , has a fast parallel arithmetic solution for any ''shallow'' class of primes, i.e. primes p such that any prime power divisor q of p -1 is bounded in value by a polynomial in log p .