Factoring polynomials modulo special primes
Tóm tắt
We consider the problem of factoring polynomials overGF(p) for those prime numbersp for which all prime factors ofp− 1 are small. We show that if we have a primitivet-th root of unity for every primet dividingp− 1 then factoring polynomials overGF(p) can be done in deterministic polynomial time.
Tài liệu tham khảo
L.Adleman, G.Miller and K.Manders, On taking roots in finite fields;Proc. 18th IEEE Symp. on Foundations of Computer Science, (1977), 175–178.
E. R.Berlekamp,Algebraic coding theory; McGraw-Hill, 1968.
citation_journal_title=Math. Computation; citation_title=Factoring polynomials over large finite fields; citation_author=E. R. Berlekamp; citation_volume=24; citation_publication_date=1970; citation_pages=713-735; citation_id=CR3
citation_journal_title=Theoretical Computer Science; citation_title=Factoring polynomials and primitive elements for special primes; citation_author=J. Gathen; citation_volume=52; citation_publication_date=1987; citation_pages=77-89; citation_id=CR4
M. A.Huang, Riemann Hypothesis and finding roots over finite fields;Proc. 17th ACM Symp. on Theory of Computing, (1985), 121–130.
D. E.Knuth,The art of computer programming; Vol. 2, Seminumerical algorithms Addison-Wesley Publishing Co., 1981.
R.Lidl and H.Niederreiter,Finite fields; Addison-Wesley Publishing Co., 1983.
citation_journal_title=Mathematics of Computation; citation_title=On the efficiency of algorithms for polynomial factoring; citation_author=R. T. Moenck; citation_volume=31; citation_publication_date=1977; citation_pages=235-250; citation_id=CR8
L.Rónyai, Factoring polynomials over finite fields;Proc. 28th IEEE Symp. on Foundations of Computer Science, (1987), 132–137.
citation_journal_title=Mathematics of Computation; citation_title=Elliptic curves over finite fields and the computation of square roots modp
; citation_author=R. J. Schoof; citation_volume=44; citation_publication_date=1985; citation_pages=483-494; citation_id=CR10
citation_title=Five number-theoretic algorithms; citation_inbook_title=Proc. 1972 Number Theory Conference; citation_publication_date=1972; citation_pages=217-224; citation_id=CR11; citation_author=D. Shanks; citation_publisher=University of Colorado
A.Tonelli,Göttinger Nachrichten, (1891), 344–346. Also in L. E.Dickson,History of the theory of numbers, Chelsea, New York, Vol. I, 215.