Shi Bai
email: shih.bai@gmail.com

AND Richard P Brent

Emmanuel Thom
email: emmanuel.thome@inria.fr

ROOT OPTIMIZATION OF POLYNOMIALS IN THE NUMBER FIELD SIEVE

The general number field sieve (GNFS) is the most efficient algorithm known for factoring large integers. It consists of several stages, the first one being polynomial selection. The quality of the chosen polynomials in polynomial selection can be modelled in terms of size and root properties. In this paper, we describe some algorithms for selecting polynomials with very good root properties.

The general number field sieve

The general number field sieve [START_REF] Lenstra | The Development of the Number Field Sieve[END_REF] is the most efficient algorithm known for factoring large integers. It consists of several stages including polynomial selection, sieving, filtering, linear algebra and finding square roots.

Let n be the integer to be factored. The number field sieve starts by choosing two irreducible and coprime polynomials f (x) and g(x) over Z which share a common root m modulo n. In practice, the notations F (x, y) and G(x, y) for the homogenized polynomials corresponding to f and g are often used. We want to find many coprime pairs (a, b) ∈ Z 2 such that the polynomial values F (a, b) and G(a, b) are simultaneously smooth with respect to some upper bound B. An integer is smooth with respect to bound B (or B-smooth) if none of its prime factors are larger than B. Lattice sieving [START_REF] Pollard | The lattice sieve[END_REF] and line sieving [START_REF] Buhler | Factoring integers with the number field sieve[END_REF] are commonly used to identify such pairs (a, b). The running time of sieving depends on the quality of the chosen polynomials in polynomial selection, hence many polynomial pairs will be generated and optimized in order to produce a best one.

This paper discusses algorithms for root optimization in polynomial selection in the number field sieve. We mainly focus on polynomial selection with two polynomials, one of which is a linear polynomial.

Polynomial selection

For large integers, most polynomial selection methods [START_REF] Buhler | Factoring integers with the number field sieve[END_REF][START_REF] Kleinjung | On polynomial selection for the general number field sieve[END_REF][START_REF] Kleinjung | Polynomial selection[END_REF][START_REF] Murphy | Modelling the Yield of Number Field Sieve Polynomials[END_REF][START_REF] Murphy | Polynomial selection for the number field sieve integer factorisation algorithm[END_REF] use a linear polynomial for g(x) and a quintic or sextic polynomial for f (x). Let f (x) = x for some u. The Dickman-de Bruijn function ρ(u) [START_REF] Granville | Smooth numbers: computational number theory and beyond[END_REF] is often used to estimate Ψ(x, x 1/u ), since lim x→∞ Ψ(x, x 1/u ) x = ρ(u).

The Dickman-de Bruijn function satisfies the differential equation

uρ ′ (u) + ρ(u -1) = 0, ρ(u) = 1 for 0 ≤ u ≤ 1.
It can be shown that ρ(u) satisfies the asymptotic estimate

log(ρ(u)) = -(1 + o(1)) u log u as u → ∞.
For practical purposes, the frequency of smooth numbers can be approximated by the Canfield-Erdős-Pomerance theorem, which can be stated as follows [START_REF] Hildebrand | Integers without large prime factors[END_REF].

Theorem 2.1. For any fixed ǫ > 0, we have

Ψ(x, x 1/u ) = xu -u(1+o(1))
as x 1/u and u tend to infinity, uniformly in the region x ≥ u u/ (1-ǫ) .

It is desirable that the polynomial pair can produce many smooth integers across the sieve region. Heuristically this requires that the size of polynomial values is small on average (Theorem 2.1). In addition, one can choose an algebraic polynomial f (x) which has many roots modulo small prime powers. Such a choice is driven by inheritance of practices which already date back to the CFRAC era, where suitable multipliers were chosen precisely in order to optimize this very property [START_REF] Morrison | A method of factoring and the factorization of F 7[END_REF][START_REF] Pomerance | Implementation of the continued fraction integer factoring algorithm[END_REF]. Then the polynomial values are likely to be divisible by small prime powers. This may increase the smoothness probability for polynomial values. We first describe some methods [START_REF] Kleinjung | On polynomial selection for the general number field sieve[END_REF][START_REF] Murphy | Polynomial selection for the number field sieve integer factorisation algorithm[END_REF] to estimate and compare the quality of polynomials.

Sieving test.

A sieving experiment over short intervals is a relatively accurate method to compare polynomial pairs. It is often used to compare a few polynomial candidates in the final stage of the polynomial selection. Ekkelkamp [START_REF] Ekkelkamp | Predicting the sieving effort for the number field sieve[END_REF] also described a method for predicting the number of relations needed in the sieving. The method conducts a short sieving test and simulates relations based on the test results. Experiments show that the prediction of the number of relations is close to the number of relations needed in the actual factorization. The base-(m 1 , m 2 ) expansion [START_REF] Kleinjung | On polynomial selection for the general number field sieve[END_REF][START_REF] Kleinjung | Polynomial selection[END_REF] gives polynomials whose coefficients are O(n1/(d+1) ). The leading coefficients c d and c d-1 are much smaller than n 1/(d+1) . The coefficient c d-2 is slightly smaller than n 1/(d+1) . For such polynomials, it is often better to use a skewed sieving region where the sieving bounds for a, b have ratio s ≥ 1, while keeping the area of the sieving region 2K 2 . The sieving bounds become |a| ≤ K √ s and 0

< b ≤ K/ √ s. Each monomial in the polynomial is bounded by c i K d s i-d/2 .
In the integral (2.1), computing ρ is time-consuming (cf. [START_REF] Bach | Asymptotic semismoothness probabilities[END_REF]), especially if there are many candidates. We can use some coarser approximations. Since ρ(u) is a decreasing function of u, we want to choose a polynomial pair such that the size of |F (a, b)| and |G(a, b)| is small on average over all (a, b). This roughly requires that the coefficients of the polynomials are small in absolute value. We can compare polynomials using the logarithm of an L 2 -norm for the polynomial F (x, y) by

(2.2) 1 2 log s -d 1 -1 1 -1 F 2 (xs, y) dx dy
where s is the skewness of sieving region. Polynomials which minimize the expression (2.2) are expected to be better than others.

2.3. Root property. If a polynomial f (x) has many roots modulo small primes and prime powers, the polynomial values may behave more smoothly than random integers of about the same size. Boender, Brent, Montgomery and Murphy [START_REF] Boender | Factoring large integers with the quadratic sieve[END_REF][START_REF] Murphy | Modelling the Yield of Number Field Sieve Polynomials[END_REF][START_REF] Murphy | Polynomial selection for the number field sieve integer factorisation algorithm[END_REF][START_REF] Murphy | On quadratic polynomials for the number field sieve[END_REF] described some quantitative measures of this effect (root property).

Let p be a fixed prime. Let ν p (x) denote the exponent of the largest power of p dividing the integer x and ν p (0) = ∞. Let S be a set of integers. We use (the same) notation ν p (S) to denote the expected p-valuation of x ∈ S. If integers in S are random and uniformly distributed 1 , the expected p-valuation ν p (S) is

ν p (S) = E x∈S [ν p (x)] = ∞ k=1 Pr(ν p ≥ k) = ∞ k=1 1 p k = 1 p -1 .
Thus, in an informal (logarithmic) sense, an integer x in S contains an expected power p 1/(p-1) . Let now S be a set of polynomial values f (x). We use (the same) notation ν p (S) (or ν p (f )) to denote the expected p-valuation of the polynomial values S. Hensel's lemma gives conditions when a root of f (mod p k ) can be lifted to a root of f (mod p k+1 ). Lemma 2.2 (Hensel's lemma). Let r 1 be a root of f (x) modulo an odd prime p.

(1) If r 1 is a simple root, f (x) (mod p k ) has an unique root r k ≡ r 1 (mod p)

for each k > 1.

(

) If r k is a multiple root 2 of f (x) (mod p k ) for k ≥ 1, there are two possible cases. If p k+1 | f (r k ), then ∀ i ∈ [0, p), p k+1 | f (r k + i p k ). If p k+1 ∤ f (r k ), 2
r k cannot be lifted to a root modulo p k+1 .

Assume now that the integers x leading to the values f (x) ∈ S are uniformly random. There are two cases. First, suppose p ∤ ∆(f ), the discriminant of f (x), then p is an unramified prime, and hence f (x) (mod p) has only simple roots. Let n p be the number of roots for f (x) (mod p). The expected p-valuation of polynomial values is ν p (f ) = n p /(p -1) (apply the formula above, using Pr(

ν p ≥ k) = n p /p k ).
The second case is when p | ∆(f ). Here one may get multiple roots. The expected p-valuation may be obtained by counting the number of lifted roots.

Homogeneous polynomials.

In the number field sieve, we want to know the expected p-valuation of homogeneous polynomial values F (a, b), where (a, b) is a pair of coprime integers, and F (x, y) is the homogenous polynomial corresponding to f (x). We assume in the following that (a, b) is a uniformly random pair of coprime integers. We have

(2.3) ν p (F (a, b)) = ν p (F (λa, λb))
for any integer λ coprime to p. A pair of coprime integers (a, b) maps to a point (a : b) on the projective line P 1 (F p ). Because of property (2.3) above, pairs for which ν p (F (a, b)) > 0 correspond to the points of the zero-dimensional variety on P 1 (F p ) defined by the polynomial F . The projective line P 1 (F p ) has p + 1 points, consisting of p affine points which can be represented as (x : 1) with x ∈ F p , together with the point at infinity (1 : 0). Among these, the zeroes of F correspond, for affine points (x : 1), to affine roots x ∈ F p of the dehomogenized polynomial f . The point at infinity is a zero of F if and only if the leading coefficient c d of f cancels modulo p. If F has a total of n p affine and projective zeroes in P 1 (F p ), then F (a, b) for coprime (a, b) is divisible by p with probability n p /(p + 1).

It is also possible to look at (a, b) modulo a prime power p k . Then (a, b) maps to an equivalence class (a : b) on the projective line over the ring Z/p k Z. The p-valuation of F at (a : b) ∈ P 1 (Z/p k Z) (an integer between 0 and k -1, or "k or more") conveys the information of what happens modulo p k . There are p k + p k-1 points in P 1 (Z/p k Z) (p k affine points of the form (x : 1), while the remaining p k-1 points at infinity are written as (1 : py)). A coprime pair (a, b) chosen at random maps therefore to a given point in P 1 (Z/p k Z) with probability 1/(p k-1 (p + 1)).

Given an unramified p, let F (x, y) (mod p) have n p affine and projective roots (zeroes on P 1 (F p )). In application of the Hensel Lemma (applied to f at an affine root x, or to p d-1 f ( 1 py ) above the possible projective root), there is a constant number n p of points (a : b) = P 1 (Z/p k Z) such that ν p (F (a : b)) ≥ k, as k grows. The expected p-valuation ν p (F ) is thus:

(2.4) ν p (F ) = ∞ k=1 n p p k-1 (p + 1) = n p p p 2 -1 .
2 Let r k be a root of f (mod p k ). We say that r k is a multiple root of f (mod

p k ) if f ′ (r k ) ≡ 0 (mod p); otherwise it is a simple root.
For ramified p, simply counting the number n p of affine and projective roots modulo p is not sufficient to deduce ν p (F ). One can substitute n p by n p k (the number of roots modulo p k ) in the above summation. For convenience, one can also define a truncated version where

(2.5) ν p (F, e) = e k=1 n p k p k-1 (p + 1)
.

Murphy [17, p. 49] defines the α(F, B) function to compare the cumulative expected p-valuation of polynomial values to random integers of similar size. The function α(F, B) can be considered as the logarithmic benefit of using polynomial values compared to using random integers:

(2.6) α(F, B) = p≤B p prime 1 p -1 -ν p (F ) log p
where the summand can be written as 1 -n p p p + 1 log p p -1 when p is unramified.

In the number field sieve, α(F, B) is often negative since we are interested in the case when F (x, y) has on average more than one root modulo small primes.

2.4.

Steps in polynomial selection. Polynomial selection can be divided into three steps: polynomial generation, size optimization and root optimization.

In the polynomial selection, we first generate some polynomials of relatively good size (cf. Subsection 2.2). Two efficient algorithms are given by Kleinjung [START_REF] Kleinjung | On polynomial selection for the general number field sieve[END_REF][START_REF] Kleinjung | Polynomial selection[END_REF]. The size and root properties of these polynomials can then be further optimized using translation and rotation.

Translation of f (x) and g(x) by t ∈ Z/nZ gives a new polynomial pair f (x+t) and g(x + t). The new common root is m 1 /m 2 -t (mod n). Translation only affects the size property. Rotation by a polynomial λ(x) produces a new polynomial f λ(x) (x) = f (x) + λ(x) (m 2 x -m 1 ). The linear polynomial and common root is unchanged during rotation. λ(x) is often a linear or quadratic polynomial, depending on the size of n and the skewness of f (x). Rotation can affect both size and root properties.

Given a polynomial pair, translation and rotation are used to find a polynomial of smaller (skewed) norm (Equation (2.2)). This is called size optimization. After size optimization, many polynomials can have comparable size. Given f (x), we can use polynomial rotation to find a related polynomial f λ(x) (x) which has a much smaller α-value but similar size. This step is referred to as root optimization. If the skewness of the polynomial is large, the size property of the polynomial may not be altered significantly. As an indication of this, the skewed L ∞ norm of f , defined as max i |s i-d/2 c i |, remains unchanged as long as the trailing coefficients of f λ (x) do not dominate. This is true for the polynomials generated by the algorithm of Kleinjung [START_REF] Kleinjung | Polynomial selection[END_REF], where the skewness of the polynomials is likely to be large.

We discuss some algorithms for root optimization in the following sections. We will focus on rotation using linear polynomials. The idea naturally generalises to quadratic and higher degree rotations which are needed for large integers such as RSA-768 [START_REF] Kleinjung | Factorization of a 768-Bit RSA Modulus[END_REF] and RSA-896.

Root sieve

We consider linear rotations defined by f u,v (x) = f (x) + (ux + v)g(x). We want to choose (u, v) such that f u,v (x) has a small α-value. The straightforward way is to look at individual polynomials f u,v (x) for all possible (u, v)'s and compare their α-values. This is time-consuming and impractical since the permissible bounds for u and v are often huge. Murphy [17, p. 84] describes a sieve-like procedure, namely the root sieve, to find polynomials with good root properties. We describe the root sieve in Algorithm 1.

Let B be the upper bound for primes in Equation (2.6) and U, V be bounds for the linear rotation such that |u| ≤ U and |v| ≤ V . We often choose V ≈ sU (cf. Subsection 2.2). The root sieve fills an array with estimated α-values. The α-values are estimated from p-valuations for primes p ≤ B. Alternatively, it is sufficient to calculate the summation of the weighted p-valuations ν p (F ) log p for the purpose of comparison. The idea of the root sieve is that, when r is a root of f u,v (x) (mod p k ), it is also a root of f u+ip k ,v+jp k (x) (mod p k ) for i, j ∈ Z.

Algorithm 1: Murphy's root sieve Input : a polynomial pair f, g; integers U , V , B; Output: an array of approximated α-values of dimension (2U + 1) × (2V + 1); In general, the root sieve does not affect the projective roots significantly. It is sufficient to only consider the affine roots' contribution to the α-value. In the end, we identify good slots (those with small α-values) in the sieving array. For each slot (polynomial), we can compute a more accurate α-value with a large bound B > B and re-optimize its size using translation only (which will not affect the root property).

1 for p ≤ B, p prime do 2 for k where p k ≤ B do 3 for x ∈ [0, p k -1] do 4 for u ∈ [0, p k -1] do 5 compute v in f (x) + (ux + v)g(x) ≡ 0 (mod p k );
With B 2 ≪ U V , the asymptotic complexity of Murphy's root sieve is

p≤B p prime    ⌊ log B log p ⌋ k=1 p k p k O(1) + (2U + 1)(2V + 1) p 2k    = O B 3 log B + (2U + 1)(2V + 1) p≤B p prime log B log p ≈ (2U + 1)(2V + 1) log B B 2 1 log 2 p dp = O U V B log B .
We are interested in small primes and hence B/ log B is small. The sieving bounds U, V dominate the running time O(U V B/ log B).

A faster root sieve

In the root sieve, we compare the number of roots of polynomials f u,v (x) for small primes and prime powers. In most cases, the roots are simple. Hence their average p-valuation follows immediately from Equation (2.4), and there is no need to count the lifted roots. We describe a faster root sieve (Algorithm 2) taking advantage of this idea.

First, we show that the cases corresponding to simple roots (cf. Equation (2.4)) can be dealt with by a sieve. Suppose r 1 is a simple root of f (x) (mod p). There exists a unique lifted root r k of f (x) (mod p k ) for each k > 1. In addition, each lifted root r k is a simple root of f (x) (mod p). Let r k be a simple root of f u,v (x) (mod p k ) for some k ≥ 1. It is clear that r k is also a simple root of polynomials f u+ip k ,v+jp k (x) (mod p k ). Given a simple root r 1 of a polynomial f u,v (x) (mod p), the contribution of the root r 1 to ν p (F u,v ) is p/(p 2 -1). We can update this value3 for all rotated polynomials f u+ip,v+jp (x) in a sieve (Line 8 of Algorithm 2).

Second, we consider the multiple roots. Let r k be a multiple root of a rotated polynomial f u,v (x) (mod p k ). It is also a multiple root for rotated polynomials f u+ip k ,v+jp k (x) (mod p k ). Hence we can also update the score in a sieve, but only for rotated polynomials f u+ip k ,v+jp k (x) (mod p k ). The lifted roots of f u+ip k ,v+jp k (x) (mod p k+1 ) can have different behaviours (cf. Lemma 2.2). We need to lift to count the multiple roots (Line 10 of Algorithm 2).

Algorithm 2: A faster root sieve input : a polynomial pair f, g; integers U , V , B; output: an array of approximated α-values of dimension (2U + 1) × (2V + 1); Line 5 of Algorithm 2 describes the following optimization. Given some r ∈ Z/pZ, we want to know when r is a multiple root for some polynomial f u,v (x) (mod p). If f (r) + (ur + v)g(r) ≡ 0 (mod p) and f ′ (r) + ug(r) + (ur + v)g ′ (r) ≡ 0 (mod p), then we get

1 for p ≤ B, p prime do 2 for x ∈ [0, p -1] do 3 compute ũ such that ũg 2 (x) ≡ f (x)g ′ (x) -f ′ (x)g(x) (mod p); 4 for u ∈ [0, p -1] do 5 compute v such that f (x) + (ux + v)g(x) ≡ 0 (mod p); 6 if u = ũ;
(4.1) ug 2 (r) ≡ f (r)g ′ (r) -f ′ (r)g(r) (mod p)
since (ur + v) ≡ -f (r)/g(r) (mod p). Therefore, only one in p values of u admit a multiple root at r (mod p). For the other u's, we can compute v and update the simple contribution p/(p 2 -1) in the sieve. If however r is a multiple root of f u,v (x) (mod p), we have to lift to count the multiple roots.

The asymptotic running time has the same magnitude as Murphy's root sieve where

p≤B p prime p (p -1) (2U + 1)(2V + 1) p 2 + O U V p 2 = O U V B log B .
In practice, however, we benefit from this optimization which avoids most prime powers. For comparison, Murphy's root sieve takes about 4U V p≤B ⌊log B/ log p⌋ operations, while Algorithm 2 takes about 4U V p≤B 1 operations. Taking B = 200 for instance. p≤200 ⌊log 200/ log p⌋ = 60 and p≤200 1 = 46. Thus the speedup is about 1.3.

A two-stage method

If the permissible rotation bounds U, V are large, the root sieve can take a long time for each polynomial. We give a two-stage algorithm for the root optimization. The algorithm is motivated by previous work by Gower [START_REF] Gower | Rotations and translations of number field sieve polynomials[END_REF], Papadopoulos (personal communication), Stahlke and Kleinjung [START_REF] Stahlke | Ideas for finding better polynomials to use in GNFS[END_REF], who suggested to consider congruence classes modulo small primes.

The root optimization is based on the following ideas. A polynomial with only a few roots modulo small prime powers is less likely to have a small α-value. Therefore, rotated polynomials with many roots modulo small prime powers p ei i are first detected, with p i ≤ P for some tiny bound P ≪ B. How exactly the powers e i are chosen is discussed at the end of this section. A further root sieve (cf. Algorithm 2) for larger prime powers p ei i (where P < p i ≤ B and p ei i ≤ B) can then be applied. For convenience, let primes p i be ordered such that p i ≤ p j when i ≤ j.

Stage 1. Let p e1

1 , • • • , p es s be the distinct prime powers and such that p s ≤ P . Let M = s i=1 p ei i . In the first stage, we find some rotated polynomial f u0,v0 (x) which has the smallest approximated α-value (Equations (2.5) and (2.6)) among all u, v ∈ Z/M Z.

Gower [START_REF] Gower | Rotations and translations of number field sieve polynomials[END_REF] described an algorithm to find such f u0,v0 (x). The method first fixes some root set {r i,j } modulo p ei i and then finds the rotated coefficients (u 0,i , v 0,i ) (mod p ei i ). Finally, the CRT (Chinese Remainder Theorem) is applied to recover (u 0 , v 0 ) (mod M ). However, it is not guaranteed that such (u 0 , v 0 ) leads to the smallest α-value among all u, v ∈ Z/M Z given the root set being fixed in advance. We describe a better method based on the lifting idea in Section 4.

Let p ei i be fixed. We first find some polynomial f u0,i,v0,i (x) that has good 4 approximated p i -valuation ν pi (F u,v , e i ) (cf. Equation (2.5)) among all u, v ∈ Z/p ei i Z. We use the lifting method in a p 2 i -ary tree (of height e i ) where each node represents some rotated polynomial f u,v modulo some ẽi ≤ e i . A depth-search method can be used since the bottom level leaves of the tree are most interesting. The number of nodes in this p 2 i -ary tree (of height e i ) can be bounded above by p ei i using the relation in Equation (4.1). Given polynomials f u0,i,v0,i (x) (mod p ei i ) for all 1 ≤ i ≤ s, we can then use the CRT to recover a set of good pairs {(u 0 , v 0 ) (mod M )}.

Stage 2.

Fix some (u 0 , v 0 ) (mod M ). We apply the root sieve on the sublattice defined by (u 0 + γM, v 0 + βM ) where (γ, β) ∈ Z 2 . The points on the sublattice are expected to give rotated polynomials with promising root properties, since the polynomials are constructed to have many roots modulo M .

In Stage 1, we often choose the p i 's to be the smallest consecutive primes since they are likely to contribute most to the α-value. The exponents e i can be chosen such that M ≈ U in practice. Note U ≪ V if s is large. Since u 0 ≈ M ≈ U , it is sufficient to sieve a single line in Stage 2.

Compared to a full root sieve over Z 2 , the search space is reduced by a factor of M 2 . The root sieve in Stage 2 runs asymptotically in U V (B-P )/(M 2 log(B-P )) ≈ (V /M )(B/ log B) as B ≪ V and P ≪ B.

Remark 5.1. In Stage 2, the polynomials f not on the sublattice are discarded since we assume that they are unlikely to give rise to polynomials with good root properties: the sum of the approximated p i -valuations s i=1 ν pi ( F , e i ) log p i is smaller than s i=1 ν pi (F, e i ) log p i . However, it may be possible that s i=1 ν pi ( F ) log p i ≥ s i=1 ν pi (F ) log p i (for the exact p i -valuations). Here we assume that ν pi (F ) ≈ ν pi (F, e i ) which is plausible if the number of lifted multiple roots becomes stationary for p k i ≥ p ei i (but also see below in 5.3).

Choice of the valuations e i .

There are several approaches to choosing the valuations e i in Stage 1. To start with, for consistency with the rest of the procedure, it is natural to restrict to p ei i ≤ B, whence e i ≤ ⌊log pi B⌋. It is also reasonable to require that polynomials f u,v considered in Stage 2, for u, v within the lattice (u 0 + γM, v 0 + βM ), all share the same lifting patterns for their p i -adic roots (in terms of numbers of roots and multiplicities as lifting proceeds), which is to say that the number of lifted roots for these polynomials should be stationary above p ei i . This would imply that we set e i to at most ν pi (disc f u,v ), since setting to a larger value would not differentiate between lifting patterns. Of course the dependency of the latter expression on u, v is cumbersome. An upper bound would be needed, and can be obtained with moderate efforts by considering disc f u,v as a bivariate polynomial in u, v. In practice, however, it is generally satisfactory to restrict to the bound ν pi (disc f ) as a first guess.

Another aspect leads to consider the maximum values for e i in a more relaxed way. So far, in our improved root sieve, we have ignored the size property of polynomials in the algorithms. In practice, we may want to tune the parameters by trying several sets of parameters (varying p i 's and e i in Stage 1). We can run a test root sieve in short intervals. The set of parameters which generates the best score (considering both size and root properties) is then used. To summarize, while a bound such as e i = min(ν pi (disc f ), ⌊log pi B⌋) would be advised by the analysis, efficiency considerations lead us to consider several sets of parameters around this value. This compensates for the acknowledged inaccuracy in considering ν pi (disc f ).

Conclusion

Root optimization aims to produce polynomials that have many roots modulo small primes and prime powers. We gave some faster methods for root optimization based on Hensel's lifting lemma and root sieve on congruence classes modulo small prime powers. The algorithms described here have been implemented in the software CADO-NFS [START_REF] Bai | CADO-NFS, an implementation of the number field sieve algorithm[END_REF] and tested in practice (e.g. for the factorization of the 704-bit RSA challenge [START_REF] Bai | Factorisation of RSA-704 with CADO-NFS[END_REF]).

di=0 c i m i 1 m d-i 2 .

 2 i=0 c i x i and g(x) = m 2 x-m 1 . The standard method to generate such polynomial pairs is to expand n in base-(m 1 , m 2 ) so n = d The running time of sieving depends on the smoothness of the polynomial values |F (a, b)| and |G(a, b)|. Let Ψ(x, x 1/u ) be the number of x 1/u -smooth integers below 2010 Mathematics Subject Classification. Primary 11Y05, 11Y16. c XXXX American Mathematical Society 1

2. 2 .

 2 Size property. Let (a, b) be pairs of coprime integers in the sieving region Ω. For the moment, we assume that a rectangular sieving region is used where |a| ≤ K and 0 < b ≤ K. We also assume that polynomial values |F (a, b)| and |G(a, b)| behave like random integers of similar size. The number of sieving reports (coprime pairs that lead to smooth polynomial values) can be approximated multiplier 6/π 2 accounts for the probability of a, b being relatively prime.Since G is a linear polynomial, we may assume that log(|G(a, b)|) does not vary much across the sieving region. A simplified approximation to compare polynomials (ignoring the constant multiplier) is to compare (

6 update

 6 νp(F u+ip k ,v+jp k ) by sieving;

7 then 8 update

 78 νp(F u+ip,v+jp ) in sieving; 9 else 10 lift to count multiple roots of fū,v(x) (mod p k ) such that (ū, v) ≡ (u, v) (mod p), ū, v ≤ p k ≤ B and then sieve;

We consider integer random variables within a large enough bounded sample space.

νp(Fu,v) log p, the contribution of the root r 1 (mod p) to α(Fu,v, B).

Acknowledgements

The authors are grateful to Pierrick Gaudry, Guillaume Hanrot, Thorsten Kleinjung, Jason Papadopoulos and Paul Zimmermann for many helpful comments and discussions on drafts of this paper. The authors would also like to thank an anonymous referee for valuable comments and suggestions.

The work of the first author was carried out at the Australian National University (ANU). He would like to thank the Research School of Computer Science (ANU) for funding and the Mathematical Sciences Institute (ANU) for providing computing facilities (orac) and support. He would also like to thank NeSI (New Zealand eScience Infrastructure) and the Centre for eResearch at the University of Auckland for providing computing facilities and support.