TY - JOUR
T1 - A new polynomial factorization algorithm and its implementation
AU - Shoup, Victor
N1 - Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.
PY - 1995/10
Y1 - 1995/10
N2 - We consider the problem of factoring univariate polynomials over a finite field. We demonstrate that the new baby step/giant step factoring method, recently developed by Kaltofen and Shoup, can be made into a very practical algorithm. We describe an implementation of this algorithm, and present the results of empirical tests comparing this new algorithm with others. When factoring polynomials modulo large primes, the algorithm allows much larger polynomials to be factored using a reasonable amount of time and space than was previously possible. For example, this new software has been used to factor a "generic" polynomial of degree 2048 modulo a 2048-bit prime in under 12 days on a Sun SPARC-station 10, using 68 MB of main memory.
AB - We consider the problem of factoring univariate polynomials over a finite field. We demonstrate that the new baby step/giant step factoring method, recently developed by Kaltofen and Shoup, can be made into a very practical algorithm. We describe an implementation of this algorithm, and present the results of empirical tests comparing this new algorithm with others. When factoring polynomials modulo large primes, the algorithm allows much larger polynomials to be factored using a reasonable amount of time and space than was previously possible. For example, this new software has been used to factor a "generic" polynomial of degree 2048 modulo a 2048-bit prime in under 12 days on a Sun SPARC-station 10, using 68 MB of main memory.
UR - http://www.scopus.com/inward/record.url?scp=0001465210&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0001465210&partnerID=8YFLogxK
U2 - 10.1006/jsco.1995.1055
DO - 10.1006/jsco.1995.1055
M3 - Article
AN - SCOPUS:0001465210
VL - 20
SP - 363
EP - 397
JO - Journal of Symbolic Computation
JF - Journal of Symbolic Computation
SN - 0747-7171
IS - 4
ER -