Факторизация NFS: новые надежды | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/8

Факторизация NFS: новые надежды

Описан новый алгоритм факторизации целых чисел специального вида методом решета числового поля.

NFS factorization: new hopes.pdf 1. Introduction In 1993, the Number Field Sieve algorithm was invented [1] with a complexity of Ln(1/3, (64/9)i/3) for factoring any n, and since then, it has been mostly unchallenged (though a variant is asymptotica11y faster [2]). A variant for specia1 numbers was also given, with a comp1exity of L„(1/3, (32/9)i/3). We give a method for factoring very special n (so special that we do not know how to find them, or if they even exist) with a complexity of only Ln(1/3, (16/9)i/3), if we can find a number field with the desired properties. This algorithm is in fact a generalization of the class group relations method [3, 4]. We also give a method for finding the maximal order of a number field, which may run just as fast, and needs no unknown construction. It might possibly be used for finding square factors in an integer. We will use standard algorithms in number theory, such as the ones for computing the class group and units of a number field, without describing them. A complete description can be found in Cohen's book [5]. 2. Background We fix a Galois extension of number fields [L : K] = p, p is prime, and the Galois group is generated by -. The goal is to factor the discriminant ideal AL/K, and we assume L = Q[X]/f (X) with f of degree d, and the height (maximal absolute value of coefficients) of f being « N(AL/K)i/2/(d-i) where N() denotes the norm of the ideal (the discriminant is a homogeneous polynomial of degree 2d - 2 in the coefficients of f). We let OL be the ring of integers of L. The principle consists in finding a non-trivial ideal a such that a (a) = a. These ideals are called strongly ambiguous [6], and known to be exactly the divisors of a power of AL/K up to an ideal of K. Therefore, gcd(AL/K, a) is non-trivial. For example, Q[X]/(X4 + 13X3 - 43X2 - 39X + 9) is a degree two extension of Q[V317], and the norm of the relative discriminant is 4429 = 43 • 103. While the technique works for all p, it is unlikely to be useful for any p > 2 since the relative discriminant is a p - 1 power. 3. CM case We assume here L is a (strict) CM-field and K is principal (a small h(K) does not pose any problem). Then aa(a) = a2 is an ideal of K so that it is principal. The algorithm therefore computes the class group, and we can then hopefully enumerate all classes [a] whose square is principal. Therefore, we can find a such that there exists v with a(va) = va. Then a = -OL, a (a) v and Gentry-Szydlo [7] recovers v, from which we deduce va (in fact, one can do the same if L has a tiny regulator (a "simplest field") by replacing Gentry-Szydlo with Schoof's algorithm [8]). How to find a "random" ideal whose square is principal: generate relations as usual, and put them in a sparse integer matrix A. It has the property that for all column j, П p^is i principal and known where pi are all prime ideals less than some bound. Then compute x such that Ax = 0[2], and return the ideal corresponding to (Ax)/2, namely п p(Ax/2)i. i The overall complexity is Ln(aL/K)(1/3, (16/9)1/3) for a well-chosen d. 4. Non-CM We assume here L is not a CM-field, so that each class of ideals is represented by a small integral ideal a (this excludes the families of the rare "simplest fields", though). Therefore, we can find a such that a(va) = va. We first compute g a generator of a = a(v) OL. Then, we a (a) v compute the units of L, and K. From there, we can in polynomial time deduce u £ L a unit, such that NL/K(gu) = 1 (a(v)/v/g is such a unit). Then, we solve3 a(w) = wgu (w = 0), an equation which is linear in w (there is a solution, because of Hilbert's Theorem 90). Finally, a(wa) = wa. The overall complexity is Ln(aL/K)(1/3, (16/9)1/3) for a well-chosen d, if we can multiply matrices in time n4+o(1). The sparse linear algebra exponent is in fact a bit higher (2.38), so the complexity will also be a bit higher. If we take the field Q[X]/(X4 + 13X3 - 43X2 - 39X + 9), and the ideal Ol, units are generators, and generated by u0 = 5/3X3 + 65/3X2 - 200/3X - 77, u1 = 121/3X3 - - 320/3X2 - 286/3X + 22 and u2 = 2183/3X3 + 26399/3X2 - 117815/3X + 7238. u1 is of norm 1, which indicates the element w0 = 92X2 + 1471X + 283 with w0/a(w0) = u1, and is of norm 103 x 4212, revealing the factor 103 of the discriminant. u-1u1u2 is of norm 1, which indicates the corresponding element w1 = 557995X2 + 9207617X + 7889384, of norm 43 x 1620922, revealing the other factor 43 of the discriminant. Average-case factorization? It may seem that by relaxing the height of f to ~ n1/d, we may hope to factor the integer n in time which is only Ln(1/3, (32/9)1/3) for most n. Of course, we also need the density of such f with a suitable subfield to be not too tiny, and a fast way to generate such a f. 5. Computing constant degree fields The best known heuristic algorithm which computes a field K of constant degree d runs in La(1/2,1), and A is the discriminant (up to sign). Now, we propose to instead find some extension L of K of degree k = w(1) but sufficiently small. Then, we can hope that L = Q[X]/f (X) with f a polynomial of height « (AkS)1/(2dk-2) = A1/2d+o(1)8(1+o(1))/2dk where 8 is the norm of the relative discriminant. Thus, the numbers which are to be smooth in the algorithm are of this size, instead of A1/2. We can then deduce some units of K as norms of the units of L. The index is a power of k, so that the units can be recovered through a saturation method. Also, if h(K) is coprime with k, then the norm of the class group of L is the class group of K (otherwise, we know that the p-Sylow differs only when p divides gcd(k, h(K))). Furthermore, in case the extension is abelian, class field theory describes the norm map. In the case of 8 small, we can therefore compute fields whose discriminants are d times the size of the previous algorithm. We add that if a family of such extensions exists with d ^ 3, k prime and the extension is Galois, then either we can factor 8 faster than the SNFS algorithm, or we can compute the base field in a faster way than the previous algorithm. Hence, the last possibility for this method to get only trivial results (if L exists), is that 8 must be smooth. While this is the case when L has lots of subfields, this should not be the general case. 6. Finding the maximal order We collect relations in Z[X]/f (X) as usual, and form a matrix A,j such that Пpfi,j i is generated by Vj. The initial order O is Z[X]/f (X), and we make it p-maximal for each prime number p in the factor base (see [5]). Then, we choose some small prime p and we compute a random x such that Ax = = 0 (mod p). The final step is to extract a p-th root of П vX and look for non trivial i denominators in the coordinate. We may ensure it is an element of Ol using characters (as in [9])- or alternatively, hope that it is the case. Then, consider g a generator of np(Ax)i/p. This ideal is "random" in Cl(O)/Cl(OL)[p], and in case it is not trivial, we get a i non trivial denominator. Consider now g-p П vX; this is a "random" (well-defined) element i in O£/Ox[p], and again if it is not trivial, we discover a non trivial denominator. We have the exact sequence 1 ^ OX/Ox ^ (Ol/f)x/(O/f)x ^ Cl(O) ^ Cl(Ol) ^ 1 where the conductor f is {x G L; xOL С O}. It implies that |C1(O)/C1(Ol)||OX/Ox| = |(Ol/f)x/(O/f)x|. In particular, if p| |(OL/f)x/(O/f)x |, we should obtain quickly the corresponding factors. In our experiments, any large prime factor q of the index gave rise either to a factor of q + 1 qd0 - 1 or q - 1, so that p =2 seems enough. We may however find factors of the type --with qdl - 1 d1|d0 ^ d, which can be tackled with p|d0/d1. Another technique is to compute |C1(O)|, and then use it to factor the discriminant. Indeed, we may hope to find large primes of |(OL/f)x |, and then use them in the p - 1 [10], p +1 [11] method, or a generalization of them [12] (while we might have been forced with the p - 1 method to factor the class number so that they do not find all factors of the conductor at the same time, this does not happen with Bach - Shallit's method). In the particular case of imaginary quadratic fields of large discriminant, f is generated by an integer and we recover a product of p + I ), see [13]. However, experiments seem to indicate that for p typical fields, large primes do not divide |C1(O)/C1(Ol)| [14]. Perhaps |(Ol/f)x/(O/f)x| splits in the two components in a way similar to \J|AL|. This excludes fields where units are constrained, of course (such as CM-fields, simplest fields). We can now take the inverse position of Buchmann - Lenstra [15]: since finding the maximal order of some number field may be easier than factoring, we should try reducing the factorization of a number with square factors to finding the maximal order of a number field which is easy to compute. Our first example is Z[X]/(X3 + 14748982211X5 + 330465312475655912644X - - 4541929250363265152095834584323). The index of the order is 31415926535897932429, the index of the unit group is 15707963267948966215 and the discriminant of the field is the prime number -1031219470443951993545807. The maximal order is principal, the order has a class number of 2. Our second example is Z[X]/(X3 + 778669X2 - 11461680097X + 400204890996). Computing its class group, we find Z/1468825548960Z x (Z/2Z)2. Therefore, we compute 24-1468825548960-1 modulo the discriminant of the order, 84855839117718748443550622974949, and searching its inverse leads to the factor 314161. The maximal order has a class group isomorphic to Z/9350812Z x Z/2Z, so that the index is 314160. X - 14417 and X - 35 are generating units of the maximal order. The discriminant of the field is the prime number 859759911423970846469. Both polynomials were found by searching the roots of the discriminant of a polynomial modulo p2. When one of them is small, it implies a small (or convenient) / such that Z[X]//(X) has a discriminant divisible by p2. In all cases found, it has a suborder of index divisible by p. We give the following challenge: Z[X ]/(X5 + 3495453004590491642X4 + 180994857869926433565628676598524675713X3+ +4080542158246926001840448564437517681525979747052560162169X2+ +29991331159418592384221751381757741736460336893245994711847509109058566545411X- -615227362764912581790656075021572703951624280216014735196790277604247021415832383798968053378087). The discriminant of the polynomial has 1287 bits, the discriminant of the field is a prime number of 948 bits and the index is a prime number of 170 bits (51 digits). (In particular, it is faster to use ECM to factor the discriminant.) 7. Conclusion We conclude that when number fields verify the given conditions, then either the norm of the relative discriminant is easily factored, either the unit group2 and the class group are not both explicit. There are known examples of the first case (any cyclotomic field), and of the second case (respectively "simplest" fields and CM fields; and "generic" fields). It suggests that for these fields, this is essentially the best we can do, i.e. there are no explicit (efficient) formulas for the class group of most CM fields and "simplest" fields, and likewise no explicit formulas for the unit group of most "generic" fields. The author thanks Thomas Espitau and Antoine Joux for interesting discussions on this subject.

Ключевые слова

number field sieve, integer factorization, решето числового поля, факторизация целых чисел

Авторы

ФИООрганизацияДополнительноE-mail
Кирхнер ПаульФранцузский институт исследований в области компьютерных наук и автоматизациистудентpkirchne@clipper.ens.fr
Всего: 1

Ссылки

Kluners J. and Pauli S. Computing residue class rings and Picard groups of orders. J. Algebra, 2005, vol. 292, no. 1, pp. 47-64.
Buchmann J. A. and Lenstra H. W. Approximating rings of integers in number fields. J. de theorie des nombres de Bordeaux, 1994, vol. 6, no. 2, pp. 221-260.
Cox D.A. Primes of the Form x2 + ny2: Fermat, Class Field Theory, and Complex Multiplication. John Wiley & Sons, 2011, vol.34.
Adleman L. M. Factoring numbers using singular integers. Proc. 23th Ann. ACM Symp. Theory of Computing, ACM, 1991, pp. 64-71.
Pollard J. M. Theorems on factorization and primality testing. Math. Proc. of the Cambridge Philosophical Soc., Cambridge Univ. Press, 1974, vol.76, no.3, pp. 521-528.
Williams H. C. A p + 1 method of factoring. Math. Computation, 1982, vol.39, no. 159, pp. 225-234.
Bach E. and Shallit J. Factoring with cyclotomic polynomials. Math. Computation, 1989, vol. 52, no. 185, pp. 201-219.
Kirchner P. Algorithms on Ideal over Complex Multiplication Order. arXiv preprint arXiv:1602.09037, 2016.
Schoof R. Computing Arakelov class groups. arXiv preprint arXiv:0801.3835, 2008.
Coppersmith D. Modifications to the number field sieve. J. Cryptology, 1993, vol.6, no.3, pp. 169-180.
Seysen M. A probabilistic factorization algorithm with quadratic forms of negative discriminant. Mathematics of Computation, 1987, vol.48, no. 178, pp. 757-780.
Lenstra H. W. and Pomerance C. A rigorous time bound for factoring integers. J. Amer. Math. Soc., 1992, vol.5, no. 3, pp. 483-516.
Cohen H. A Course in Computational Algebraic Number Theory. Springer Science & Business Media, 2013.
Lemmermeyer F. The Ambiguous Class Number Formula Revisited. arXiv preprint arXiv:1309.1071,2013.
Buhler J. P., Lenstra H. W., and Pomerance C. Factoring integers with the number field sieve. The Development of the Number Field Sieve, Springer, 1993, pp. 50-94.
 Факторизация NFS: новые надежды | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/8

Факторизация NFS: новые надежды | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/8