Primer-Field Complete Functions and Factoring Polynomials over Finite Fields

Authors

  • L. Rónyai
  • A. Szántó

Abstract

We relate the arithmetic straight-line complexity over a field GF(p) (p is a prime) of the parity function lp 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 lp into a factoring algorithm.  As a consequence, a short straight-line program for lp would imply the existence of an efficient factoring method.

Downloads

Download data is not yet available.

Published

2012-03-05

How to Cite

Rónyai, L., & Szántó, A. (2012). Primer-Field Complete Functions and Factoring Polynomials over Finite Fields. Computing and Informatics, 15(6), 571–577. Retrieved from http://147.213.75.17/ojs/index.php/cai/article/view/680