[dcba2] 4pp. (PDF) (PS) (DVI) D. J. Bernstein. Research announcement: Faster factorization into coprimes. Document ID: 53a2e278e21bcbb7287b81c563995925. URL: https://cr.yp.to/papers.html#dcba2. Date: 2004.11.03. Supersedes: (PDF) (PS) (DVI) 2004.10.09.
Relevant talks: 1997.11.19, ``Factoring into coprimes in essentially linear time.'' 2000.09.07 (slides available), ``Factoring into coprimes.'' 2004.11.19 (slides available), ``Faster factorization into coprimes.'' 2006.11.19 (slides available), ``Faster factorization into coprimes.''
1974 Collins, ``Quantifier elimination for real closed fields by cylindrical algebraic decomposition.''
1985 Kaltofen, ``Sparse Hensel lifting,'' Section 3.
1985 Della Dora DiCrescenzo Duval, ``About a new method for computing in algebraic number fields.''
1986 Bach Miller Shallit, ``Sums of divisors, perfect numbers, and factoring.''
1986 von zur Gathen, ``Representations and parallel computations for rational functions,'' Remark 6.8.
1986 Lueneburg, ``On a little but useful algorithm.''
1989 Pohst Zassenhaus, ``Algorithmic algebraic number theory,'' Section 4.6.
1990 Teitelbaum, ``On the computational complexity of the resolution of plane curve singularities,'' Section 3.1.
1990 Smedley, ``Detecting algebraic dependencies between unnested radicals: extended abstract.''
1993 Bach Driscoll Shallit, ``Factor refinement.''
1994 Ge, ``Recognizing units in number fields.''
1994 Buchmann Lenstra, ``Approximating rings of integers in number fields.''
1994 Goettfert, ``An acceleration of the Niederreiter factorization algorithm in characteristic 2.''
1996 Bernstein, ``Fast ideal arithmetic via lazy localization.''
1997 Silverman, ``Computing canonical heights,'' page 797, subroutine to compute gcd{m,n^infinity}.
1998 Cohen Diaz y Diaz Olivier, ``Computing ray class groups, conductors and discriminants,'' Lemma 2.1.
1998 Storjohann, ``Computing Hermite and Smith normal forms of triangular integer matrices,'' Theorem 5.
1999 Buchmann Eisenbrand, ``On factor refinement in number fields.''
2000 Bernstein, ``How to find small factors of integers.''
2002 Kantor Seress, ``Prime power graphs for groups of Lie type,'' page 427.
2002 Giesbrecht Storjohann, ``Computing rational forms of integer matrices,'' Section 4.
2003 Cai Bach, ``On testing for zero polynomials by a set of points with bounded precision,'' page 17: ``Note that it is computationally easy to test for this property of multiplicative independence modulo squares.''
2003 Gerhard Giesbrecht Storjohann Zima, ``Shiftless decomposition and polynomial-time rational summation,'' Section 3.
2003 Cremona Rusin, ``Efficient solution of rational conics,'' Lemma 2.5.
2004? Perdry, ``Point de vue constructif sur les corps henseliens,'' Lemma 6.
2004 Babai Beals Cai Ivanyos Luks, ``Multiplicative equations over commuting matrices.'' Ge's result is the 1x1 case.
2004 Franke Kleinjung Morain Wirth, ``Proving the primality of very large numbers with fastECPP,'' Section 4.
2004 Bernstein, ``How to find smooth parts of integers.''
2004 Bernstein Lenstra Pila, ``Detecting perfect powers by factoring into coprimes.''
2004 Saunders Wan, ``Smith normal form of dense integer matrices, fast algorithms into practice,'' Section 3.2.