Primer-Field Complete Functions and Factoring Polynomials over Finite Fields
L. Rónyai ; A. Szántó
Computing and Informatics, Tome 28 (2012) no. 1, / Harvested from Computing and Informatics
Text on Computing and Informatics
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.
Publié le : 2012-01-26
Classification:  
@article{cai680,
     author = {L. R\'onyai and A. Sz\'ant\'o},
     title = {Primer-Field Complete Functions and Factoring Polynomials over Finite Fields},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai680}
}

L. Rónyai; A. Szántó. Primer-Field Complete Functions and Factoring Polynomials over Finite Fields. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai680/