@article{lecerf10,
author = {Lecerf, Gr\'{e}goire},
title = {New Recombination Algorithms for Bivariate Polynomial Factorization Based on Hensel Lifting},
year = {2010},
issue_date = {March 2010},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg},
volume = {21},
number = {2},
issn = {0938-1279},
url = {https://doi.org/10.1007/s00200-010-0121-5},
doi = {10.1007/s00200-010-0121-5},
journal = {Appl. Algebra Eng., Commun. Comput.},
month = {mar},
pages = {151-176},
numpages = {26},
keywords = {13P05, Secondary 11Y16, 12D05, 68W30, Primary 12Y05}
}
@book{tolstaya,
place={Cambridge},
edition={3},
title={Modern Computer Algebra}, DOI={10.1017/CBO9781139856065}, publisher={Cambridge University Press}, author={von zur Gathen, Joachim and Gerhard, J{\"u}rgen},
year={2013}
}
@Inbook{algebraic-complexity,
author="B{\"u}rgisser, Peter
and Clausen, Michael
and Shokrollahi, Mohammad Amin",
title="Models of Computation",
bookTitle="Algebraic Complexity Theory: With the Collaboration of Thomas Lickteig",
year="1997",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="103--124",
abstract="The standard models for investigating issues in computational complexity in the discrete setting are the Turing machine and the random access machine. However, these models are not well-suited for a discussion of complexity questions in a general algebraic framework, where one assumes that arithmetic operations (over the reals, say) can be performed with infinite-precision at unit cost. For the search of lower bounds in such an algebraic framework, two computational models have proved to be particularly useful: the straight-line program, also called arithmetic circuit, and the computation tree.",
isbn="978-3-662-03338-8",
doi="10.1007/978-3-662-03338-8_4",
url="https://doi.org/10.1007/978-3-662-03338-8_4"
}
@inbook{kaltofen-overview-1,
author = {Kaltofen, Erich},
year = {2020},
month = {12},
pages = {285-309},
title = {Polynomial Factorization 1982-1986},
isbn = {9781003072157},
doi = {10.1201/9781003072157-9}
}
@misc{tellegen-or-not,
author = {D. J. Bernstein},
url = {http://cr.yp.to/transposition.html}
}
@article{moenck-borodin-74,
author = {A. Borodin and R. Moenck},
title = {Fast Modular Transforms},
year = {1974},
journal = {JOURNAL OF COMPUTER AND SYSTEM SCIENCES},
volume = {8}
}
@InProceedings{kaltofen-overview-2,
author="Kaltofen, Erich",
editor="Simon, Imre",
title="Polynomial factorization 1987--1991",
booktitle="LATIN '92",
year="1992",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="294--313",
isbn="978-3-540-47012-0"
}
@article{kaltofen-overview-3,
author = {Kaltofen, Erich},
year = {2003},
month = {09},
pages = {},
title = {Polynomial Factorization: a Success Story},
doi = {10.1145/860854.860857}
}
@inproceedings{monagan-tuncer-sparse-hl-1,
author = {Monagan, Michael and Tuncer, Baris},
year = {2016},
month = {09},
pages = {381-400},
title = {Using Sparse Interpolation in Hensel Lifting},
volume = {9890},
isbn = {978-3-319-45640-9},
doi = {10.1007/978-3-319-45641-6_25}
}
@inbook{monagan-tuncer-sparse-hl-2,
author = {Monagan, Michael and Tuncer, Baris},
year = {2018},
month = {07},
pages = {359-368},
title = {Sparse Multivariate Hensel Lifting: A High-Performance Design and Implementation: 6th International Conference, South Bend, IN, USA, July 24-27, 2018, Proceedings},
isbn = {978-3-319-96417-1},
doi = {10.1007/978-3-319-96418-8_43}
}
@article{monagan-tuncer-sparse-hl-3,
title = {The complexity of sparse Hensel lifting and sparse polynomial factorization},
journal = {Journal of Symbolic Computation},
volume = {99},
pages = {189-230},
year = {2020},
issn = {0747-7171},
doi = {https://doi.org/10.1016/j.jsc.2019.05.001},
url = {https://www.sciencedirect.com/science/article/pii/S0747717119300409},
author = {Michael Monagan and Baris Tuncer},
keywords = {Polynomial factorization, Sparse polynomial interpolation, Multivariate Hensel lifting, Polynomial diophantine equations},
abstract = {The standard approach to factor a multivariate polynomial in Z[x1,x2,…,xn] is to factor a univariate image in Z[x1] then recover the multivariate factors from their univariate images using a process known as multivariate Hensel lifting. Wang's multivariate Hensel lifting recovers the variables one at a time. It is currently implemented in many computer algebra systems, including Maple, Magma and Singular. When the factors are sparse, Wang's approach can be exponential in the number of variables n. To address this, sparse Hensel lifting was introduced by Zippel and then improved by Kaltofen. Recently, Monagan and Tuncer introduced a new approach which uses sparse polynomial interpolation to solve the multivariate polynomial diophantine equations that arise inside Hensel lifting in random polynomial time. This approach is shown to be practical and faster than Zippel's and Kaltofen's algorithms and faster than Wang's algorithm for non-zero evaluation points. In this work we first present a complete description of the sparse interpolation used by Monagan and Tuncer and show that it runs in random polynomial time. Next we study what happens to the sparsity of multivariate polynomials when the variables are successively evaluated at numbers. We determine the expected number of remaining terms. We use this result to revisit and correct the complexity analysis of Zippel's original sparse interpolation. Next we present an average case complexity analysis of our approach. We have implemented our algorithm in Maple with some sub-algorithms implemented in C. We present some experimental data comparing our approach with Wang's method for both sparse and dense factors. The data shows that our method is always competitive with Wang's method and faster when Wang's method is exponential in n.}
}
@InProceedings{monagan18,
author="Monagan, Michael
and Tuncer, Baris",
editor="Gerdt, Vladimir P.
and Koepf, Wolfram
and Seiler, Werner M.
and Vorozhtsov, Evgenii V.",
title="Factoring Multivariate Polynomials with Many Factors and Huge Coefficients",
booktitle="Computer Algebra in Scientific Computing",
year="2018",
publisher="Springer International Publishing",
address="Cham",
pages="319--334",
isbn="978-3-319-99639-4"
}
@article{hoeven-lecerf-20-2,
title = {Fast multivariate multi-point evaluation revisited},
journal = {Journal of Complexity},
volume = {56},
pages = {101405},
year = {2020},
issn = {0885-064X},
doi = {https://doi.org/10.1016/j.jco.2019.04.001},
url = {https://www.sciencedirect.com/science/article/pii/S0885064X1930038X},
author = {Joris {van der Hoeven} and Grégoire Lecerf},
keywords = {Multi-point evaluation, Modular composition, Algorithm, Complexity bound, Kedlaya-Umans algorithm, Power projection},
abstract = {In 2008, Kedlaya and Umans designed the first multivariate multi-point evaluation algorithm over finite fields with an asymptotic complexity that can be made arbitrarily close to linear. However, it remains a major challenge to make their algorithm efficient for practical input sizes. In this paper, we revisit and improve their algorithm, while keeping this ultimate goal in mind. In addition we sharpen the known complexity bounds for modular composition of univariate polynomials over finite fields.}
}
@misc{sturmfels-lection-notes,
title = {Discriminants, resultants, and their tropicalization},
author = {Bernd Sturmfels and Silvia Adduci},
note = {Course by Bernd Sturmfels -- Notes by Silvia Adduci},
year = {2006},
url = {https://swc-math.github.io/aws/2006/06SturmfelsLN.pdf}
}
@article{Hoeven-13,
affiliation = {Laboratoire d'informatique, UMR 7161 CNRS; Computer Science Department, The University of Western Ontario},
author = {Hoeven, Joris and Schost, Éric},
copyright = {Springer-Verlag Berlin Heidelberg},
doi = {10.1007/s00200-012-0179-3},
journal = {Applicable Algebra in Engineering, Communication and Computing},
keywords = {Multi-point evaluation; Multi-point interpolation; Algorithm; Complexity; Power series multiplication},
language = {English},
note = {This work has been partly supported by the French ANR-09-JCJC-0098-01 MaGiX project, by the DIGITEO 2009-36HD grant of the Région Ile-de-France, as well as the NSERC and the Canada Research Chairs program.},
number = {1},
pages = {37-52},
title = {Multi-point evaluation in higher dimensions},
volume = {24},
year = {2013},
}
@inproceedings{Canny-89,
title={Solving systems of nonlinear polynomial equations faster},
author={John F. Canny and Erich L. Kaltofen and Yagati N. Lakshman},
booktitle={International Symposium on Symbolic and Algebraic Computation},
year={1989}
}
@article{Aho-75,
title={Evaluating Polynomials at Fixed Sets of Points},
author={Alfred V. Aho and Kenneth Steiglitz and Jeffrey D. Ullman},
journal={SIAM J. Comput.},
year={1975},
volume={4},
pages={533-539}
}
@article{bostan-schost-05,
author = {Bostan, Alin and Schost, \'{E}ric},
title = {Polynomial Evaluation and Interpolation on Special Sets of Points},
year = {2005},
issue_date = {August 2005},
publisher = {Academic Press, Inc.},
address = {USA},
volume = {21},
number = {4},
issn = {0885-064X},
abstract = {We give complexity estimates for the problems of evaluation and interpolation on various polynomial bases. We focus on the particular cases when the sample points form an arithmetic or a geometric sequence, and we discuss applications, respectively, to computations with linear differential operators and to polynomial matrix multiplication.},
journal = {J. Complex.},
month = {aug},
pages = {420-446},
numpages = {27},
keywords = {Transposition principle, Polynomial matrix multiplication, Complexity, Polynomial evaluation and interpolation}
}
@article{Cooley-1965,
title={An algorithm for the machine calculation of complex Fourier series},
author={James W. Cooley and John W. Tukey},
journal={Mathematics of Computation},
year={1965},
volume={19},
pages={297-301}
}
@article{Pollard-1971,
title={The fast Fourier transform in a finite field},
author={John M. Pollard},
journal={Mathematics of Computation},
year={1971},
volume={25},
pages={365-374}
}
@article{garg-schost-09,
title = {Interpolation of polynomials given by straight-line programs},
journal = {Theoretical Computer Science},
volume = {410},
number = {27},
pages = {2659-2662},
year = {2009},
issn = {0304-3975},
doi = {https://doi.org/10.1016/j.tcs.2009.03.030},
url = {https://www.sciencedirect.com/science/article/pii/S0304397509002254},
author = {Sanchit Garg and Éric Schost},
keywords = {Interpolation, Straight-line program},
abstract = {We give an algorithm for the interpolation of a polynomial A given by a straight-line program. Its complexity is polynomial in τ,log(d),L,n, where τ is an input bound on the number of terms in A, d is a bound on its partial degree in all variables, L is the length of the given straight-line program and n is the number of variables.}
}
@article{firefly-ratfuncs,
title = {Interpolation of dense and sparse rational functions and other improvements in FireFly},
journal = {Computer Physics Communications},
volume = {264},
pages = {107968},
year = {2021},
issn = {0010-4655},
doi = {https://doi.org/10.1016/j.cpc.2021.107968},
url = {https://www.sciencedirect.com/science/article/pii/S0010465521000825},
author = {Jonas Klappert and Sven Yannick Klein and Fabian Lange},
keywords = {Finite field, Black-box interpolation, Modular arithmetic, Symbolic calculations, Feynman integral},
}
@article{zippel-90,
title = {Interpolating polynomials from their values},
journal = {Journal of Symbolic Computation},
volume = {9},
number = {3},
pages = {375-403},
year = {1990},
note = {Computational algebraic complexity editorial},
issn = {0747-7171},
doi = {https://doi.org/10.1016/S0747-7171(08)80018-1},
url = {https://www.sciencedirect.com/science/article/pii/S0747717108800181},
author = {Richard Zippel},
abstract = {A fundamental technique used by many algorithms in computer algebrais interpolating polynomials from their values. This paper discusses two algorithms for solving this problem for sparse multivariate polynomials, an updated version of a probabilistic one and a new deterministic technique that uses some ideas due to Ben-Or and Tiwari (1988). In addition algorithms are presented for quickly finding points that are not zeroes of sparse multivariate polynomials—the zero avoidance problem.}
}
@article{early-tm-kaltofen-lee-2002,
title = {Early termination in sparse interpolation algorithms},
journal = {Journal of Symbolic Computation},
volume = {36},
number = {3},
pages = {365-400},
year = {2003},
note = {ISSAC 2002},
issn = {0747-7171},
doi = {https://doi.org/10.1016/S0747-7171(03)00088-9},
url = {https://www.sciencedirect.com/science/article/pii/S0747717103000889},
author = {Erich Kaltofen and Wen-shin Lee},
keywords = {Early termination, Sparse polynomial, Black box polynomial, Interpolation, Sparse interpolation, Randomized algorithm},
abstract = {A probabilistic strategy, early termination, enables different interpolation algorithms to adapt to the degree or the number of terms in the target polynomial when neither is supplied in the input. In addition to dense algorithms, we implement this strategy in sparse interpolation algorithms. Based on early termination, racing algorithms execute simultaneously dense and sparse algorithms. The racing algorithms can be embedded as the univariate interpolation substep within Zippel’s multivariate method. In addition, we experimentally verify some heuristics of early termination, which make use of thresholds and post-verification.}
}
@inproceedings{arnold-roche-14,
author = {Arnold, Andrew and Roche, Daniel S.},
title = {Multivariate Sparse Interpolation Using Randomized Kronecker Substitutions},
year = {2014},
isbn = {9781450325011},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2608628.2608674},
doi = {10.1145/2608628.2608674},
abstract = {We present new techniques for reducing a multivariate sparse polynomial to a univariate polynomial. The reduction works similarly to the classical and widely-used Kronecker substitution, except that we choose the degrees randomly based on the number of nonzero terms in the multivariate polynomial. The resulting univariate polynomial often has a significantly lower degree than the Kronecker substitution polynomial, at the expense of a small number of term collisions. As an application, we give a new algorithm for multivariate interpolation which uses these new techniques along with any existing univariate interpolation algorithm.},
booktitle = {Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation},
pages = {35--42},
numpages = {8},
keywords = {multivariate polynomials, Kronecker substitution, sparse interpolation, randomized algorithms},
location = {Kobe, Japan},
series = {ISSAC '14}
}
@InProceedings{kaltofen-sparse-hs-gcd,
author="Kaltofen, Erich",
editor="Caviness, Bob F.",
title="Sparse hensel lifting",
booktitle="EUROCAL '85",
year="1985",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="4--17",
abstract="A new algorithm is introduced which computes the multivariate leading coefficients of polynomial factors from their univariate images. This algorithm is incorporated into a sparse Hensel lifting scheme and only requires the factorization of a single univariate image. The algorithm also provides the content of the input polynomial in the main variable as a by-product. We show how we can take advantage of this property when computing the GCD of multivariate polynomials by sparse Hensel lifting.",
isbn="978-3-540-39685-7"
}
@inproceedings{zippel-sparse-hl,
author = {Zippel, Richard},
title = {Newton's Iteration and the Sparse Hensel Algorithm (Extended Abstract)},
year = {1981},
isbn = {0897910478},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/800206.806372},
doi = {10.1145/800206.806372},
abstract = {This paper presents an organization of the p-adic lifting (or Hensel) algorithm that differs from the organization previously presented by Zassenhaus [Zas69] and currently used in algebraic manipulation circles [Mos73, Yun74, Wan75, Mus75]. Our organization is somewhat more general than the earlier one and admits the improvements that yielded the “sparse modular” algorithm [Zip79] more easily than the Zassenhaus algorithm. From a pedagogical point of view, the relationship between Newton's iteration and the p-adic algorithms is clearer in our formulation than with the Zassenhaus algorithm.},
booktitle = {Proceedings of the Fourth ACM Symposium on Symbolic and Algebraic Computation},
pages = {68--72},
numpages = {5},
location = {Snowbird, Utah, USA},
series = {SYMSAC '81}
}
@inproceedings{Yun1973TheHL,
title={The Hensel Lemma in Algebraic Manipulation},
author={David Y. Y. Yun},
booktitle={Outstanding Dissertations in the Computer Sciences},
year={1973}
}
@inproceedings{early-tm-kaltofen-lee-lobo-2000,
author = {Kaltofen, Erich and Lee, Wen-shin and Lobo, Austin A.},
title = {Early Termination in Ben-Or/Tiwari Sparse Interpolation and a Hybrid of Zippel's Algorithm},
year = {2000},
isbn = {1581132182},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/345542.345629},
doi = {10.1145/345542.345629},
booktitle = {Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation},
pages = {192-201},
numpages = {10},
location = {St. Andrews, Scotland},
series = {ISSAC '00}
}
@article{huang-rao-99,
author = {Huang, Ming-Deh A. and Rao, Ashwin J.},
title = {Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications},
year = {1999},
issue_date = {Nov. 1999},
publisher = {Academic Press, Inc.},
address = {USA},
volume = {33},
number = {2},
issn = {0196-6774},
url = {https://doi.org/10.1006/jagm.1999.1045},
doi = {10.1006/jagm.1999.1045},
journal = {J. Algorithms},
month = {nov},
pages = {204–228},
numpages = {25}
}
@inproceedings{benor-tiwari-88,
title={A deterministic algorithm for sparse multivariate polynomial interpolation},
author={Michael Ben-Or and Prasoon Tiwari},
booktitle={Symposium on the Theory of Computing},
year={1988}
}
@article{prony,
author = {R. Prony},
journal = {Journal de l'École Polytechnique Floréal et Plairial, an III, 1(cahier 22)},
title = {Essai expérimental et analytique sur les lois de la dilatabilité des fluides élastiques et sur celles de la force expansive de la vapeur de l'eau et de la vapeur de l'alkool, à différentes températures},
year = {1795},
pages = {24-76}
}
@unpublished{hoeven-lecerf-19,
title = {{Sparse polynomial interpolation. Exploring fast heuristic algorithms over finite fields}},
author = {van Der Hoeven, Joris and Lecerf, Gr{\'e}goire},
url = {https://hal.science/hal-02382117},
note = {working paper or preprint},
year = {2019},
}
@inbook{matrix-multiplication-constant,
author = {Josh Alman and Virginia Vassilevska Williams},
title = {A Refined Laser Method and Faster Matrix Multiplication},
booktitle = {Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)},
chapter = {},
pages = {522-539},
doi = {10.1137/1.9781611976465.32},
URL = {https://epubs.siam.org/doi/abs/10.1137/1.9781611976465.32},
eprint = {https://epubs.siam.org/doi/pdf/10.1137/1.9781611976465.32},
abstract = { The complexity of matrix multiplication is measured in terms of ω, the smallest real number such that two n × n matrices can be multiplied using O(nω+∊) field operations for all ∊ > 0; the best bound until now is ω < 2.37287 [Le Gall'14]. All bounds on ω since 1986 have been obtained using the so-called laser method, a way to lower-bound the ‘value’ of a tensor in designing matrix multiplication algorithms. The main result of this paper is a refinement of the laser method that improves the resulting value bound for most sufficiently large tensors. Thus, even before computing any specific values, it is clear that we achieve an improved bound on ω, and we indeed obtain the best bound on ω to date: ω < 2.37286. The improvement is of the same magnitude as the improvement that [Le Gall'14] obtained over the previous bound [Vassilevska W.'12]. Our improvement to the laser method is quite general, and we believe it will have further applications in arithmetic complexity. }
}
@article{Kedlaya-11,
title={Fast Polynomial Factorization and Modular Composition},
author={Kiran S. Kedlaya and Christopher Umans},
journal={SIAM J. Comput.},
year={2011},
volume={40},
pages={1767-1802}
}
@article{huang-pan-98,
title = {Fast Rectangular Matrix Multiplication and Applications},
journal = {Journal of Complexity},
volume = {14},
number = {2},
pages = {257-299},
year = {1998},
issn = {0885-064X},
doi = {https://doi.org/10.1006/jcom.1998.0476},
url = {https://www.sciencedirect.com/science/article/pii/S0885064X98904769},
author = {Xiaohan Huang and Victor Y. Pan},
keywords = {rectangular matrix multiplication, asymptotic arithmetic complexity, bilinear algorithms, parallel complexity, polynomial composition, polynomial factorization over finite fields, linear programming},
abstract = {First we study asymptotically fast algorithms for rectangular matrix multiplication. We begin with new algorithms for multiplication of ann×nmatrix by ann×n2matrix in arithmetic timeO(nω),ω=3.333953…, which is less by 0.041 than the previous record 3.375477…. Then we present fast multiplication algorithms for matrix pairs of arbitrary dimensions, estimate the asymptotic running time as a function of the dimensions, and optimize the exponents of the complexity estimates. For a large class of input matrix pairs, we improve the known exponents. Finally we show three applications of our results: (a)we decrease from 2.851 to 2.837 the known exponent of the work bounds for fast deterministic (NC) parallel evaluation of the determinant, the characteristic polynomial, and the inverse of ann×nmatrix, as well as for the solution to a nonsingular linear system ofnequations, (b)we asymptotically accelerate the known sequential algorithms for the univariate polynomial composition modxn, yielding the complexity boundO(n1.667) versus the old record ofO(n1.688), and for the univariate polynomial factorization over a finite field, and (c)we improve slightly the known complexity estimates for computing basic solutions to the linear programming problem withmconstraints andnvariables.}
}
@article{kaltofen-shoup,
ISSN = {00255718, 10886842},
URL = {http://www.jstor.org/stable/2585178},
author = {Erich Kaltofen and Victor Shoup},
journal = {Mathematics of Computation},
number = {223},
pages = {1179--1197},
publisher = {American Mathematical Society},
title = {Subquadratic-Time Factoring of Polynomials over Finite Fields},
urldate = {2023-01-28},
volume = {67},
year = {1998}
}
@Inbook{Shafarevich-2013,
author="Shafarevich, Igor R.",
title="Local Properties",
bookTitle="Basic Algebraic Geometry 1: Varieties in Projective Space",
year="2013",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="83--146",
isbn="978-3-642-37956-7",
doi="10.1007/978-3-642-37956-7_2",
url="https://doi.org/10.1007/978-3-642-37956-7_2"
}
@article{wang-var-by-var,
ISSN = {00255718, 10886842},
URL = {http://www.jstor.org/stable/2006346},
abstract = {A new algorithm for factoring multivariate polynomials over the integers based on an algorithm by Wang and Rothschild is described. The new algorithm has improved strategies for dealing with the known problems of the original algorithm, namely, the leading coefficient problem, the bad-zero problem and the occurrence of extraneous factors. It has an algorithm for correctly predetermining leading coefficients of the factors. A new and efficient $p$-adic algorithm named EEZ is described. Basically it is a linearly convergent variable-by-variable parallel construction. The improved algorithm is generally faster and requires less store then the original algorithm. Machine examples with comparative timing are included.},
author = {Paul S. Wang},
journal = {Mathematics of Computation},
number = {144},
pages = {1215--1231},
publisher = {American Mathematical Society},
title = {An Improved Multivariate Polynomial Factoring Algorithm},
urldate = {2023-04-18},
volume = {32},
year = {1978}
}
@article{wang-the-first-one,
ISSN = {00255718, 10886842},
URL = {http://www.jstor.org/stable/2005309},
abstract = {An algorithm for the irreducible factorization of any multivariate polynomial over the integers is given. It is much faster than the classical method ascribed to Kronecker. The algorithm begins by making substitutions for all but one of the variables with selected integers, giving a polynomial in just one variable. This univariate polynomial is then factored by a known method, which uses an algorithm of Berlekamp for factoring univariate polynomials over finite fields. The multivariate factors are constructed from the univariate ones by a kind of Hensel algorithm. The procedure has been implemented in the algebraic manipulation systems MACSYMA and SCRATCHPAD. A number of machine examples with timing are included.},
author = {Paul S. Wang and Linda Preiss Rothschild},
journal = {Mathematics of Computation},
number = {131},
pages = {935--950},
publisher = {American Mathematical Society},
title = {Factoring Multivariate Polynomials Over the Integers},
urldate = {2023-04-18},
volume = {29},
year = {1975}
}
@article{Hilbert-1892,
author = {Hilbert, David},
journal = {Journal für die reine und angewandte Mathematik},
pages = {104-129},
title = {Ueber die Irreducibilität ganzer rationaler Functionen mit ganzzahligen Coefficienten.},
url = {http://eudml.org/doc/148853},
volume = {110},
year = {1892},
}
@article{kaltofen-95,
title = {Effective Noether Irreducibility Forms and Applications},
journal = {Journal of Computer and System Sciences},
volume = {50},
number = {2},
pages = {274-295},
year = {1995},
issn = {0022-0000},
doi = {https://doi.org/10.1006/jcss.1995.1023},
url = {https://www.sciencedirect.com/science/article/pii/S0022000085710239},
author = {E. Kaltofen},
}
@InProceedings{monagan-chen20,
author="Chen, Tian
and Monagan, Michael",
editor="Boulier, Fran{\c{c}}ois
and England, Matthew
and Sadykov, Timur M.
and Vorozhtsov, Evgenii V.",
title="The Complexity and Parallel Implementation of Two Sparse Multivariate Hensel Lifting Algorithms for Polynomial Factorization",
booktitle="Computer Algebra in Scientific Computing",
year="2020",
publisher="Springer International Publishing",
address="Cham",
pages="150--169",
isbn="978-3-030-60026-6"
}
@article{blackbox-factor,
author = {Chen, Tian and Monagan, Michael},
year = {2022},
month = {09},
pages = {},
title = {Factoring Multivariate Polynomials Represented by Black Boxes: A Maple + C Implementation},
volume = {16},
journal = {Mathematics in Computer Science},
doi = {10.1007/s11786-022-00534-7}
}
@article{bernardin-thesis,
author = {Bernardin, Laurent and Fernand, Laurent and Bernardin, Guy and Informatik, Dipl and Eth, Ing and Guy, Loulou},
year = {2000},
month = {08},
journal = {PhD thesis},
title = {Factorization of Multivariate Polynomials over Finite Fields}
}
@article{lecerf07,
title = {Improved dense multivariate polynomial factorization algorithms},
journal = {Journal of Symbolic Computation},
volume = {42},
number = {4},
pages = {477-494},
year = {2007},
issn = {0747-7171},
doi = {https://doi.org/10.1016/j.jsc.2007.01.003},
url = {https://www.sciencedirect.com/science/article/pii/S0747717107000119},
author = {Grégoire Lecerf},
keywords = {Polynomial factorization, Hensel lifting, Bertini's irreducibility theorem}
}
@misc {singular,
title = {{\sc Singular} {4-3-0} --- {A} computer algebra system for polynomial computations},
author = {Decker, Wolfram and Greuel, Gert-Martin and Pfister, Gerhard and Sch\"onemann, Hans},
year = {2022},
howpublished = {\url{http://www.singular.uni-kl.de}},
}
@book{nice-algebra-book,
author = {Kreuzer, Martin and Robbiano, Lorenzo},
year = {2000},
month = {01},
pages = {},
title = {Computational Commutative Algebra I},
isbn = {978-3-540-67733-8 (Print) 978-3-540-70628-1 (Online)},
doi = {10.1007/978-3-540-70628-1}
}
@article{monagan-pearce-12,
author = {Monagan, Michael and Pearce, Roman},
title = {POLY: A New Polynomial Data Structure for Maple 17},
year = {2013},
issue_date = {September/December 2012},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {46},
number = {3/4},
issn = {1932-2240},
url = {https://doi.org/10.1145/2429135.2429173},
doi = {10.1145/2429135.2429173},
journal = {ACM Commun. Comput. Algebra},
month = {jan},
pages = {164-167},
numpages = {4}
}
@inproceedings{monagan-garrett-22,
author = {Monagan, Michael and Paluck, Garrett},
title = {Linear Hensel Lifting for Zp[x,y] for n Factors with Cubic Cost},
year = {2022},
isbn = {9781450386883},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3476446.3536178},
doi = {10.1145/3476446.3536178},
booktitle = {Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation},
pages = {159-166},
numpages = {8},
keywords = {modular methods, hensel lifting, bivariate polynomial factorization},
location = {Villeneuve-d'Ascq, France},
series = {ISSAC '22}
}
@article{cuyt-lee,
author = {Cuyt, Annie and Lee, Wen-shin},
year = {2011},
month = {04},
pages = {1445-1456},
title = {Sparse interpolation of multivariate rational functions},
volume = {412},
journal = {Theor. Comput. Sci.},
doi = {10.1016/j.tcs.2010.11.050}
}
@article{nlognmult,
author = {Harvey, David and van der Hoeven, Joris},
title = {Polynomial Multiplication over Finite Fields in Time \( O(n \log n \) },
year = {2022},
issue_date = {April 2022},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {69},
number = {2},
issn = {0004-5411},
url = {https://doi.org/10.1145/3505584},
doi = {10.1145/3505584},
abstract = {Assuming a widely believed hypothesis concerning the least prime in an arithmetic progression, we show that polynomials of degree less than ( n ) over a finite field ( mathbb {F}_q ) with ( q ) elements can be multiplied in time ( O (n log q log (n log q)) ) , uniformly in ( q ) . Under the same hypothesis, we show how to multiply two ( n ) -bit integers in time ( O (n log n) ) ; this algorithm is somewhat simpler than the unconditional algorithm from the companion paper [22]. Our results hold in the Turing machine model with a finite number of tapes.},
journal = {J. ACM},
month = {mar},
articleno = {12},
numpages = {40},
keywords = {integer multiplication, Polynomial multiplication, complexity bound, algorithm, finite field, FFT}
}
@article{vdhl-ratfunc-21,
author = {van der Hoeven, Joris and Lecerf, Gr\'{e}goire},
title = {On Sparse Interpolation of Rational Functions and Gcds},
year = {2021},
issue_date = {March 2021},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {55},
number = {1},
issn = {1932-2240},
url = {https://doi.org/10.1145/3466895.3466896},
doi = {10.1145/3466895.3466896},
abstract = {In this note, we present a variant of a probabilistic algorithm by Cuyt and Lee for the sparse interpolation of multivariate rational functions. We also present an analogous method for the computation of sparse gcds.},
journal = {ACM Commun. Comput. Algebra},
month = {may},
pages = {1-12},
numpages = {12}
}
@article{BERNARDIN1997,
title = {On square-free factorization of multivariate polynomials over a finite field},
journal = {Theoretical Computer Science},
volume = {187},
number = {1},
pages = {105-116},
year = {1997},
issn = {0304-3975},
doi = {https://doi.org/10.1016/S0304-3975(97)00059-5},
url = {https://www.sciencedirect.com/science/article/pii/S0304397597000595},
author = {Laurent Bernardin},
keywords = {Square-free factorization, Multivariate polynomial, Finite field},
abstract = {In this paper we present a new deterministic algorithm for computing the square-free decomposition of multivariate polynomials with coefficients from a finite field. Our algorithm is based on Yun's square-free factorization algorithm for characteristic 0. The new algorithm is more efficient than existing, deterministic algorithms based on Musser's squarefree algorithm. We will show that the modular approach presented by Yun has no significant performance advantage over our algorithm. The new algorithm is also simpler to implement and it can rely on any existing GCD algorithm without having to worry about choosing “good” evaluation points. To demonstrate this, we present some timings using implementations in Maple (Char et al., 1991), where the new algorithm is used for Release 4 onwards, and Axiom (Jenks and Sutor, 1992) which is the only system known to the author to use an implementation of Yun's modular algorithm mentioned above.}
}
@inproceedings{yun,
author = {Yun, David Y.Y.},
title = {On Square-Free Decomposition Algorithms},
year = {1976},
isbn = {9781450377904},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/800205.806320},
doi = {10.1145/800205.806320},
abstract = {In this paper, we will give three different (including revamped versions of Horowitz's and Musser's) algorithms for computing the SQFR decomposition of polynomials in R[x]. Some algorithm analysis will be carried out to show the (asymptotic) superiority of the algorithm we propose (last of the three).},
booktitle = {Proceedings of the Third ACM Symposium on Symbolic and Algebraic Computation},
pages = {26-35},
numpages = {10},
location = {Yorktown Heights, New York, USA},
series = {SYMSAC '76}
}
@article{julia,
title={Julia: A fresh approach to numerical computing},
author={Bezanson, Jeff and Edelman, Alan and Karpinski, Stefan and Shah, Viral B},
journal={SIAM review},
volume={59},
number={1},
pages={65--98},
year={2017},
publisher={SIAM},
url={https://doi.org/10.1137/141000671}
}
@article {magma,
AUTHOR = {Bosma, Wieb and Cannon, John and Playoust, Catherine},
TITLE = {The {M}agma algebra system. {I}. {T}he user language},
NOTE = {Computational algebra and number theory (London, 1993)},
JOURNAL = {J. Symbolic Comput.},
FJOURNAL = {Journal of Symbolic Computation},
VOLUME = {24},
YEAR = {1997},
NUMBER = {3-4},
PAGES = {235--265},
ISSN = {0747-7171},
MRCLASS = {68Q40},
MRNUMBER = {MR1484478},
DOI = {10.1006/jsco.1996.0125},
URL = {http://dx.doi.org/10.1006/jsco.1996.0125},
}
@article{monagan-tuncer-20,
author = {Monagan, Michael and Tuncer, Baris},
year = {2019},
month = {05},
pages = {},
title = {The complexity of sparse Hensel lifting and sparse polynomial factorization},
volume = {99},
journal = {Journal of Symbolic Computation},
doi = {10.1016/j.jsc.2019.05.001}
}
@article{garrett-monagan-19,
author = {Paluck, Garrett and Monagan, Michael},
title = {New Bivariate Hensel Lifting Algorithm for n Factors},
year = {2019},
issue_date = {September 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {53},
number = {3},
issn = {1932-2240},
url = {https://doi.org/10.1145/3377006.3377021},
doi = {10.1145/3377006.3377021},
journal = {ACM Commun. Comput. Algebra},
month = {dec},
pages = {142-145},
numpages = {4},
keywords = {modular methods, polynomial evaluation, Hensel lifting, polynomial interpolation, polynomial factorization}
}
@misc{ntl,
title={{N}umber theory library ({NTL})},
url={http://www.shoup.net/ntl},
author={Victor Shoup}
}
@misc{flint,
author = {W. Hart and F. Johansson and S. Pancratz},
title = {{FLINT}: {F}ast {L}ibrary for {N}umber {T}heory},
year = {2013},
note = {Version 2.4.0, \url{https://flintlib.org}}
}
@article{v-z-gathen-kaltofen-85,
ISSN = {00255718, 10886842},
URL = {http://www.jstor.org/stable/2008063},
author = {Joachim von zur Gathen and Erich Kaltofen},
journal = {Mathematics of Computation},
number = {171},
pages = {251--261},
publisher = {American Mathematical Society},
title = {Factorization of Multivariate Polynomials Over Finite Fields},
urldate = {2023-01-20},
volume = {45},
year = {1985}
}
@inproceedings{lecerf-04,
author = {Bostan, A. and Lecerf, G. and Salvy, B. and Schost, \'{E}. and Wiebelt, B.},
title = {Complexity Issues in Bivariate Polynomial Factorization},
year = {2004},
isbn = {158113827X},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1005285.1005294},
doi = {10.1145/1005285.1005294},
booktitle = {Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation},
pages = {42-49},
numpages = {8},
keywords = {Hensel lifting, tellegen, multi-moduli, polynomial factorization, transposition principle, computer algebra},
location = {Santander, Spain},
series = {ISSAC '04}
}
@book{Maple10,
author = {Michael B.~Monagan and Keith O.~Geddes and K.~Michael Heal
and George Labahn and Stefan M.~Vorkoetter and James McCarron and Paul DeMarco},
title = {Maple~10 Programming Guide},
publisher = {Maplesoft},
year = {2005},
volume = {},
series = {},
address = {Waterloo ON, Canada},
edition = {},
month = {},
note = {},
key = {}
}
@inproceedings{bernardin-monagan-97,
title={Efficient Multivariate Factorization over Finite Fields},
author={Laurent Bernardin and Michael B. Monagan},
booktitle={International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes},
year={1997}
}
@Inbook{Geddes1992,
author="Geddes, K. O.
and Czapor, S. R.
and Labahn, G.",
title="Newton's Iteration and the Hensel Construction",
bookTitle="Algorithms for Computer Algebra",
year="1992",
publisher="Springer US",
address="Boston, MA",
pages="205--277",
isbn="978-0-585-33247-5",
doi="10.1007/978-0-585-33247-5_6",
url="https://doi.org/10.1007/978-0-585-33247-5_6"
}
@InProceedings{huang-gao-19,
author="Huang, Qiao-Long
and Gao, Xiao-Shan",
editor="England, Matthew
and Koepf, Wolfram
and Sadykov, Timur M.
and Seiler, Werner M.
and Vorozhtsov, Evgenii V.",
title="Revisit Sparse Polynomial Interpolation Based on Randomized Kronecker Substitution",
booktitle="Computer Algebra in Scientific Computing",
year="2019",
publisher="Springer International Publishing",
address="Cham",
pages="215--235",
isbn="978-3-030-26831-2"
}
@inproceedings{javadi-monagan-10,
author = {Javadi, Seyed Mohammad Mahdi and Monagan, Michael},
title = {Parallel Sparse Polynomial Interpolation over Finite Fields},
year = {2010},
isbn = {9781450300674},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1837210.1837233},
doi = {10.1145/1837210.1837233},
booktitle = {Proceedings of the 4th International Workshop on Parallel and Symbolic Computation},
pages = {160-168},
numpages = {9},
keywords = {sparse polynomial interpolation, parallel interpolation algorithms, Ben-Or Tiwari},
location = {Grenoble, France},
series = {PASCO '10}
}
@article{interpolation-in-practice,
author = {Hoeven, Joris and Lecerf, Grégoire},
year = {2015},
month = {02},
pages = {187-191},
title = {Sparse Polynomial Interpolation in Practice},
volume = {48},
journal = {ACM Communications in Computer Algebra},
doi = {10.1145/2733693.2733721}
}
@article{wiedemann,
author={Wiedemann, D.},
journal={IEEE Transactions on Information Theory},
title={Solving sparse linear equations over finite fields},
year={1986},
volume={32},
number={1},
pages={54-62},
doi={10.1109/TIT.1986.1057137}}
@inproceedings{kaltofen-shoup-95,
author = {Kaltofen, Erich and Shoup, Victor},
title = {Subquadratic-Time Factoring of Polynomials over Finite Fields},
year = {1995},
isbn = {0897917189},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/225058.225166},
doi = {10.1145/225058.225166},
booktitle = {Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing},
pages = {398-406},
numpages = {9},
location = {Las Vegas, Nevada, USA},
series = {STOC '95}
}
@article{shoup95,
title = {A New Polynomial Factorization Algorithm and its Implementation},
journal = {Journal of Symbolic Computation},
volume = {20},
number = {4},
pages = {363-397},
year = {1995},
issn = {0747-7171},
doi = {https://doi.org/10.1006/jsco.1995.1055},
url = {https://www.sciencedirect.com/science/article/pii/S0747717185710553},
author = {Victor Shoup},
abstract = {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.}
}
@article{LLL,
author = {Lenstra, H.W. jr. and Lenstra, A.K. and Lovász, L.},
journal = {Mathematische Annalen},
keywords = {polynomial-time algorithm; factorization of primitive polynomials; algorithm for basis reduction; diophantine approximation; operations research; cryptography},
pages = {515-534},
title = {Factoring Polynomials with Rational Coefficients.},
url = {http://eudml.org/doc/182903},
volume = {261},
year = {1982},
}
@INPROCEEDINGS{kaltofen-82-2,
author={Kaltofen, Erich},
booktitle={23rd Annual Symposium on Foundations of Computer Science (sfcs 1982)},
title={A polynomial-time reduction from bivariate to univariate integral polynomial factorization},
year={1982},
volume={},
number={},
pages={57-64},
doi={10.1109/SFCS.1982.56}
}
@inproceedings{kaltofen-82,
author = {Kaltofen, Erich},
title = {A Polynomial Reduction from Multivariate to Bivariate Integral Polynomial Factorization.},
year = {1982},
isbn = {0897910702},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/800070.802200},
doi = {10.1145/800070.802200},
booktitle = {Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing},
pages = {261-266},
numpages = {6},
location = {San Francisco, California, USA},
series = {STOC '82}
}
@article{cantor-zassenhaus-81,
title={A new algorithm for factoring polynomials over finite fields},
author={David Geoffrey Cantor and Hans Zassenhaus},
journal={Mathematics of Computation},
year={1981},
volume={36},
pages={587-592}
}
@ARTICLE{berlekamp67,
author={Berlekamp, E. R.},
journal={The Bell System Technical Journal},
title={Factoring polynomials over finite fields},
year={1967},
volume={46},
number={8},
pages={1853-1859},
doi={10.1002/j.1538-7305.1967.tb03174.x}}
@article{berlekamp70,
ISSN = {00255718, 10886842},
URL = {http://www.jstor.org/stable/2004849},
author = {E. R. Berlekamp},
journal = {Mathematics of Computation},
number = {111},
pages = {713--735},
publisher = {American Mathematical Society},
title = {Factoring Polynomials Over Large Finite Fields},
urldate = {2023-01-20},
volume = {24},
year = {1970}
}
@InProceedings{buchmann-baier-00,
author="Buchmann, Johannes
and Baier, Harald",
editor="Roy, Bimal
and Okamoto, Eiji",
title="Efficient Construction of Cryptographically Strong Elliptic Curves",
booktitle="Progress in Cryptology ---INDOCRYPT 2000",
year="2000",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="191--202",
isbn="978-3-540-44495-4"
}
@article{zassenhaus-1969,
title = {On Hensel factorization, I},
journal = {Journal of Number Theory},
volume = {1},
number = {3},
pages = {291-311},
year = {1969},
issn = {0022-314X},
doi = {https://doi.org/10.1016/0022-314X(69)90047-X},
url = {https://www.sciencedirect.com/science/article/pii/0022314X6990047X},
author = {Hans Zassenhaus},
}
@article{chor-rivest-01,
author = {Chor, Benny and Rivest, Ronald},
year = {2001},
month = {09},
pages = {},
title = {A Knapsack Type Public Key Cryptosystem Based On Arithmetic in Finite Fields},
volume = {34},
journal = {IEEE Transactions on Information Theory},
doi = {10.1109/18.21214}
}
@article{gianni-1988,
title = {Gröbner bases and primary decomposition of polynomial ideals},
journal = {Journal of Symbolic Computation},
volume = {6},
number = {2},
pages = {149-167},
year = {1988},
issn = {0747-7171},
doi = {https://doi.org/10.1016/S0747-7171(88)80040-3},
url = {https://www.sciencedirect.com/science/article/pii/S0747717188800403},
author = {Patrizia Gianni and Barry Trager and Gail Zacharias},
}
@article{lecerf10,
author = {Lecerf, Gr\'{e}goire},
title = {New Recombination Algorithms for Bivariate Polynomial Factorization Based on Hensel Lifting},
year = {2010},
issue_date = {March 2010},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg},
volume = {21},
number = {2},
issn = {0938-1279},
url = {https://doi.org/10.1007/s00200-010-0121-5},
doi = {10.1007/s00200-010-0121-5},
journal = {Appl. Algebra Eng., Commun. Comput.},
month = {mar},
pages = {151-176},
numpages = {26},
keywords = {13P05, Secondary 11Y16, 12D05, 68W30, Primary 12Y05}
}
@article{overview-factor-2001,
title = {Factoring Polynomials Over Finite Fields: A Survey},
journal = {Journal of Symbolic Computation},
volume = {31},
number = {1},
pages = {3-17},
year = {2001},
issn = {0747-7171},
doi = {https://doi.org/10.1006/jsco.1999.1002},
url = {https://www.sciencedirect.com/science/article/pii/S0747717199910027},
author = {Joachim {von zur Gathen} and Daniel Panario},
abstract = {This survey reviews several algorithms for the factorization of univariate polynomials over finite fields. We emphasize the main ideas of the methods and provide an up-to-date bibliography of the problem.}
}
@article{FGLM,
title = {Efficient Computation of Zero-dimensional Gröbner Bases by Change of Ordering},
journal = {Journal of Symbolic Computation},
volume = {16},
number = {4},
pages = {329-344},
year = {1993},
issn = {0747-7171},
doi = {https://doi.org/10.1006/jsco.1993.1051},
url = {https://www.sciencedirect.com/science/article/pii/S0747717183710515},
author = {J.C. Faugère and P. Gianni and D. Lazard and T. Mora},
}
@article{gao-breakthrough-2003,
title={Factoring multivariate polynomials via partial differential equations},
author={Shuhong Gao},
journal={Math. Comp.},
volume={72},
pages={801-822},
year={2003},
doi = {https://doi.org/10.1090/S0025-5718-02-01428-X}
}