Jing-wei Chen
ABSTRACT
For factoring polynomials in two variables with rational coefficients, an algorithm using transcendental evaluation was presented by Hulst and Lenstra. In their algorithm, transcendence measure was computed. However, a constant c is necessary to compute the transcendence measure. The size of c involved the transcendence measure can influence the efficiency of the algorithm greatly.
In this paper, we overcome the problem arising in Hulst and Lenstra's algorithm and propose a new polynomial time algorithm for factoring bivariate polynomials with rational coefficients. Using an approximate algebraic number of high degree instead of a variable of a bivariate polynomial, we can get a univariate one. A factor of the resulting univariate polynomial can then be obtained by a numerical root finder and the purely numerical LLL algorithm. The high degree of the algebraic number guarantees that this factor corresponds to a factor of the original bivariate polynomial. We prove that our algorithm saves a (log2(mn))2+ε factor in bit-complexity comparing with the algorithm presented by Hulst and Lenstra, where (n, m) represents the bi-degree of the polynomial to be factored. We also demonstrate on many significant experiments that our algorithm is practical. Moreover our algorithm can be generalized to polynomials with variables more than two.
- B.Hassibi and H. Vikalo. On the Sphere-decoding Algorithm I. Expected Complexity. IEEE Trans. Signal Processing, 53:2806--2818, 2005. Google Scholar
Digital Library
- A. Bostan, G. Lecerf, B. Salvy, É. Schost, and B. Wiebelt. Complexity Issues in Bivariate Polynomial Factorization. In ISSAC '04: Proceedings of the 2004 international symposium on Symbolic and algebraic computation, pages 42--49, 2004. Google ScholarDigital Library
- G. Chèze and A. Galligo. From an Approximate to an Exact Absolute Polynomial Factorization. Journal of Symbolic Computation, 41(6):682--696, 2006. Google ScholarDigital Library
- G. Chèze and G. Lecerf. Lifting and Recombination Techniques for Absolute Factorization. Journal of Complexity, 23(3):380--420, 2007. Google ScholarDigital Library
- A. Chistov. An Algorithm of Polynomial Complexity for Factoring Polynomials, and Determination of the Components of a Variety in a Subexponential Time. (Russian), Theory of the complexity of computations, II., Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov.(LOMI) 137, pages 124--188, 1984.Google Scholar
- R. M. Corless, A. Galligo, I. S. Kotsireas, and S. M. Watt. A Geometric-numeric Algorithm for Absolute Factorization of Multivariate Polynomials. In ISSAC '02: Proceedings of the 2002 international symposium on Symbolic and algebraic computation, pages 37--45, 2002. Google ScholarDigital Library
- J. D. Dora, A. Maignan, M. Mirica-Ruse, and S. Yovine. Hybrid Computation. In ISSAC '01: Proceedings of the 2001 international symposium on Symbolic and algebraic computation, pages 101--108, 2001. Google ScholarDigital Library
- N. I. Fel'dman. Estimate for a Linear Form of Logarithms of Algebraic Numbers. Sbornik: Mathematics, 5(2):291--307, 1968.Google Scholar
- S. Gao. Factoring Multivariate Polynomials via Partial Differential Equations. Math. Comput., 72(242):801--822, 2003. Google ScholarDigital Library
- S. Gao, E. Kaltofen, J. May, Z. Yang, and L. Zhi. Approximate Factorization of Multivariate Polynomials via Differential Equations. In Proceedings of the 2004 international symposium on Symbolic and algebraic computation, pages 167--174, 2004. Google ScholarDigital Library
- A. Goldstein and R. Graham. A Hadamard-type Bound on the Coeffcients of a Determinant of Polynomials. SIAM Review, 16(3):394--395, 1974.Google ScholarDigital Library
- E. Kaltofen. A Polynomial-time Reduction from Bivariate to Univariate Integral Polynomial Factorization. In 23rd Annual Symposium on Foundations of Computer Science, pages 57--64, 1982. Google ScholarDigital Library
- E. Kaltofen. A Polynomial Reduction from Multivariate to Bivariate Integral Polynomial Factorization. In STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing, pages 261--266, 1982. Google ScholarDigital Library
- E. Kaltofen. Polynomial Factorization 1982-1986. In Computers in mathematics (Stanford, CA, 1986). Vol. 125 of Lecture Notes in Pure and Appl. Math. Dekker, pages 285--309, 1990.Google Scholar
- E. Kaltofen. Polynomial Factorization 1987-1991. In LATIN '92, pages 294--313, 1992. Google ScholarDigital Library
- E. Kaltofen. Effective Noether Irreducibility Forms and Applications. Journal of Computer and System Sciences, 50(2):274--295, 1995. Google ScholarDigital Library
- E. Kaltofen. Polynomial Factorization: a success story. In ISSAC '03: Proceedings of the 2003 international symposium on Symbolic and algebraic computation, pages 3--4, 2003. Google ScholarDigital Library
- E. Kaltofen and L. Zhi. Hybrid Symbolic-numeric Computation. In ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation, pages 7--7, 2006. Google ScholarDigital Library
- R. Kannan, A. Lenstra, and L. Lovász. Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers. Math. Comput., 181:235--250, 1988.Google ScholarCross Ref
- G. Lecerf. Sharp Precision in Hensel Lifting for Bivariate Polynomial Factorization. Math. Comput., 75(254):921--934, 2006.Google Scholar
- A. Lenstra. Factoring Multivariate Integral Polynomials. Theoretical Comput. Sci., 34:207--213, 1984.Google Scholar
- A. Lenstra, H. Lenstra, and L. Lovász. Factoring Polynormials with Rational Coeffcients. Math. Ann., 261:513--534, 1982.Google ScholarCross Ref
- A. K. Lenstra. Factoring Multivariate Polynomials over Finite Fields. In STOC '83: Proceedings of the fifteenth annual ACM symposium on Theory of computing, pages 189--192, 1983. Google ScholarDigital Library
- A. K. Lenstra. Factoring Multivariate Polynomials over Algebraic Number Fields. SIAM Journal on Computing, 16(3):591--598, 1987. Google ScholarDigital Library
- A. May. Using LLL-reduction for Solving RSA and Factorization Problems: A Survey. In LLL+25 Conference in honour of the 25th birthday of the LLL algorithm, 2007.Google Scholar
- M. Mignotte and M. Waldschmidt. Linear Forms in Two Logarithms and Schneider's method. Math. Ann., 231:241--267, 1978.Google ScholarCross Ref
- P. Nguyen and D. Stehlé. Low-dimensional Lattice Basis Reduction Revisited. In Algorithmic Number Theory, pages 338--357. 2004. Google ScholarDigital Library
- A. Novocin. Factoring Univariate Polynomials over the Rationals. Florida State University, http://www.math.fsu.edu/~anovocin, 2008.Google Scholar
- A. Novocin and M. v. Hoeij. Factoring Univariate Polynomials over the Rationals. ACM Commun. Comput. Algebra, 42(3):157--157, 2008. Google ScholarDigital Library
- A. Schönhage. Factorization of Univariate Integer Polynomials by Diophantine Aproximation and an Improved Basis Reduction Algorithm. In Proceedings of the 11th Colloquium on Automata, Languages and Programming, pages 436--447, 1984. Google ScholarDigital Library
- M.-P. van der Hulst and A. Lenstra. Factorization of Polynomials by Transcendental Evaluation. In EUROCAL '85, pages 138--145, 1985. Google ScholarDigital Library
- M. van Hoeij. Factoring Polynomials and 0-1 Vectors. In Cryptography and Lattices, pages 45--50, 2001. Google ScholarDigital Library
- M. van Hoeij. Factoring Polynomials and the Knapsack Problem. Journal of Number Theory, 95(2):167--189, 2002.Google ScholarCross Ref
- J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, London, 1999. Google ScholarDigital Library
- L. Zhi. Numerical Optimization in Hybrid Symbolic-numeric Computation. In SNC '07: Proceedings of the 2007 international workshop on Symbolic-numeric computation, pages 33--35, 2007. Google ScholarDigital Library
Index Terms
- Exact polynomial factorization by approximate high degree algebraic numbers
Recommendations
Real algebraic numbers and polynomial systems of small degree
Based on precomputed Sturm-Habicht sequences, discriminants and invariants, we classify, isolate with rational points, and compare the real roots of polynomials of degree up to 4. In particular, we express all isolating points as rational functions of ...
The approximate GCD of inexact polynomials
ISSAC '04: Proceedings of the 2004 international symposium on Symbolic and algebraic computationThis paper presents an algorithm and its implementation for computing the approximate GCD (greatest common divisor) of multivariate polynomials whose coefficients may be inexact. The method and the companion software appear to be the first practical ...
Estimations of psi function and harmonic numbers
The asymptotic expansion of digamma function is a starting point for the derivation of approximants for harmonic sums or Euler-Mascheroni constant. It is usual to derive such approximations as values of logarithmic function, which leads to the expansion ...
Comments