Prime-field-complete functions and factoring polynomials over finite fields
Lajos Rónyai, Ágnes Szántó · SZTAKI Publication Repository (Hungarian Academy of Sciences) · 1996
We relate the arithmetic straight-line complexity over a field GF(p) (p is a prime) of the parity function l p to the Boolean complexity of the problem of factoring polynomials over finite fields of characteristic p. A procedure is described which -converts an arithmetic straight-line program for l p into a factoring algorithm. As a consequence, a short straight-line program for l p would imply the existence of an efficient factoring method.