NFS factorization: new hopes

P. Kirchner

Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 25-30.

Résumé

We describe new Number Field Sieve techniques. While none is proved (even under heuristics) to work for a concrete family of number fields, we hope such a family exist. If this is the case, we can factor a special integer $n$ in time $L_n(1/3,(16/9)^{1/3})$, which doubles the length of $n$ with respect to SNFS for the same time. This algorithm works by finding a strongly-ambiguous ideal in order to factor the relative discriminant of a prime degree Galois extension. In case this method can be adapted for factoring general numbers, it may reach a complexity $L_n(1/3,(32/9)^{1/3})$. A variant of the same technique for computing number fields of constant degree $d$ would allow multiplying by $d$ the length of the discriminant at the same complexity. We emphasize that for these running times to hold, we need to build highly specific number fields, and there is no evidence it can be done. Finally, we give another technique for finding the maximum order of number fields, and may run as fast as $L_{|\Delta|}(1/3,(16/9)^{1/3})$. This method is likely to work, and can therefore find some square factors in some numbers.

Détail

Keywords: integer factorization, number field sieve.

Bibliographie

[1] Buhler J. P., Lenstra H. W., Pomerance C., “Factoring integers with the number field sieve”, The Development of the Number Field Sieve, Springer, 1993, 50–94 | DOI | MR | Zbl

[2] Coppersmith D., “Modifications to the number field sieve”, J. Cryptology, 6:3 (1993), 169–180 | DOI | MR | Zbl

[3] Seysen M., “A probabilistic factorization algorithm with quadratic forms of negative discriminant”, Mathematics of Computation, 48:178 (1987), 757–780 | DOI | MR | Zbl

[4] Lenstra H. W., Pomerance C., “A rigorous time bound for factoring integers”, J. Amer. Math. Soc., 5:3 (1992), 483–516 | DOI | MR | Zbl

[5] Cohen H., A Course in Computational Algebraic Number Theory, Springer Science Business Media, 2013 | MR

[6] Lemmermeyer F., The Ambiguous Class Number Formula Revisited, 2013, arXiv: 1309.1071 | MR

[7] Kirchner P., Algorithms on Ideal over Complex Multiplication Order, 2016, arXiv: 1602.09037

[8] Schoof R., Computing Arakelov class groups, 2008, arXiv: 0801.3835 | MR

[9] Adleman L. M., “Factoring numbers using singular integers”, Proc. 23th Ann. ACM Symp. Theory of Computing, ACM, 1991, 64–71

[10] Pollard J. M., “Theorems on factorization and primality testing”, Math. Proc. of the Cambridge Philosophical Soc., 76:3 (1974), 521–528 | DOI | MR | Zbl

[11] Williams H. C., “A $p+1$ method of factoring”, Math. Computation, 39:159 (1982), 225–234 | MR | Zbl

[12] Bach E., Shallit J., “Factoring with cyclotomic polynomials”, Math. Computation, 52:185 (1989), 201–219 | DOI | MR | Zbl

[13] Cox D. A., Primes of the Form $x^2+ ny^2$: Fermat, Class Field Theory, and Complex Multiplication, Pure and Appl. Math., 34, John Wiley Sons, 2011 | MR

[14] Klüners J., Pauli S., “Computing residue class rings and Picard groups of orders”, J. Algebra, 292:1 (2005), 47–64 | DOI | MR | Zbl

[15] Buchmann J. A., Lenstra H. W., “Approximating rings of integers in number fields”, J. de Théorie des Nombres de Bordeaux, 6:2 (1994), 221–260 | MR | Zbl