D. J. Bernstein
Fast arithmetic

Factoring into coprimes


[dcba] 30pp. (PDF) (PS) (DVI) D. J. Bernstein. Factoring into coprimes in essentially linear time. Journal of Algorithms 54 (2005), 1-30. Document ID: f32943f0bb67a9317d4021513f9eee5a. URL: http://cr.yp.to/papers.html#dcba. Date: 2004.04.04. Supersedes: (PDF) (PS) (DVI) 1998.01.08.

[dcba2] 4pp. (PDF) (PS) (DVI) D. J. Bernstein. Research announcement: Faster factorization into coprimes. Document ID: 53a2e278e21bcbb7287b81c563995925. URL: http://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.''

Proof-of-concept software

Proof-of-concept software to factor integers into coprimes in essentially linear time

Examples and applications of factoring into coprimes

1890 Stieltjes, ``Sur la theorie des nombres,'' Chapter 1, Section 19.

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.