Victor Shoup
- 1.W. Baur and V. Strassen. The complexity of computing partial derivatives. Theoretical Computer Science, 22:317-330, 1983.Google Scholar
Cross Ref
- 2.M. Ben-Or. Probabilistic Mgorithms in finite fields. In 22nd Annual Symposium on Foundations of Computer Science, pages 394-398, 1981.Google ScholarDigital Library
- 3.E. R. Berlekamp. Factoring polynomi- Ms over large finite fields. Math. Comp., 24( 111):713-735, 1970.Google Scholar
- 4.A. Borodin and I. Munro. The Computational Complexity of Algebraic and Numeric Problems. American Elsevier, 1975.Google Scholar
- 5.D. A. Burgess. A note on the distribution of residues and non-residues. Jour. London Math. Soc., 38:253-256, 1963.Google ScholarCross Ref
- 6.P. Camion. Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomials. IEEE Trans. Inform. Theory, IT-29(3):378- 385, 1983.Google ScholarCross Ref
- 7.J. F. Canny~ E. Kaltofen~ and L. Yagati. Solving systems of non-linear polynomial equations faster. In Proc. A CM-SIGSAM Int. Syrup. on Symbolic and Algebraic Computation, pages 121-128, 1989. Google ScholarDigital Library
- 8.D. G. Cantor and E. Kaltofen. Fast multiplication of polynomials over arbitrary rings. Technical Report 87-35, Department of Computer Science, Rensselaer Polytechnic Institute, 1987. To appear, Acta. inf.Google Scholar
- 9.D. G. Cantor and H. Zassenhaus. A new algorithm for factoring polynomials over finite fields. Math. Comp., 36(154):587-592, 1981.Google ScholarCross Ref
- 10.D. Coppersmith and S. Winograd. Matrix multiplication via Behrend's method. In 19th Annual A CM Symposium on Theory of Computing, pages 1-6, 1987. Google ScholarDigital Library
- 11.M. Kaminski, D. G. Kirkpatrick, and N. H. Bshouty. Addition requirements for matrix and transposed matrix products. Journal of Algorithms, 9:354-364, 1988. Google ScholarDigital Library
- 12.R. T. Moenck. On the efficiency of algorithms for polynomial factoring. Math. Comp., 31(137):235-250, 1977.Google ScholarCross Ref
- 13.V. Shoup. On the deterministic complexity of factoring polynomials over finite fields. Inform. Process. Lett., 33(5):261-267, 1990. Google ScholarDigital Library
- 14.I. E. Shparlinsky. On some questions in the theory of finite fields. Preprint, 1990.Google Scholar
- 15.J. von zur Gathen. Factoring polynomials and primitive elements for special primes. Theoret. Comput. Sci., 52:77-89, 1987. Google ScholarDigital Library
Index Terms
- A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic
Recommendations
Factoring bivariate lacunary polynomials without heights
ISSAC '13: Proceedings of the 38th International Symposium on Symbolic and Algebraic ComputationWe present an algorithm which computes the multilinear factors of bivariate lacunary polynomials. It is based on a new Gap theorem which allows to test whether P(X)=∑kj=1 αjXαj(1+X)βjis identically zero in polynomial time. The algorithm we obtain is ...
Factoring polynomials over finite fields
SFCS '87: Proceedings of the 28th Annual Symposium on Foundations of Computer ScienceWe propose a new deterministic method of factoring polynomials over finite fields. Assuming the Generalized Riemann Hypothesis (GRH), we obtain, in polynomial time, the factorization of any polynomial with a bounded number of irreducible factors. Other ...
Factoring Polynomials over Special Finite Fields
We exhibit a deterministic algorithm for factoring polynomials in one variable over finite fields. It is efficient only if a positive integer k is known for which k(p) is built up from small prime factors; here k denotes the kth cyclotomic polynomial, ...
Comments