Index of algorithms implemented in Rings

Univariate rings

  1. Karatsuba multiplication   (Sec. 8.1 in [GaGe03])
    used with some adaptations for multiplication of univariate polynomials:
  1. Half-GCD and Extended Half-GCD   (Sec. 11 in [GaGe03])
    used (with adaptations inspired by [ShoNTL]) for univariate GCD:
  1. Subresultant polynomial remainder sequences   (Sec. 7.3 in [GeCL92]):
  1. Modular GCD in \(Z[x]\) and \(Q[x]\)   (Sec. 6.7 in [GaGe03], small primes version):
  1. Fast univariate division with Newton iteration   (Sec. 9.1 in [GaGe03])
    used everywhere where multiple divisions (remainders) by the same divider are performed:
  1. Univariate square-free factorization in zero characteristic (Yun’s algorithm)   (Sec. 14.6 in [GaGe03]):
  1. Univariate square-free factorization in non-zero characteristic (Musser’s algorithm)   (Sec. 8.3 in [GeCL92], [Muss71]):
  1. Distinct-degree factorization   (Sec. 14.2 in [GaGe03])
    plain version and adapted version with precomputed \(x\)-powers (used by default):
  1. Shoup’s baby-step giant-step algorithm for distinct-degree factorization   ([Shou95])
    used for factorization over fields with large cardinality:
  1. Univariate modular composition
    plain algorithm with Horner schema:
  1. Brent-Kung univariate modular composition   ([BreK98], [Shou95]):
  1. Cantor-Zassenhaus algorithm (equal-degree splitting)   (Sec. 14.3 in [GaGe03])
    both for odd and even characteristic:
  1. Univaraite linear p-adic Hensel lifting   (Sec. 6.5 in [GeCL92]):
  1. Univaraite quadratic p-adic Hensel lifting   (Sec. 15.4-15.5 in [GaGe03]):
  1. Univariate polynomial factorization over finite fields
    uses Musser’s square free factorization followed by distinct-degree factorization (either \(x\)-powers or Shoup’s algorithm) followed by Cantor-Zassenhaus equal-degree factorization:
  1. Univariate polynomial factorization over Z and Q
    uses factorization modulo small prime followed by Hensel lifting (adaptive linear/quadratic) and naive recombination:
  1. Univariate irreducibility test   (Sec. 14.9 in [GaGe03]):
  1. Ben-Or’s generation of irreducible polynomials   (Sec. 14.9 in [GaGe03]):
  1. Univariate polynomial interpolation
    Lagrange and Newton methods:

Multivariate rings

  1. Brown GCD over finite fields   ([Brow71], Sec. 7.4 in [GeCL92], [Yang09]):
  1. Zippel’s sparse GCD over finite fields   ([Zipp79], [Zipp93], [dKMW05], [Yang09])
    both for monic (with fast Vandermonde systems) and non-monic (LINZIP) cases:
  1. Extended Zassenhaus GCD (EZ-GCD) over finite fields   (Sec. 7.6 in [GeCL92], [MosY73]):
  1. Enhanced Extended Zassenhaus GCD (EEZ-GCD) over finite fields   ([Wang80]):
  1. Modular GCD over Z with sparse interpolation   ([Zipp79], [Zipp93], [dKMW05])
    (the same interpolation techniques as in ZippelGCD is used):
  1. Modular GCD over Z (small primes version):
  1. Kaltofen’s & Monagan’s generic modular GCD   ([KalM99])
    used for computing multivariate GCD over finite fields of very small cardinality:
  1. Kaltofen’s & Monagan’s generic modular GCD with EEZ-GCD for modular images   ([KalM99])
    used for computing multivariate GCD over finite fields of very small cardinality:
  1. Multivariate square-free factorization in zero characteristic (Yun’s algorithm)   ([LeeM13]):
  1. Multivariate square-free factorization in non-zero characteristic (Musser’s algorithm)   ([Muss71], Sec. 8.3 in [GeCL92]):
  1. Bernardin’s fast dense multivariate Hensel lifting   ([Bern99], [LeeM13])
    both for bivariate case (original Bernardin’s paper) and multivariate case (Lee thesis) and both with and without precomputed leading coefficients:
  1. Sparse Hensel lifting   ([Kalt85], [LeeM13])
  1. Fast dense bivariate factorization with recombination   ([Bern99], [LeeM13]):
  1. Kaltofen’s multivariate factorization in finite fields   ([Kalt85], [LeeM13])
    modified version of original Kaltofen’s algorithm for leading coefficient precomputation with square-free decomposition (instead of distinct variables decomposition) due to Lee is used; further adaptations are made to work in finite fields of very small cardinality; the resulting algorithm is close to [LeeM13], but at the same time has many differences in details:
  1. Kaltofen’s multivariate factorization Z   ([Kalt85], [LeeM13])
    (with the same modifications as for algorithm for finite fields):
  1. Multivariate polynomial interpolation with Newton method:
  1. Buchberger algorihm for Groebner basis   ([Buch76], [BecW93], [CLOS97])
    with Gebauer-Moller installation of Buchberger criteria ([GebM88], [BecW93]) and sugar strategy for lexicographic orders ([GMNR88]):
  1. Faugere’s F4 algorithm for Groebner basis   ([Faug99])
    with fast sparse linear algebra [FauL10] and simplification algoritm from [JouV11]:
  1. Hilbert-Poincare series and Hilbert-driven methods for Groebner bases   ([Trav96]):
  1. Modular Groebner bases in Z   ([Arno03]):

References

[GaGe03]J von zur Gathen and J Gerhard. Modern computer algebra (2 ed.). Cambridge University Press, 2003.
[ShoNTL]V Shoup. NTL: A library for doing number theory. www.shoup.net/ntl
[GeCL92]K O Geddes, S R Czapor, G Labahn. Algorithms for Computer Algebra. 1992.
[Muss71]D R Musser. Algorithms for polynomial factorization, Ph.D. Thesis, University of Wisconsin, 1971.
[Shou95]V Shoup. A new polynomial factorization algorithm and its implementation. J. Symb. Comput., 20(4):363–397, 1995.
[BreK98]R P Brent and H T Kung. Fast algorithms for manipulating formal power series. J. Assoc. Comput. Math. 25:581-595, 1978
[Brow71]W S Brown. On Euclid’s algorithm and the computation of polynomial greatest common divisors. J. ACM, 18(4):478–504, 1971.
[Zipp79]R E Zippel. Probabilistic algorithms for sparse polynomials. In Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, EUROSAM ‘79, pages 216–226, London, UK, UK, 1979. Springer-Verlag.
[Zipp93]R E Zippel. Effective Polynomial Computation. Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, 1993.
[dKMW05]J de Kleine, M B Monagan, A D Wittkopf. Algorithms for the Non-monic Case of the Sparse Modular GCD Algorithm. Proceeding of ISSAC ‘05, ACM Press, pp. 124-131 , 2005.
[Yang09]S Yang. Computing the greatest common divisor of multivariate polynomials over finite fields. Master’s thesis, Simon Fraser University, 2009.
[MosY73]J Moses and D Y Y Yun, “The EZGCD Algorithm” pp. 159-166 in Proc. ACM Annual Conference, (1973).
[Wang80]P S Wang, “The EEZ-GCD Algorithm,” ACM SIGSAMBull., 14 pp. 50-60 (1980).
[KalM99]E Kaltofen, M. B. Monagan. On the Genericity of the Modular Polynomial GCD Algorithm. Proceeding of ISSAC ‘99, ACM Press, 59-66, 1999.
[Bern99]L Bernardin. Factorization of Multivariate Polynomials over Finite Fields. PhD thesis, ETH Zu ̈rich, 1999.
[LeeM13]M M-D Lee, Factorization of multivariate polynomials, Ph.D. thesis, University of Kaiserslautern, 2013
[Kalt85]E Kaltofen. Sparse Hensel lifting. In EUROCAL 85 European Conf. Comput. Algebra Proc. Vol. 2, pages 4–17, 1985.
[Trav96]C Traverso, Hilbert Functions and the Buchberger Algorithm, J. Symbolic Comp., 22(4):355–376, 1996.
[Faug99]J-C Faugere, A new efficient algorithm for computing Gröbner bases (F4), Journal of Pure and Applied Algebra. Elsevier Science. 139 (1): 61–88, 1999
[FauL10]J-C Faugere, S Lachartre, Parallel Gaussian elimination for Gröbner bases computations in finite fields, PASCO (2010)
[JouV11]A Joux, V Vitse, A Variant of the F4 Algorithm. In: Kiayias A. (eds) Topics in Cryptology – CT-RSA 2011. CT-RSA 2011. Lecture Notes in Computer Science, vol 6558. Springer, Berlin, Heidelberg
[Buch76]B Buchberger, Theoretical Basis for the Reduction of Polynomials to Canonical Forms, ACM SIGSAM Bulletin. ACM. 10 (3): 19–29
[GebM88]R Gebauer and H Moller, On an Installation of Buchberger’s Algorithm, Journal of Symbolic Computation, 6(2 and 3):275–286, October/December 1988
[GMNR88]A Giovini, T Mora, G Niesi, L Robbiano and C Traverso, One sugar cube, please, or Selection strategies in the Buchberger Algorithm. In S. M. Watt, editor, Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation. ISSAC‘91, ACM Press, 1991.
[BecW93]T Becker and V Weispfenning, Groebner Bases, a Computationnal Approach to Commutative Algebra. Graduate Texts in Mathematics. Springer-Verlag, 1993.
[CLOS97]D Cox, J Little and D O’Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Springer, 1997
[Arno03]E Arnold, Modular algorithms for computing Gröbner bases, Journal of Symbolic Computation Vol. 35, Issue 4, April 2003, Pages 403-419