TY - JOUR
AU - Rónyai, L.
AU - Szántó, A.
PY - 2012/03/05
Y2 - 2023/03/21
TI - Primer-Field Complete Functions and Factoring Polynomials over Finite Fields
JF - COMPUTING AND INFORMATICS
JA - Comput. Inform.
VL - 15
IS - 6
SE - Articles
DO -
UR - https://www.cai.sk/ojs/index.php/cai/article/view/680
SP - 571-577
AB - 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.
ER -