Michaël Mignard

Peter Schauenburg

MODULAR CATEGORIES ARE NOT DETERMINED BY THEIR MODULAR DATA MICHAËL MIGNARD AND

come

Introduction

A modular category is a braided spherical fusion category such that the square matrix S whose coefficients are the traces of the square of the braiding on pairs of simple objects is invertible. This S-matrix, together with the T-matrix, which is diagonal and contains the values of a kink on the simple objects, defines a projective representation of the modular group on the complexified Grothendieck ring of the category. The two matrices together are referred to as the modular data of the modular category.

The modular data constitute a very important invariant of modular categories, both powerful for the structure theory and classification of such categories, and central to their role in mathematical physics and low-dimensional topology. For the theory of modular categories, and their background in mathematical physics, we refer generally to [START_REF] Bakalov | Lectures on tensor categories and modular functors[END_REF].

It is a natural question whether the modular data constitute a complete invariant of modular tensor categories, or at least modular tensor categories in some interesting class. The authors of [START_REF] Bruillard | Rank-finiteness for modular categories[END_REF] expressed their belief that this is true for integral modular categories; it is the present authors' impression, however, that the research community in general, including perhaps the authors of [START_REF] Bruillard | Rank-finiteness for modular categories[END_REF], did not have great faith in that conjecture. Still, it seems that to this date no explicit example was known of two modular categories that share the same modular data without being equivalent as modular categories. In recent computer-based work, the authors have provided evidence rather in favor of the conjecture: The twisted Drinfeld doubles of finite groups up to order 31 which have the same modular data are 2020 Mathematics Subject Classification. 18D10,16T05,20C15. equivalent; altogether, there are 1126 inequivalent nontrivial modular categories that arise in this fashion. In fact they are already distinguished by the coefficients of the T-matrices taken together with the values of the higher Frobenius-Schur indicators for simple objects; this is a potentially weaker invariant in general.

The present paper now exhibits a family of examples showing in fact that arbitrarily many modular categories can share the same modular data without being equivalent as braided tensor categories. Moreover, our examples are found among the particularly accessible class of module categories over twisted Drinfeld doubles of finite groups. In our examples the categories in each family either have identical modular data, or they are distinguished by their T-matrices.

Preliminaries

Throughout the paper we consider fusion categories in the sense of [START_REF] Etingof | On fusion categories[END_REF] defined over the field of complex numbers. A general reference for the theory of fusion categories is [START_REF] Etingof | Tensor categories[END_REF]. We denote Vect ω G the category of finite dimensional G-graded vector spaces with associativity constraint given by a normalized three-cocycle ω : G 3 → C × . We note that G is determined by the fusion category Vect ω G as its Grothendieck ring, and that Vect ω G and Vect ν G are equivalent as fusion categories if and only if there is an automorphism f of G such that ν and f * ω are cohomologous.

A group-theoretical fusion category is a fusion category which is categorically Morita equivalent to a pointed fusion category, see [Ost03], and [START_REF] Nikshych | Morita equivalence methods in classification of fusion categories[END_REF] for an overview, or [START_REF] Etingof | Tensor categories[END_REF]9.7] We note several elementary types of equivalences between grouptheoretical fusion categories:

If f : G ′ → G is an isomorphism of groups, then C(G, H, ω, µ) and C(G ′ , f -1 (H), f * ω, f * µ) are equivalent. If θ : G 2 → C × is a cochain, then C(G, H, ω, µ) and C(G, H, ωdθ, µθ) are equivalent. In particular, C(G, H, ω, µ) is equivalent to C(G, H, ω ′ , 1) where ω ′ = ωd θ-1 with any extension θ of θ to G × G. If λ : H → C × is a cochain, then C(G, H, ω, µ) is equivalent to C(G, H, ω, µdλ).
Two fusion categories are categorically Morita equivalent if and only if their Drinfeld centers are equivalent braided monoidal categories [START_REF] Etingof | On fusion categories[END_REF]. The Drinfeld center of Vect ω G is equivalent to the module category of the twisted Drinfeld double D ω (G) introduced in [START_REF] Dijkgraaf | Quasi Hopf algebras, group cohomology and orbifold models[END_REF]; the modular data of these modular categories is the focus of [START_REF] Coste | Finite group modular data[END_REF].

Pointed fusion categories of rank pq

Let p, q be odd primes such that p|q -1. It is well-known that there exist exactly two non-isomorphic groups of order pq, namely the cyclic group and a nonabelian group, denoted G in the sequel, which is a semidirect product Z q ⋊ Z p = Z q ⋊ n Z p in which the generator of Z p acts on Z q as multiplication by an element n of multiplicative order p in Z q . Let κ : Z 3 p → C × denote a representative of a generator of the cohomology group H 3 (Z p , C × ) ∼ = Z p . We can assume that κ takes values in p-th roots of unity.

We note for later use that the automorphism of Z p given by multiplication with m ∈ Z (prime to p) induces the action on H 3 (Z p , C × ) ∼ = Z p given by multiplication with m 2 . This can be deduced by a direct calculation with the well-known periodic Z p -resolution of Z [ML95, IV.7]. A more conceptual proof uses the structure of the integral cohomology ring of Z p and the fact that the group has periodic cohomology, cf. [START_REF] Cartan | Homological algebra[END_REF][START_REF] Brown | Cohomology of groups[END_REF]. In fact H 3 (Z p , C × ) ∼ = H 4 (Z p , Z), and an isomorphism between H k (Z p , Z) and H k+2 (Z p , Z) is given by multiplication with a generator η of H 2 (Z p , Z) ∼ = Z p in the cohomology ring. Thus H 4 (Z p , Z) ∼ = Z p is generated by η 2 ; the action of m on H 2 (Z p , Z) is given by the action on Z p , and thus the action on H 4 (Z p , Z) is given by m 2 . Now we can define p pointed fusion categories C 0 , . . .

C p-1 by C u = Vect ω u G where ω = Inf G Zp κ is the inflation of κ to G. Lemma 3.1.
The categories C 0 , . . . , C p-1 are pairwise not categorically Morita equivalent. Equivalently, the Drinfeld centers Z(C 0 ), . . . , Z(C p-1 ) are pairwise inequivalent braided monoidal categories.

Proof. Any automorphism of G fixes the unique subgroup of order q and induces the identity on the quotient Z p . Thus, the p pointed categories are pairwise inequivalent fusion categories. The only fusion categories categorically Morita equivalent to C u are the group-theoretical fusion categories C(G, H, ω, µ) where ω is a three-cocycle on G mapped to ω u by an automorphism of G, H is a subgroup of G and µ is a two-cochain on H whose coboundary is the restriction of ω. For C(G, H, ω, µ) to be pointed, it is necessary (see e.g. [START_REF] Naidu | Categorical Morita equivalence for group-theoretical categories[END_REF]) that H be abelian and normal in G. Now the only three-cocycle mapped to ω u by an automorphism of G is ω u itself. The only nontrivial abelian normal subgroup is H = Z q , and the restriction of ω u to H is trivial, so µ has to be a two-cocycle. Since the second cohomology group of H is trivial, we can assume that µ is trivial outright. In this case the category C(G, H, ω u , 1) is explicitly known [GMN07, Thm.2.1] in the form Vect α G ′ and can be described as follows: G ′ is the semidirect product of Z p with the dual group of Z q under the dualized action, and α = Inf G ′ Zp κ u . If we identify Z q with its dual, this means that G ′ = Z q ⋊ n ′ Z p , with the generator of Z p acting as multiplication with the multiplicative inverse n ′ = n p-1 of n modulo q. This in turn means that G ∼ = G ′ , with the isomorphism inducing the inversion map on the quotient Z p . But the inversion map, or multiplication by -1, acts as the identity on H 3 (Z p , C × ), so the isomorphism pulls Inf G ′ Zp κ u back to ω u , and we conclude that C(G, H, ω u , 1) is equivalent to C u as a fusion category.

For the primary purpose of the present paper having found the p distinct categories above is sufficient -we will see in the next section that they afford only three distinct modular data. For completeness we will continue and classify all pointed fusion categories of dimension pq up to categorical Morita equivalence: Lemma 3.2. Let p < q be primes. Then two pointed fusion categories of rank pq are categorically Morita equivalent if and only if they are equivalent monoidal categories.

(1) If p is odd and p | q -1, then there are exactly p + 9 equivalence classes of pointed fusion categories of dimension pq, namely the p categories defined above, and nine categories of the form Vect α Zp×Zq .

(2) If p is odd and p ∤ q -1, there are exactly nine equivalence classes of pointed fusion categories of dimension pq.

(3) If p = 2, then there are exactly 12 equivalence classes of pointed fusion categories of dimension pq.

Proof. We have H 3 (Z p , C × ) ∼ = Z p , and the automorphism of Z p given by multiplication with x ∈ Z × p acts on the cohomology group as multiplication with x 2 ; thus there are three orbits, namely zero, the quadratic residues, and the quadratic nonresidues (except when p = 2, where there are two orbits). The same holds for q, and thus H 3 (Z p × Z q , C × ) ∼ = Z p × Z q has 3 • 3 = 9 orbits under the action of the automorphism group of Z p × Z q if p > 2, and 6 if p = 2. It is easy to see that the nine, resp. six pointed fusion categories thus obtained are categorically Morita equivalent only to themselves. Now let p|q -1. The cohomology groups of the nonabelian group G of order pq (are surely well-known and) can be readily computed using [ML95, Cor.10.8]: For the unique subgroup H of order q there is a short exact sequence

0 → H 3 (Z p , C × ) → H 3 (G, C × ) → H 3 (Z q , C × ) Zp → 0.
If the generator of Z p acts on Z q as multiplication by x, it acts on H 3 (Z q , C × ) as multiplication by x 2 . Thus, if p > 2, the action is nontrivial, the invariants are trivial, and every cohomology class is inflated from Z p , giving the p categories we have already studied.

If p = 2 (so G is a dihedral group), then the action is trivial, thus H 3 (G, C × ) ∼ = Z 2 ×Z q . Any automorphism of Z q extends to an automorphism of G, thus the automorphism group of G acts on the cohomology group as Z q acts on its cohomology group, giving three orbits on Z q , and thus six orbits on Z 2 × Z q .

Equivalence of modular data

We will now determine to what extent the modular data distinguish the centers of the pointed categories of dimension pq listed in the previous section. We will first concentrate on showing that the p pointed fusion categories with noncommutative Grothendieck ring from the start of the previous section have too few distinct modular data to be distinguished by them. This gives the desired counterexample in the paper's title. The main trick is an application of Galois group actions, on the one hand on the cocycles' values, on the other hand in the form of the Galois action defined on modular fusion categories in general.

We will then proceed to investigate to what extent exactly the modular data distinguish centers of pointed fusion categories of dimension pq.

Consider the situation of lemma 3.1. The p different cocycles ω u are not so fundamentally different: With the exception of ω 0 , any two of them are mapped to each other by an element of the absolute Galois group of abelian extensions Γ := Gal(Q ab /Q). In fact there is σ ∈ Γ such that for each i we get ω u = σ j ω for some j ∈ {0, ..., p -2}: it suffices to arrange σ(ζ p ) = ζ m p for a primitive root m modulo p. It is quite tempting to simply declare as obvious: Proposition 4.1. Denote S (u) , T (u) the modular data of Z(Vect

ω u G ). Let σ ∈ Γ satisfy σ(ζ p ) = ζ m
p for m a primitive root modulo p. Then there are bijections p r between the simples of Z(Vect ω G ) and Z(Vect

σ r ω G ) = Z(Vect ω m r G ) such that S (v)
pr(i),pr(j) = σ r (S

(1) ij ) and T (v)

pr(i) = σ r (T (1)
i ) when v ≡ m r (p).

A rather informal argument would be the following: The definition of Vect ω G depends on the choice of a p-th root of unity involved in the definition of our standard generator of the third cohomology group. Of course, neither the category thus defined, nor anything constructed from it (like the Drinfeld center with its braiding, or the modular data) can crucially depend on that choice. Any other choice will only lead to analogous constructions, with the root of unity replaced in the appropriate way by another root.

We will give a somewhat more precise argument in the following

Proof. The simple objects of Z(Vect ω G ), which is the module category over the twisted Drinfeld double D ω (G), were given in [START_REF] Dijkgraaf | Quasi Hopf algebras, group cohomology and orbifold models[END_REF]; the simples are parametrized by pairs (g, χ), where g ∈ G represents a conjugacy class, and χ is an irreducible α g -projective character of the centralizer C G (g); here α g is a certain two-cocycle on C G (g) computed from ω. We can assume that χ is the character of a projective matrix representation ρ whose matrix coefficients are in a cyclotomic field. When we replace ω by σω, then α g changes to σα g , applying σ to the matrix coefficients of ρ yields a σα g -projective representation, whose character is σχ. In [START_REF] Coste | Finite group modular data[END_REF], formulas are given that compute the modular data of Z(Vect ω G ) in terms of the group structure, the cocycle ω, and the projective characters representing the simple objects. Now applying σ to a matrix coefficient of the S-or T -matrix amounts to applying σ to the values of all the characters and cocycles involved in the formula in [START_REF] Coste | Finite group modular data[END_REF]; the bijection p r therefore just maps the simple corresponding to the pair (g, χ) to that corresponding to (g, σ r χ).

Next, we consider the Galois action defined for any modular fusion category, originating in [START_REF] De | Markov traces and II 1 factors in conformal field theory[END_REF][START_REF] Coste | Remarks on Galois symmetry in rational conformal field theories[END_REF]; see [START_REF] Etingof | On fusion categories[END_REF]Appendix]. Since our modular category C = Z(Vect ω G ) is integral, there is, for each σ ∈ Γ, a unique permutation σ of the simple objects of C such that σ(S ij ) = S i,σ(j) (in the general case this is true up to a sign). Thus σ 2 (S ij ) = S σ(i),σ(j) . In addition, it is shown in

[DLN15] that σ 2 (T ii ) = T σ(i),σ(i) .
Combined with the preceding remark, we obtain Corollary 4.2. There are at most three different sets among the modular data of the p modular fusion categories Z(Vect ω u G ). More precisely, the modular data of Z(Vect

σ r (ω) G
) only depends on the parity of r, so that at least (p -1)/2 of these categories share the same modular data.

In particular, for p > 3 the modular data of the categories Z(Vect ω u G ) does not distinguish them up to braided equivalence, and for a prime p > 2k there are k pairwise braided inequivalent categories among the Z(Vect ω u G ) that share the same modular data. Note that the smallest example thus obtained is for the nonabelian group of order 55; the rank of the twisted double is 49.

This completes the task of finding the counterexample indicated in the present paper's title. We will give a "better" counterexample in the next section, but first we continue to analyze the modular data for completeness:

The group G = Z q ⋊ n Z p has the presentation

G = a, b|a q = b p = 1, bab -1 = a n .
There are q-1 p + p conjugacy classes of G. A set of representatives of those classes is given by:

{b k , k ∈ {0, . . . , p -1}} ∪ {a l , n l ≡ 1 (mod p)}
For our calculations we choose a representative for a generator of the third cohomology group

H 3 (Z p , C × ) ∼ = Z p , namely [MS89, (E.14)] (4.1) κ( j, k, l) := exp 2πi p 2 [l]([j] + [k] -[j + k])
where, for a integer m, m denotes its class in Z p and [m] ∈ {0, . . . , p-1} with m ≡ [m] (mod p).

The simple D ω (G)-modules are parametrized by couples (g, χ) where g is a representative of a conjugacy class in G, and χ is the character of an irreducible α g -projective representation of the centralizer C G (g), where the 2-cocycle α g on C G (g) is given by:

α g (x, y) := ω(g, x, y)ω -1 (x, g, y)ω(x, y, g) Finally, the element of the T -matrix of D ω (G) -Mod corresponding to a simple (g, χ) is the scalar θ(g, χ) := χ(g)/χ(1 G ).
Proposition 4.3. For odd prime numbers p and q such that p|q -1, there are exactly 3 different T -matrices for the p non-equivalent modular tensor categories Z(Vect ω u G ), where G := Z q ⋊ n Z p . Proof. Take first a representative of a conjugacy class of G of the form a l where l ∈ {0, . . . , q -1} is such that n l ≡ 1 (mod p). The centralizer in G of this representative is the cyclic group Z q generated by a. So, its third cohomology group is trivial; moreover, as ω is inflated from the quotient G/ a , the cocycle α a l is trivial on C a l (G) ∼ = Z q . Therefore, the α a l -projective representations of Z q , and with them the q-1 p × q associated elements of the T -matrix of Z(Vect ω u G ) do not depend on the choice of the 3-cocycle ω u on G. Now, take the trivial element 1 G = b p ∈ G. As all the cocycles we consider are normalized, the 2-cocycle α 1 G on G is trivial and again, the q-1 p + p associated elements of the T -matrix do not depend on the choice of the 3-cocycle on G.

So, the only conjugacy classes that may lead to elements of T that depend on the cocycle are the ones represented by b k with k ∈ {1, . . . , p -1}; there are p 2 associated entries of the T -matrix. Take such a k, and also an integer u ∈ {1, . . . , p -1}. We compute explicitly the elements of the T -matrix of Z(Vect

k , letting (k, m) ∈ {0, . . . , p -1} 2 correspond to (b k , χ m ′ 0 ) where m ′ k ≡ m(p) if k ≡ 0(p) and m ′ = m otherwise. Then θ(b k , χ m ′ 0 ) = χ m ′ 0 (b k )µ b k (b k ) = exp 2πim ′ k p exp 2πik 2 u p 2 = exp 2πi p 2 (mp + k 2 u) . Thus {θ(b k , χ m ′ 0 )|m = 0, . . . , p -1} = {ζ x p 2 |x ≡ k 2 u(p)} = {z ∈ C|z p = ζ k 2 u
p } for each k ∈ {0, . . . , p -1}. For k = 0 this gives the set of p-th roots of unity, and the union over the remaining values of k only depends on whether u is a quadratic residue modulo p or not: The values of θ(b k , χ m ′ 0 ) for k ∈ {1, . . . , p -1} and m ∈ {0, . . . , p -1} are the p-th roots of the powers ζ x p where xu is a quadratic residue modulo p; each value occurs exactly twice. To conclude, we just need to observe that for the trivial cocycle, all the µ g are trivial for the representative g of any conjugacy class of G.

Corollary 4.4. The twisted doubles of groups of order 3q with a prime q > 3 are classified by their modular data.

More counterexamples

The module categories of twisted Drinfeld doubles are fusion categories defined over a cyclotomic field, and for such categories a Galois twist can be defined [START_REF] Davidovich | On Arithmetic Modular Categories[END_REF]; clearly the categories found above which share the same modular data are Galois twists of each other. One might be tempted to immediately refine the refuted conjecture: Perhaps modular fusion categories defined over a cyclotomic field can only share the same modular data if they are, at worst, Galois twists of each other? Consider three primes p < q < r such that p divides both q -1 and r -1. Let G q be the semidirect product group considered above, define G r in the same way, and consider G = G q × G r . Further define ω uv := Inf G Gq Inf Gq Zp (κ u ) • Inf G Gr Inf Gr Zp κ v . The same arguments as above show that the categories C uv := Vect ωuv G are pairwise not categorically Morita equivalent (Again, any automorphism leaves ω uv invariant, and the only abelian normal subgroups are Z q , Z r , and Z q × Z r ).

The modular data for Z(Vect ωuv G ) is the Kronecker product of the modular data for Z(Vect ω u Gq ) and Z(Vect ω v Gr ). Thus, there are at most 3• 3 = 9 different modular data. But the effect of a Galois automorphism on ω uv is a cyclic permutation of {1, . . . , p -1} which is to be applied to u and v simultaneously (unless u or v is zero). Thus, there are p + 1 orbits of cocycles, and thus p + 1 categories among the Z(Vect ωuv G ) that are pairwise inequivalent, even up to a Galois twist.

Of course one may argue that the inequivalent up to Galois twist examples are thus obtained due to a cheap trick: They are Deligne products of two modular categories, and we simply have a separate Galois twist on each factor. Question 5.1. If two modular categories defined over the cyclotomic numbers are prime in the sense of [START_REF] Müger | On the structure of modular categories[END_REF], and if they share the same modular data, are they then Galois twists of each other? Is the module category of a twisted Drinfeld double D ω (G) of an indecomposable group determined up to Galois twist by its modular data? Email address: michael.mignard@u-bourgogne.fr

Email address: peter.schauenburg@u-bourgogne.fr Institut de Mathématiques de Bourgogne, UMR 5584 CNRS, Université Bourgogne Franche-Comté, F-21000 Dijon, France

  ω u G ) corresponding to the representative b k . The centralizer of b k in G is the cyclic group Z p generated by b. So, the cocycle α b k is a coboundary. Take a 1-cochain µ b k such that ∂µ b k = α b k . Then the α b k -projective representations of Z p are usual representations twisted by µ b k . A generator χ 0 of b is given by: χ 0 (b) := exp 2πi p Take m ∈ {0, . . . , p -1}. The T -matrix element corresponding to the couple (b k , χ m 0 ) is given by θ(b k , χ m 0 ) = χ m 0 (b k )µ b k (b k ) We need now to compute the scalar µ b k (b k ). From 4.1, it is easy to see that α b k (x, y) = ω u (x, y, b k ) = exp 2πi p 2 ku([x] + [y] -[x + y]) , and so µ b k (x) = exp 2πi p 2 ku[x] . Finally we renumber the simples corresponding to b

  Module categories, weak Hopf algebras and modular invariants. Transform. Groups, 8(2):177-206, 2003.

  . Any group-theoretical fusion category categorically Morita equivalent to Vect ω G can be described in terms of a couple (H, µ) where H is a subgroup of G and µ : H × H → C × is a two-cochain with dµ = ω| H×H×H . The last condition ensures that the twisted group algebra C µ [H], which has H as a basis and multiplication x • y = µ(x, y)xy for x, y ∈ H, is an associative algebra in the fusion category Vect ω

	G . The associated group-theoretical
	fusion category C(G, H, ω, µ) is the category of endofunctors of the
	category of C µ [H]-modules in Vect ω G . A slightly more elementary (but
	equivalent by Watts' theorem) description is that C(G, H, ω, µ) is the
	category of bimodules in Vect ω G over the algebra C µ [H], with the tensor
	product of bimodules taken over C µ [H].


Abderrahmane Nitaj
email: abderrahmane.nitaj@unicaen.fr

Muhammad Rezal
email: rezal@upm.edu.my

Kamel Ariffin

Dieaa I Nassr

Hatem M Bahig
email: hmbahig@sci.asu.edu.eg

Muhammad Rezal Kamel

New Attacks on the RSA Cryptosystem

Keywords: RSA, Cryptanalysis, Factorization, LLL algorithm, Simultaneous diophantine approximations, Coppersmith's method

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The RSA cryptosystem [START_REF] Rivest | A Method for Obtaining digital signatures and public-key cryptosystems[END_REF] is currently the most widely known and widely used public key cryptosystem. The main parameters in RSA are the RSA modulus N and the public exponent e. The modulus N = pq is the product of two large primes of equal bit-size and e satisfies gcd(e, φ(N )) = 1 where φ(N ) = (p -1)(q -1) is the Euler totient function. The integer d satisfying ed ≡ 1 (mod φ(N )) is the private exponent. The RSA cryptosystem is deployed in various application systems for encryption, signing and for providing privacy and ensuring authenticity of digital data. Therefore, most research is focused on reducing the encryption/decryption execution time or the signature verification/generation time. For example, to reduce the decryption time or the signature generation time, one may wish to use a small private exponent d. Unfortunately, based on the convergents of the continued fraction expansion of e N , Wiener [START_REF] Wiener | Cryptanalysis of short RSA secret exponents[END_REF] showed that the RSA cryptosystem is insecure when d < N 1/4 . Boneh and Durfee [START_REF] Boneh | Cryptanalysis of RSA with private key d less than N 0.292[END_REF] proposed an extension of Wiener's attack that allows the RSA cryptosystem to be broken when d < N 0.292 . Their Method is based on lattice basis reduction techniques. Similarly, Blömer and May [START_REF] Blömer | A generalized Wiener attack on RSA[END_REF] proposed an extension of Wiener's attack and showed that the RSA cryptosystem is insecure if there exist three integers x, y and z satisfying ex -yφ(N ) = z with x < 1 3 N 1/4 and |z| < exN -3/4 . Their method combines lattice basis reduction techniques and the continued fraction algorithm. In general, the use of short secret exponent encounters serious security problem in various instances of RSA. A typical example is when a single user generates many instances of RSA (N, e i ) with the same modulus and small private exponents [START_REF] Howgrave-Graham | Extending Wieners attack in the presence of many decrypting exponents[END_REF]. Another example is when a single user generates k instances of RSA (N i , e i ), each with the same small private exponent d. Using k equations e i d -k i φ(N i ) = 1, Hinek [START_REF] Hinek | On the Security of Some Variants of RSA[END_REF] showed that it is possible to factor the k modulus N i if d < N δ with δ = k 2(k+1) -ε where ε is a small constant depending on the size of max N i . Similarly, to improve the computational efficiency of server-aided signature generation (see [START_REF] Steinfeld | An advantage of Low-Exponent RSA with Modulus Primes Sharing Least Significant Bits[END_REF]), one may use RSA with a modulus N = pq such that the prime factors p and q share a large number of least significant bits (LSBs). The security of this variant of RSA has been analyzed under the partial key exposure attacks in [START_REF] Steinfeld | An advantage of Low-Exponent RSA with Modulus Primes Sharing Least Significant Bits[END_REF], [START_REF] Steinfeld | On the Security of RSA with Primes Sharing Least-Significant Bits[END_REF], [START_REF] Zhao | Small private-exponent attack on RSA with primes sharing bits[END_REF], and [START_REF] Sun | Cryptanalysis of Short Exponent RSA with Primes Sharing Least Significant Bits[END_REF]. In [START_REF] Sun | Cryptanalysis of Short Exponent RSA with Primes Sharing Least Significant Bits[END_REF], Sun et al. showed that RSA is more vulnerable in the situation when p and q share a large number of LSBs than the standard scenario when the prime factors p and q differ in the first LSBs. When e = N γ , they showed that RSA is vulnerable if |p -q| = 2 m x with 2 m = N α and d < N δ whenever δ < 7 6 -2 3 α -1 3

(1 -4α)(1 -4α + 6γ). For example, if γ = 1, and α = 0.2, then δ < 0.662, that is, RSA is insecure if the private exponent is such that d < N 0.662 . In [START_REF] Howgrave-Graham | Extending Wieners attack in the presence of many decrypting exponents[END_REF], Howgrave-Graham and Seifert extended Wiener's attack in the presence of many decryption exponents for a single RSA modulus. They showed that RSA is insecure if one knows two public exponents e 1 and e 2 such that the corresponding private exponents d 1 and d 2 satisfy d 1 , d 2 < N 0.357 . In [START_REF] Sarkar | Cryptanalysis of RSA with two decryption exponents[END_REF], Sarkar and Maitra improved this bound up to d 1 , d 2 < N 0.416 .

In this paper, we present three new attacks on RSA. The first attack works for k ≥ 2 moduli N i = p i q i , i = 1, . . . , k, when k instances (N i , e i ) are such that there exist an integer x, k integers y i , and k integers z i satisfying e i x -y i φ(N i ) = z i . We show that the k RSA moduli N i can be factored in polynomial time if N = min i N i and

x < N δ , y i < N δ , |z i | < p i -q i 3(p i + q i ) y i N 1/4 where δ = k 2(k + 1)
.

The second attack works when the k instances (N i , e i ) of RSA are such that there exist an integer y, and k integers x i , and k integers z i satisfying e i x i -yφ(N i ) = z i . Similarly, we show that the k RSA moduli N i can be factored in polynomial time if N = min i N i , min i e i = N α , and

x i < N δ , y < N δ , |z i | < p i -q i 3(p i + q i )
yN 1/4 where δ = (2α -1)k 2(k + 1) .

In both scenarios, we transform the equations into a simultaneous diophantine problem and apply lattice basis reduction techniques to find the parameters (x, y i ) or (y, x i ). This leads to a suitable approximation of p i + q i which allows us to apply Coppersmith's method [START_REF] Coppersmith | Small solutions to polynomial equations, and low exponent RSA vulnerabilities[END_REF] to compute the prime factors p i and q i of the moduli N i .

The third attack enables us to factor an RSA modulus N = pq when the prime factors share their LSBs in the presence of two public exponents e 1 and e 2 such that the corresponding decryption exponents d 1 and d 2 share their MSBs. To be more precise, suppose that e = N γ , |p -q| = 2 m x with 2 m = N α , and

|d 1 -d 2 | < N β . We show that one can factor the RSA modulus if d 1 , d 2 < N δ under the condition δ < 5 2 -2α -β - 1 4 6(1 -4α)(5 + 4γ -4α -4β). (1)
As an example, observe that, in the situation that γ = 1, α = 0.2, and β = δ, that is d 1 and d 2 differ in the first MSBs, then the condition (1) gives δ < 0.736 which improves the bound δ < 0.662 obtained in [START_REF] Sun | Cryptanalysis of Short Exponent RSA with Primes Sharing Least Significant Bits[END_REF]. On the other hand, in the standard situation γ = 1, α = 0, and β = δ, that is when the prime integers p, q do not share any LSBs and d 1 , d 2 do not share any MSBs, the condition (1) gives δ < 0.422 which also improves the bound δ < 0.416 found in [START_REF] Sarkar | Cryptanalysis of RSA with two decryption exponents[END_REF]. Our method is based on Coppersmith's method for solving polynomial equations The remainder of this paper is organized as follows. In Section 2, we review the tools that we apply in the scenarios, namely Coppersmith's method, lattice basis reduction and simultaneous diophantine approximations. We also present some useful results that will be used through the paper. In Section 3, we present the first attack. In Section 4, we present the second attack and in Section 5, we present the third attack. We conclude in Section 6.

Preliminaries

In this section, we give some basics on Coppersmith's method, lattice basis reduction techniques and simultaneous diophantine equations that will be used in this paper.

Coppersmith's method

At Eurocrypt'96, Coppersmith [START_REF] Coppersmith | Small solutions to polynomial equations, and low exponent RSA vulnerabilities[END_REF] proposed an algorithm for finding small roots of bivariate integer polynomial equations in polynomial-time. The algorithm is based on the LLL algorithm [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF] for lattice reduction. A clever application of Coppersmith's algorithm is to factor an RSA modulus N = pq when half of the least significant or most significants bits of p are known.

Theorem 1 (Coppersmith). Let N = pq be the product of two unknown integers such that q < p < 2q. Given an approximation of p with additive error term at most N 1 4 , then p and q can be found in polynomial time.

Coppersmith's method has been heuristically extended to many variables. To find the small roots of a multivariate polynomial f (x 1 , • • • , x n ), we construct a set of coprime polynomials with small coefficients which contain the same roots over the integers. This can be done by applying the LLL algorithm to a lattice that can be built using the strategy of Jochemsz and May [START_REF] Jochemsz | A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants[END_REF]. To this end, a practical way is the use the following result of Howgrave-Graham [START_REF] Howgrave-Graham | Finding small roots of univariate modular equations revisited[END_REF].

Theorem 2 (Howgrave-Graham). Let h(x 1 , • • • , x n ) ∈ Z[x 1 , • • • , x n ] be a polynomial with at most ω monomials. Suppose that h x (0) 1 , • • • , x (0) n ≡ 0 (mod R) where |x (0) i | < X i for i = 1, . . . , n, and h(x 1 X 1 , • • • , x n X n ) < R √ ω . Then h x (0) 1 , • • • , x (0) n
= 0 holds over the integers.

To find the small roots of the first polynomials of the LLL-reduced basis, we can use Gröbner bases or evaluation of resultants.

Lattice reductions and simultaneous diophantine approximations

Let u 1 . . . , u d be d linearly independent vectors of R n with d ≤ n. The set of all integer linear combinations of the vectors u 1 . . . , u d is called a lattice and is in the form

L = d i=1 x i u i | x i ∈ Z .
The set (u 1 , . . . , u d ) is called a basis of L and d is its dimension. The determinant of L is defined as det(L) = det(U T U ) where U is the the matrix of the u i 's in the canonical basis of R n . Define v to be the Euclidean norm of a vector v ∈ L. A central problem in lattice reduction is to find a short non-zero vector in L. The LLL algorithm of Lenstra, Lenstra, and Lovász [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF] produces a reduced basis and answers positively but partially this problem. The following result fixes the sizes of the reduced basis vectors (see [START_REF] May | New RSA Vulnerabilities Using Lattice Reduction Methods[END_REF]).

Theorem 3. Let L be a lattice of dimension ω with a basis {v 1 , . . . , v ω }. The LLL algorithm produces a reduced basis

{b 1 , • • • , b ω } satisfying b 1 ≤ b 2 ≤ • • • ≤ b i ≤ 2 ω(ω-1)
4(ω+1-i det(L)

1 ω+1-i , for all 1 ≤ i ≤ ω.
One important application of the LLL algorithm is that it provides a solution to the simultaneous diophantine approximations problem which is defined as follows. Let α 1 , . . . , α n be n real numbers and ε a real number such that 0 < ε < 1. A classical theorem of Dirichlet asserts that there exist integers p 1 , • • • , p n and a positive integer q ≤ ε -n such that

|qα i -p i | < ε for 1 ≤ i ≤ n.
In 1982, Lenstra, Lenstra and Lovász [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF] described a method to find simultaneous diophantine approximations to rational numbers. In their work, they considered a lattice with real entries. We state below a similar result for a lattice with integer entries.

Theorem 4 (Simultaneous Diophantine Approximations).

There is a polynomial time algorithm, for given rational numbers α 1 , . . . , α n and 0 < ε < 1, to compute integers p 1 , • • • , p n and a positive integer q such that max

i |qα i -p i | < ε and q ≤ 2 n(n-3)/4 • 3 n • ε -n .
Proof. See Appendix A.

Primes sharing LSBs

The following lemma is reformulation of a result of [START_REF] Steinfeld | On the Security of RSA with Primes Sharing Least-Significant Bits[END_REF]. It concerns an RSA modulus N = pq when the prime factors p and q share an amount of their LSBs.

Lemma 1. Let N = pq be an RSA modulus with q < p < 2q. Suppose that p -q = 2 m u for a known value m. Then p = 2 m p 1 + u 0 and q = 2 m q 1 + u 0 where u 0 is a solution of the equation

x 2 ≡ N (mod 2 m ) and p + q = 2 2m v + v 0 with v 0 ≡ 2u 0 + N -u 2 0 u -1 0 (mod 2 2m ).
Proof. See Appendix B.

Approximations of the primes in RSA

Let N = pq be an RSA modulus with q < p < 2q. Then p + q satisfies the following inequalities (see [START_REF] Nitaj | Another generalization of Wiener's attack on RSA[END_REF])

2 √ N < p + q < 3 √ 2 √ N 2 . ( 2
)
The following result shows that any approximation of p + q will lead to an approximation of p.

Lemma 2. Let N = pq be an RSA modulus with q < p < 2q. Suppose we know an approximation S of p + q such that S > 2N 1 2 and |p + q -S| < p -q 3(p + q) N 1 4 .

Then P = 1 2 S + √ S 2 -4N is an approximation of p satisfying |p -P | < N 1 4 .
Proof. See Appendix C.

Remark 1. Notice that in Section 4.1.2 of the ANSI X9.31:1998 standard for public key cryptography [START_REF]ANSI Standard X9.31-1998, Digital Signatures Using Reversible Public Key Cryptography for the Financial Services Industry (rDSA)[END_REF], there are a number of recommendations for the generation of the primes in N = pq. One criteria is that the primes p, q shall satisfy p -q > 2 -100 √ N . Combining with (2) when q < p < 2q and N > 2 1024 , this implies that the term p-q 3(p+q) N

1 4 satisfies p -q 3(p + q) N 1 4 > 2 -100 √ N 9 √ 2 2 √ N • 2 256 = 2 157 9 √ 2 .
This shows that, when N = pq > 2 1024 and the prime factors p and q are chosen following the ANSI X9.31:1998 standard, the approximation extra term

(p-q) 3(p+q) N 1 4 of p + q is not too small.

The First Attack on k RSA Moduli

In this section, we are given k ≥ 2 moduli N i = p i q i with the same size N . We suppose in this scenario that the RSA moduli satisfy k equations e i x-y i φ(N i ) = z i . Notice that the parameters φ(N i ) = (p i -1)(q i -1) are also unknown. We show that it is possible to factor the RSA moduli N i if the unknown parameters x, y i and z i are suitably small.

Theorem 5. For k ≥ 2, let N i = p i q i , 1 ≤ i ≤ k, be k RSA moduli. Let N = min i N i . Let e i , i = 1, . . . , k, be k public exponents. Define δ = k 2(k+1) . If there exist an integer x < N δ and k integers y i < N δ and |z i | < pi-qi 3(pi+qi) y i N 1/4 such that e i x -y i φ(N i ) = z i for i = 1, . . . , k, then one can factor the k RSA moduli N 1 , • • • N k in polynomial time.
Proof. For k ≥ 2 and i = 1, . . . , k, the equation e i x -y i φ(N i ) = z i can be rewritten as e i x -y i (N i + 1) = z i -y i (p i + q i ). Hence

e i N i + 1 x -y i = |z i -y i (p i + q i )| N i + 1 . (3)
Let N = min i N i and suppose that y i < N δ and |z i | < pi-qi 3(pi+qi) y i N 1/4 . Then 4 . Since by (2) we have

|z i | < y i N 1/4 < N δ+
p i + q i < 3 √ 2 2
√ N , we will get

|z i -y i (p i + q i )| N i + 1 ≤ |z i | + y i (p i + q i ) N < N δ+1/4 + 3 √ 2 2 N δ+1/2 N < √ 5N δ+1/2 N = √ 5N δ-1/2 .
Plugging in (3), we get

e i N i + 1 x -y i < √ 5N δ-1/2 .
We now proceed to prove the existence of the integer x.

Let ε = √ 5N δ-1/2 , δ = k 2(k+1)
. We have

N δ = N k/2-kδ < 2 k(k-3)/4 • 3 k • √ 5N δ-1/2 -k = 2 k(k-3)/4 • 3 k • ε -k . It follows that if x < N δ , then x < 2 k(k-3)/4 • 3 k ε -k . Summarizing, for i = 1, . . . , k, we have e i N i + 1 x -y i < ε, x < 2 k(k-3)/4 • 3 k • ε -k .
It follows that the conditions of Theorem 4 are fulfilled which will find x and y i for i = 1, . . . , k. Next, using the equation e i x -y i φ(N i ) = z i , we get

p i + q i = N i + 1 - e i x y i + z i y i . Since |z i | < pi-qi 3(pi+qi) y i N 1/4 , then zi yi < pi-qi 3(pi+qi) N 1/4 and S i = N i + 1 -eix
yi is an approximation of p i + q i with an error of at most pi-qi 3(pi+qi) N 1/4 . Hence, using Lemma 2, we can find an approximation Pi = 1 2

S i + S 2 i -4N i of p i such that |p i -Pi | < N 1/4 .
Then, for each i = 1, . . . , k, we find p i using Theorem 1. This leads to the factorization of the k RSA moduli N 1 , . . . , N k .

Remark 2. It is conjectured in [START_REF] Boneh | Cryptanalysis of RSA with private key d less than N 0.292[END_REF] that an RSA instance with a modulus N = pq and a public exponent e is insecure if ed -yφ(N ) = 1 with d < N 1/2 . This conjecture can be related to Theorem 5 as follows. Suppose that k RSA moduli N 1 , • • • , N k and k public exponents e 1 , . . . , e k satisfy e 1 d-y 1 φ(N 1 ) = 1 and e i d-

y i φ(N i ) = z i , i = 2, . . . , k, where d < N δ , y i < N δ 1 and |z i | < pi-qi 3(pi+qi) y i N 1/4 with δ = k 2(k+1) . Then, by Theorem 5, one can factor the RSA moduli N 1 , • • • , N k .
Observe that, for sufficiently large k, we have δ ≈ 1 2 , which answer positively the conjecture in this case. 5N δ-1/2 ≈ 0.000757. Using [START_REF] Sarkar | Cryptanalysis of RSA with two decryption exponents[END_REF] with n = k = 3, we find

C = 3 n+1 • 2 (n+1)(n-4) 4 • ε -n-1 = 123330787675873.
Consider the lattice L spanned by the matrix

M =     1 -[Ce 1 /(N 1 + 1)] -Ce 2 /(N 2 + 1)] -[Ce 3 /(N 3 + 1) 0 C 0 0 0 0 C 0 0 0 0 C     .
Then, applying the LLL algorithm to L, we get a reduced basis with the matrix from which we deduce x = 3779027519, y 1 = 2963128168, y 2 = 978749302 and y 3 = 312187655. Using x and y i for i = 1, 2, 3, define S i = N i + 1 -eix yi . We get

K =     -3779027519, -
S 1 = 73202632183869, S 2 = 152156156125079, S 3 = 102878795201660. For i = 1, 2, 3, let D i = S 2 i -4N i . We get D 1 = 1098771258961, D 2 = 10306351764921, D 3 = 74513749733949.
By Lemma 2, for i = 1, 2, 3, Pi = 1 2 (S i + D i ) is a candidate for an approximation of p i . Applying Coppersmith's method 1 with Pi for i = 1, 2, 3, we get

p 1 = 37150702190747, p 2 = 81231254125183, p 3 = 88696272470797.
This leads us to the factorization of the 3 RSA moduli N 1 , N 2 and N 3 . Observe that x > N 0.344 is much larger than Blőmer-May's bound x < 1 3 N 1/4 . This shows that Blömer-May's attack will not give the factorization of the RSA moduli in this example.

The Second Attack on k RSA Moduli

In this section, we consider the second scenario when the k RSA moduli satisfy k equations of the shape e i x i -yφ(N i ) = z i where the parameters x i , y and z i are suitably small unknown parameters. Theorem 6. For k ≥ 3, let N i = p i q i , 1 ≤ i ≤ k, be k RSA moduli with the same size N . Let e i , i = 1, . . . , k, be k public exponents with min i e i = N α . Let δ = (2α-1)k 2(k+1) . If there exist an integer y < N δ and k integers x i < N δ and

|z i | < pi-qi 3(pi+qi) yN 1/4 such that e i x i -yφ(N i ) = z i for i = 1, . . . , k, then one can factor the k RSA moduli N 1 , • • • N k in polynomial time.
Proof. For i = 1, . . . , k, the equation e i x i -yφ(N i ) = z i can be transformed into e i x i -y(N i + 1) = z i -y(p i + q i ). Hence

N i + 1 e i y -x i = |z i -y(p i + q i )| e i . (4)
Let N = max i N i . Suppose that y < N δ and |z i | < pi-qi 3(pi+qi) yN 1/4 . Also, suppose that min i e i = N α . Since by [START_REF] Blömer | A generalized Wiener attack on RSA[END_REF] we have

p i + q i < √ 3 2 √ N i , then we get |z i -y(p i + q i )| e i ≤ |z i | + y(p i + q i ) N α < N δ+ 1 4 + 3 √ 2 2 N δ+ 1 2 i N α < √ 5N δ+ 1 2 N α = √ 5N δ+ 1 2 -α .
Using this in (4), we get

N i + 1 e i y -x i < √ 5N δ+ 1 2 -α .
We now proceed to prove the existence of y and the integers

x i . Let ε = √ 5N δ+ 1 2 -α , δ = (2α-1)k 2(k+1)
. We have

N δ ε k = 5 k 2 N δ+kδ+ k 2 -kα = 5 k 2 .
Then, since 5

k 2 < 2 k(k-3) 4 • 3 k for k ≥ 2, we get N δ ε k < 2 k(k-3)/4 • 3 k . It follows that if y < N δ , then y < 2 k(k-3)/4 • 3 k ε -k . Summarizing, we have N i + 1 e i y -x i < ε, y < 2 k(k-3)/4 • 3 k • ε -k , for i = 1, . . . , k,
It follows that the conditions of Theorem 4 are fulfilled and we will obtain y and x i for i = 1, . . . , k. Next, by utilizing the equation e i x i -yφ(N i ) = z i , we get

p i + q i = N i + 1 - e i x i y + z i y .
Since |z i | < pi-qi 3(pi+qi) yN 1/4 , then |zi| y < pi-qi 3(pi+qi) N 1/4 and S i = N i + 1 -eixi y is an approximation of p i + q i with an error of at most pi-qi 3(pi+qi) N 1/4 . Hence, using Lemma 2, we can find an approximation Pi = 1 2 S i + S 2 i -4N i of p i such that |p i -Pi | < N 1/4 . Then, using Theorem 1, we find p i for i = 1, . . . , k. This leads to the factorization of the k RSA moduli N 1 , . . . , N k .

Example 2. Consider the following three RSA moduli and three public exponents Then N = max(N 1 , N 2 , N 3 ) = 701404527220444023808491592451. We also get min(e 1 , e 2 , e 3 ) = N α with α ≈ 0.9791. Since k = 3, we get δ = k(2α-1) 2(k+1) = 0.359325 and ε = √ 5N δ+1/2-α ≈ 0.000595. Using [START_REF] Sarkar | Cryptanalysis of RSA with two decryption exponents[END_REF] with n = k = 3, let

N 1 = 701404527220444023808491592451,
C = 3 n+1 • 2 (n+1)(n-4) 4 • ε -n-1 = 323072188568099.
Consider the lattice L spanned by the the rows of the matrix

M =     1 -[C(N 1 + 1)/e 1 ] -C(N 2 + 1)/e 2 ] -[C(N 3 + 1)/e 3 0 C 0 0 0 0 C 0 0 0 0 C     .
Then, applying the LLL algorithm to L, we get a reduced basis with the matrix From the first row, we deduce y = 9963214223, x 1 = 11669001827, x 2 = 17178297583, and x 3 = 11494200282. Using y and x i for i = 1, 2, 3, define

K =     9963214223
S i = N i + 1 -eixi y . We get S 1 = 1677562597323852, S 2 = 1169977613299368, S 3 = 1377024442150848. For i = 1, 2, 3, let D i = S 2 i -4N i . We get D 1 = 92726258730590, D 2 = 467404129426390, D 3 = 414122540907110.
By Lemma 2, for i = 1, 2, 3, Pi = 1 2 (S i + D i ) is a candidate for an approximation of p i . Applying Coppersmith's method 1 with Pi for i = 1, 2, 3, we get

p 1 = 885144428027221, p 2 = 818690871362879, p 3 = 895573491528979.
This leads to the factorization of the three RSA moduli N 1 , N 2 and N 3 . Observe that min(x 1 , x 2 , x 3 ) > N 0.337 is much larger than Blömer-May's bound x < 1 3 N 1/4 . This shows that Blömer-May's attack does not work in this case.

The Third Attack on RSA With Primes and Decryption Exponents Sharing Bits

In this section, we present the attack which applies when the prime factors of an RSA modulus share an amount of their LSBs in the presence of two decryption exponents d 1 and d 2 sharing an amount of their MSBs. Proof. Suppose that e 1 and e 2 are two public exponents satisfying e

1 d 1 -k 1 φ(N ) = 1, e 2 d 2 -k 2 φ(N ) = 1.
Multiplying the first equation by e 2 and the second by e 1 and subtracting, we get

e 1 e 2 (d 1 -d 2 ) -e 2 k 1 φ(N ) + e 1 k 2 φ(N ) = e 2 -e 1 . (5)
Suppose that p -q = 2 m u. Then, Lemma 1 shows that p + q is in the form

p + q = v 0 + 2 2m v where v 0 ≡ 2u 0 + N -u 2 0 u -1 0 (mod 2 2m
) and u 0 is a solution of the modular equation x 2 ≡ N (mod 2 m ). Hence

φ(N ) = N + 1 -(p + q) = N + 1 -v 0 -2 2m v.
Plugging this in (5), we get

e 1 e 2 (d 1 -d 2 ) -e 2 k 1 N + 1 -v 0 -2 2m v + e 1 k 2 N + 1 -v 0 -2 2m v = e 2 -e 1 .
which can be rewritten as

e 1 e 2 (d 1 -d 2 ) -e 2 (N + 1 -v 0 )k 1 + 2 2m e 2 k 1 v + e 1 (N + 1 -v 0 )k 2 -2 2m e 1 k 2 v + (e 1 -e 2 ) = 0. ( 6
)
Fix the known and the unknown parameters as follows

               a 1 =e 1 e 2 , a 2 =-e 2 (N + 1 -v 0 ), a 3 =2 2m e 2 , a 4 =e 1 (N + 1 -v 0 ), a 5 =-2 2m e 1 , a 6 =e 1 -e 2 ,
and

       x 1 =d 1 -d 2 , x 2 =k 1 , x 3 =k 2 , x 4 =v.
Hence, the equation ( 6) becomes a 1 x 1 + a 2 x 2 + a 3 x 2 x 4 + a 4 x 3 + a 5 x 3 x 4 + a 6 = 0. Consider the polynomial

f (x 1 , x 2 , x 3 , x 4 ) = a 1 x 1 + a 2 x 2 + a 3 x 2 x 4 + a 4 x 3 + a 5 x 3 x 4 + a 6 . Then (d 1 -d 2 , k 1 , k 2 , v) is a root of f (x 1 , x 2 , x 3 , x 4
) which can be small enough to be found by Coppersmith's technique. To find the small roots of f (x 1 , x 2 , x 3 , x 4 ) using this method, we use the extended strategy of Jochemsz and May [START_REF] Jochemsz | A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants[END_REF]. We will need the following bounds.

• max(e 1 , e 2 ) = N γ , • max(d 1 , d 2 ) < N δ , • |d 1 -d 2 | < X 1 = N β , • k 1 = e1d1-1 φ(N ) < X 2 = N γ+δ-1 , • k 2 = e2d2-1 φ(N ) < X 3 = N γ+δ-1 , • p -q = 2 m u with 2 m = N α and α < 1 4 . • By (2) and Lemma 1, p + q = 2 2m v + v 0 with v < X 4 = 3N 1/2-2α .
Observe that α < 1 4 , otherwise p and q can be found using Coppersmith's metho [START_REF] Coppersmith | Small solutions to polynomial equations, and low exponent RSA vulnerabilities[END_REF]. Let us fix the bounds of the unknown parameters

X 1 = N β , X 2 = N γ+δ-1 , X 3 = N γ+δ-1 , X 4 = 3N 1/2-2α . (7)
Let m and t be two positive integers. Define the set

S = 0≤j≤t {x i1 1 x i2 2 x i3 3 x i3+j 3 x i1 1 x i2 2 x i3 3 x i4 4 monomial of f m-1 }.
and the set

M = {monomials of x i1 1 x i2 2 x i3 3 x i4 4 f x i1 1 x i2 2 x i3 3 x i4 4 ∈ S}.
Neglecting the coefficients, it is easy to find that f m-1 (x 1 , x 2 , x 3 , x 4 ) satisfies

f m-1 (x 1 , x 2 , x 3 , x 4 ) = m-1 i1=0 m-1-i1 i2=0 m-1-i1-i2 i3=0 i2+i3 i4=0 x i1 1 x i2 2 x i3 3 x i4 4 .
This leads to the characterization of the monomials x i1 1 x i2 2 x i3 3 x i4 4 of S:

x i1 1 x i2 2 x i3 3 x i4 4 ∈ S if        i 1 =0, . . . , m -1, i 2 =0, . . . , m -1 -i 1 , i 3 =0, . . . , m -1 -i 1 -i 2 , i 4 =0, . . . , i 2 + i 3 + t.
We also easily find

x i1 1 x i2 2 x i3 3 x i4 4 ∈ M if        i 1 =0, . . . , m, i 2 =0, . . . , m -i 1 , i 3 =0, . . . , m -i 1 -i 2 , i 4 =0, . . . , i 2 + i 3 + t. Define W = f (x 1 X 1 , x 2 X 2 , x 3 X 3 , x 4 X 4 ) ∞ = max(|a 1 |X 1 , |a 2 |X 2 , |a 3 |X 2 X 3 , |a 4 |X 4 , |a 5 |X 4 X 3 , |a 6 |).
Then W satisfies

W ≥ |a 2 |X 2 = e 2 (N + 1 -v 0 )N γ+δ-1 ≈ N 2γ+δ . (8)
Next, define

R = W X m-1 1 X m-1 2 X m-1 3 X m-1+t 4 .
Without loss of generality, suppose that a 6 = e 1 -e 2 is coprime with R. We define f (x 1 , x 2 , x 3 , x 4 ) = a -1 6 f (x 1 , x 2 , x 3 , x 4 ) (mod R) so that f (0, 0, 0, 0) = 1. Next, define the polynomials

g i1,i2,i3,i4 = x i1 1 x i2 2 x i3 3 x i4 4 f X m-1-i1 1 X m-1-i2 2 X m-1-i3 3 X m-1+t-i4 4 , with x i1 1 x i2 2 x i3 3 x i4 4 ∈ S, h i1,i2,i3,i4 = x i1 1 x i2 2 x i3 3 x i4 4 R, with x i1 1 x i2 2 x i3 3 x i4 4 ∈ M S.
The monomials of M S reduce to x i1 1 x i2 2 x i3 3 x i4 4 with (x 1 , x 2 , x 3 , x 4 ) ∈ S i for i = 1, 2, 3 where

S 1 = {x i1 1 x i2 2 x i3 3 x i4 4 } for        i 1 =m, i 2 =0, . . . , m -i 1 , i 3 =0, . . . , m -i 1 -i 2 , i 4 =0, . . . , i 2 + i 3 + t. S 2 = {x i1 1 x i2 2 x i3 3 x i4 4 } for        i 1 =0, . . . , m -1, i 2 =m -i 1 , i 3 =0, . . . , m -i 1 -i 2 , i 4 =0, . . . , i 2 + i 3 + t. S 3 = {x i1 1 x i2 2 x i3 3 x i4 4 } for        i 1 =0, . . . , m -1, i 2 =0, . . . , m -1 -i 1 , i 3 =m -i 1 -i 2 , i 4 =0, . . . , i 2 + i 3 + t.
As shown in [START_REF] Jochemsz | A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants[END_REF], we use the coefficients of g i1,i2,i3,i4 (x 1 X 1 , x 2 X 2 , x 3 X 3 , x 4 X 4 ) and h i1,i2,i3,i4 (x 1 X 1 , x 2 X 2 , x 3 X 3 , x 4 X 4 ) to build a basis of a lattice L with dimension

ω = x i 1 1 x i 2 2 x i 3 3 x i 4 4 ∈M 1 = 1 12 (m + 1)(m + 2)(m + 3)(m + 2t + 2).
The following ordering of the monomials is performed to construct an upper triangular matrix: if

i j < i j then x i1 1 x i2 2 x i3 3 x i4 4 < x i 1 1 x i 2 2 x i 3 3 x i 4
4 and if i j = i j then the monomials are lexicographically ordered. The diagonal entries of the matrix are of the form

(X 1 X 2 X 3 ) m-1 X m-1+t 4 for the polynomials g W X m-1+i1 1 X m-1+i2 2 X m-1+i3 3 X m-1+t+i4 4
for the polynomials h. Define

s j = x i 1 1 x i 2 2 x i 3 3 x i 4 4 ∈M \S i j , for j = 1, . . . , 4. (9)
The determinant of L is then

det(L) = W |M \S| X (m-1+t)|S|+(m-1+t)|M \S|+s4 4 3 j=1 X (m-1)|S|+(m-1)|M \S|+sj j = W |M \S| x (m-1+t)ω+s4 4 3 j=1 X (m-1)ω+sj j .
All the polynomials g(x 1 , x 2 , x 3 , x 4 ) and h(x 1 , x 2 , x 3 , x 4 ) and their combinations share the root (d

1 -d 2 , k 1 , k 2 , v) modulo R.
Applying the LLL algorithm to the lattice L with the basis spanned by the polynomials g(x 1 X 1 , x 2 X 2 , x 3 X 3 , x 4 X 4 ) and h(x 1 X 1 , x 2 X 2 , x 3 X 3 , x 4 X 4 ), we get a new basis with short vectors. Let f i (x 1 X 1 , x 2 X 2 , x 3 X 3 , x 4 X 4 ), i = 1, 2, 3 be three short vectors of the reduced basis. Each f i is a combination of g and h, and then share the root (d

1 -d 2 , k 1 , k 2 , v).
Then, by Theorem 3, we have for i = 1, 2, 3

f i (x 1 X 1 , x 2 X 2 , x 3 X 3 , x 4 X 4 ) < 2 ω(ω-1) 4(ω-2) det(L) 1 ω-2 .
For i = 1, 2, 3, we force the polynomials f i to satisfy Howgrave-Graham's bound

f i (x 1 X 1 , x 2 X 2 , x 3 X 3 , x 4 X 4 ) < R √ ω . A sufficient condition is 2 ω(ω-1) 4(ω-2 det(L) 1 ω-2 < R √ ω ,
which can be transformed into det(L) < R ω , that is

W |M \S| x (m-1+t)ω+s4 4 3 j=1 X (m-1)ω+sj j < W X m-1 1 X m-1 2 X m-1 3 X m-1+t
Using ( 9), we easily get

s 1 = 1 12 m(m + 1)(m + 2)(m + 2t + 1), s 2 = 1 24 m(m + 1)(m + 2)(3m + 4t + 5), s 3 = 1 24 m(m + 1)(m + 2)(3m + 4t + 5), s 4 = 1 24 (m + 1)(m + 2)(3m 2 + 5m + 8tm + 6t + 6t 2 ).
Similarly, we get

|S| = x i 1 1 x i 2 2 x i 3 3 x i 4 4 ∈S 1 = 1 12 m(m + 1)(m + 2)(m + 2t + 1).
Set t = τ m, then, Using this, and after simplifying by m 4 , the inequation (10) transforms into

s 1 = 1 12 (2τ + 1)m 4 + o(m 4 ),
X 1 12 (2τ +1) 1 X 1 24 (4τ +3) 2 X 1 24 (4τ +3) 3 X 1 24 (6τ 2 +8τ +3) 4 < W 1 12 (2τ +1) .
Substituting the values of X 1 , X 2 , X 3 , X 4 from ( 7) and W from (8), we get

1 12 (2τ + 1)β + 1 24 (4τ + 3)(γ + δ -1) + 1 24 (4τ + 3)(γ + δ -1) + 1 24 (6τ 2 + 8τ + 3) 1 2 -2α < 1 12 (2τ + 1)(2γ + δ),
or equivalently, (6 -24α)τ 2 + (8β + 8δ -8 -32α)τ + 4γ + 4β + 8δ -9 -12α < 0.

For the optimal value τ = 2(1+4α-β-δ)

3 (1-4α) , this reduces to

-8δ 2 + (40 -32α -16β)δ + 16α 2 -48γα + 16βα + 8α + 28β -35 + 12γ -8β 2 < 0, which is valid if δ < 5 2 -2α -β - 1 4 6(1 -4α)(5 + 4γ -4α -4β).
Under this condition, we find four polynomials, namely f , f 1 , f 2 and f 3 with the root (d

1 -d 2 , k 1 , k 2 , v).
Using the resultant technique, we find the solution

(d 1 -d 2 , k 1 , k 2 , v).
Using v, we compute p -q = 2 m v. Since N = pq, we get p 2 -2 m vp -N = 0 which leads to the factorization of the RSA modulus N = pq. This terminates the proof.

Comparison with former attacks

We compare the bound on δ of Theorem 7 with two former bounds, namely the bound obtained by Sarkar and Maitra in [START_REF] Sarkar | Cryptanalysis of RSA with two decryption exponents[END_REF] and the bound obtained by Sun et al. in [START_REF] Sun | Cryptanalysis of Short Exponent RSA with Primes Sharing Least Significant Bits[END_REF].

5.2.1

Comparison with the bound of Sarkar and Maitra. In [START_REF] Sarkar | Cryptanalysis of RSA with two decryption exponents[END_REF], Sarkar and Maitra showed that for d 1 , d 2 < N δ , and

|d 1 -d 2 | < N β , RSA is insecure if δ < 5 8 -1 2 β.
To compare this with the bound of Theorem 7, we consider γ = 1 and α = 0 in the next result. This corresponds to the situation when e 1 ≈ e 2 ≈ N and p and d differ in their first LSBs. Proof. This is a direct application of Theorem 7 with γ = 1 and α = 0.

In Table 1, we compare the bound δ < Table 1. Comparison of the new method with the method of [START_REF] Sarkar | Cryptanalysis of RSA with two decryption exponents[END_REF].

One may note that when d 1 and d 2 differ in their first MSBs, then β = δ and the bound of Sarkar and Maitra is valid if δ < 5 12 ≈ 0.416, while the bound of Corollary 1 gives δ < 0.422.

5.2.2

Comparison with the bound in Sun et al. In [START_REF] Sun | Cryptanalysis of Short Exponent RSA with Primes Sharing Least Significant Bits[END_REF], Sun et al. showed that RSA is insecure when e = N γ , p -q = 2 m v with 2 m = N α , and d < N δ , if δ < 7 6 -2 3 α -1 3

(1 -4α)(1 -4α + 6γ). To compare our method with the method of Sun et al., we consider Theorem 7 with β = δ, that is when d 1 and d 2 do not share any amount of their MSBs. We get the following corollary.

Corollary 2. Let N = pq be an RSA modulus such that p -q = 2 m u where 2 m ≈ N α . Let e 1 and e 2 be two public exponents satisfying e 1 , e 2 ≈ N γ , and

e 1 d 1 -k 1 φ(N ) = 1, e 2 d 2 -k 2 φ(N ) = 1. Suppose that d 1 , d 2 ≤ N δ . Then one can factor N in polynomial time if δ < 17 16 - 1 4 α - 1 16 3(1 -4α)(3 + 32γ -12α).
Proof. In the bound of δ in Theorem 7, if we plug β = δ and solve the inequation for δ, we get the desired bound on δ.

In Table 2, we compare the largest values of δ of Corollary 2 and the the largest values obtained in [START_REF] Sun | Cryptanalysis of Short Exponent RSA with Primes Sharing Least Significant Bits[END_REF] for various values of γ = log N (e) and α = log N (2 m ).

γ = log N (e) γ = 1 γ = 0.9 γ = 0.8 γ = 0.7 γ = 0.6

Bound for δ in [START_REF] Sun | Cryptanalysis of Short Exponent RSA with Primes Sharing Least Significant Bits[END_REF] with α = 0 0.284 0.323 0.363 0.406 0.451 New bound for δ with α = 0 0.422 0.452 0.483 0.516 0.552 Bound for δ in [START_REF] Sun | Cryptanalysis of Short Exponent RSA with Primes Sharing Least Significant Bits[END_REF] with α = 0.1 0.436 0.467 0.500 0.534 0.570 New bound for δ with α = 0.1 0.550 0.573 0.598 0.625 0.653 Bound for δ in [START_REF] Sun | Cryptanalysis of Short Exponent RSA with Primes Sharing Least Significant Bits[END_REF] with α = 0.2 0.662 0.680 0.699 0.720 0.742 New bound for δ with α = 0.2 0.736 0.750 0.764 0.780 0.797 Bound for δ in [START_REF] Sun | Cryptanalysis of Short Exponent RSA with Primes Sharing Least Significant Bits[END_REF] with α = 0.25 1 1 1 1 1 New bound for δ with α = 0.25 1 1 1 1 1

Table 2. Comparisons of the new method with the method of [START_REF] Sun | Cryptanalysis of Short Exponent RSA with Primes Sharing Least Significant Bits[END_REF] for α = log N (2 m ).

Conclusion

For k ≥ 2 and i = 1, . . . , k, let (N i , e i ) be k RSA instances with k moduli N i = p i q i and k public exponents e i . In this paper, we proposed a new method to factor all the RSA moduli N 1 , . . . , N k in the scenario that the RSA instances satisfy k equations of the shape e i x -y i φ(N i ) = z i or of the shape e i x i -yφ(N i ) = z i with suitably small parameters x i , y i , z i , x, y where φ(N i ) = (p i -1)(q i -1).

We also proposed an attack on RSA when the prime factors p and q of the RSA modulus N = pq are of the same bit-size. The attack factors N when p and q share a number of their least significant bits (LSBs) in the presence of two public exponents e 1 and e 2 with decryption exponents d 1 and d 2 sharing an amount of their most significant bits (MSBs).

A Proof of Theorem 4

Proof. Let ε ∈ (0, 1). Set

C = 3 n+1 • 2 (n+1)(n-4) 4 • ε -n-1 , ( 11
)
where x is the integer greater than or equal to x. Consider the lattice L spanned by the rows of the matrix Since b 1 ∈ L, we can write b 1 = ±[q, p 1 , p 2 , . . . , p n ]M , that is

M =         1 -[Cα 1 ] -[Cα 2 ] • • • -[Cα n ] 0 C 0 • • • 0 0 0 C • • • 0
b 1 = ± [q, Cp 1 -q [Cα 1 ] , Cp 2 -q [Cα 2 ] , • • • , Cp n -q [Cα n ]] , (12)
where q > 0. Hence, the norm of b 1 satisfies

b 1 = q 2 + n i=1 |Cp i -q [Cα i ] | 2 1/2
≤ 2 n/4 C n/(n+1) , which leads to q ≤ 2 n/4 C n/(n+1) and max

i |Cp i -q [Cα i ]| ≤ 2 n/4 C n/(n+1) . (13)
Let us consider the entries qα i -p i . We have

|qα i -p i | = 1 C |Cqα i -Cp i | ≤ 1 C (|Cqα i -q[Cα i ]| + |q[Cα i ] -Cp i |) = 1 C (q|Cα i -[Cα i ]| + |q[Cα i ] -Cp i |) ≤ 1 C 1 2 q + |q[Cα i ] -Cp i | .
Using the two inequalities in (13), we get

|qα i -p i | ≤ 1 C 1 2 • 2 n/4 C n/(n+1) + 2 n/4 C n/(n+1) = 3 • 2 (n-4)/4 C 1/(n+1)
Observe that [START_REF] Sarkar | Cryptanalysis of RSA with two decryption exponents[END_REF] gives

3 n+1 • 2 (n+1)(n-4) 4 • ε -n-1 ≤ C ≤≤ 3 n+1 • 2 (n+1)(n-3) 4 ε -n-1 , (14)
which leads to ε ≥ 3•2 (n-4)/4 C 1/(n+1) . As a consequence, we get |qα i -p i | ≤ ε. On the other hand, using ( 13) and ( 14) , we get q ≤ 2 n/4 C n/(n+1) ≤ 2 n/4 C n/(n+1) ≤ 2 n(n-3)/4 • 3 n • ε -n .

To compute the vector [q, p 1 , p 2 , . . . , p n ], we use [START_REF] May | New RSA Vulnerabilities Using Lattice Reduction Methods[END_REF] [q, p 1 , p 2 , . . . , p n ] = ± [q, Cp 1 -q

[Cα 1 ] , Cp 2 -q [Cα 2 ] , • • • , Cp n -q [Cα n ]] M -1 .
This terminates the proof.

B Proof of Lemma 1

Proof. Suppose that p -q = 2 m u. Then p = q + 2 m u and N = q 2 + 2 m uq. Hence q 2 ≡ N (mod 2 m ). Let u 0 be a solution of the congruence x 2 ≡ N (mod 2 m ). For m ≤ 2, this equation has only one solution and for m ≥ 3, there are four solutions that can be found in polynomial time using Hensel's Lemma. Then q ≡ u 0 (mod 2 m ) for one of the solutions u 0 which implies that q = 2 m q 1 + u 0 for a positive integer q 1 . Now, we have p = q + 2 m u = 2 m q 1 + u 0 + 2 m u = 2 m (q 1 + u) + u 0 = 2 m p 1 + u 0 , where p 1 = q 1 + u. Using N = pq, we get N = (2 m p 1 + u 0 ) (2 m q 1 + u 0 ) = 2 2m p 1 q 1 + 2 m u 0 (p 1 + q 1 ) + u 2 0 .

From this, we deduce 2 m u 0 (p 1 + q 1 ) + u 2 0 ≡ N (mod 2 2m ). Since u 0 is odd, we obtain 2 m (p 1 + q 1 ) ≡ N -u 2 0 u -1 0 (mod 2 2m ), which can be rewritten as 2 m (p 1 + q 1 ) = 2 2m v + t 0 with t 0 ≡ N -u 2 0 u -1 0 (mod 2 2m ).

Finally, we get p + q = 2 m p 1 + u 0 + 2 m q 1 + u 0 = 2 m (p 1 + q 1 ) + 2u 0

= 2 2m v + t 0 + 2u 0 = 2 2m v + v 0 ,
where v 0 = t 0 + 2u 0 . This terminates the proof.

1

 1

Example 1 .

 1 Consider the following 3 RSA moduli and public exponents N 1 = 1339354515091823859151801241, e 1 = 1050185284614316002488409263, N 2 = 5761318740014279657192789531, e 2 = 1492152853356436953159599262 N 3 = 1257936900682879025849691469, e 3 = 103918896908705941667125587. Then N = max(N 1 , N 2 , N 3 ) = 5761318740014279657192789531. Since k = 3, we get δ = k 2(k+1) = 0.375 and ε = √

5. 1 1 -

 11 The attack Theorem 7. Let N = pq be an RSA modulus such that p -q = 2 m u where 2 m ≈ N α . Let e 1 and e 2 be two public exponents satisfying e 1 , e 2 ≈ N γ , e 1 d 1k 1 φ(N ) = 1, and e 2 d 2 -k 2 φ(N ) = 1. Suppose that d 1 , d 2 < N δ and |d 1 -d 2 | < N β . Then one can factor N in polynomial time if 4α)(5 + 4γ -4α -4β).

4 ω.

 4 Using ω = |M | and |M | -|M \S| = |S|, we get

  1)m 4 + o(m 4 ).

Corollary 1 .

 1 Let N = pq be an RSA modulus. Let e 1 and e 2 be two public exponents satisfying e 1 d 1 -k 1 φ(N ) = 1, e 2 d 2 -k 2 φ(N ) = 1. Suppose that d 1 , d 2 ≤ N δ and |d 1 -d 2 | < N β . Then one can factor N in polynomial time if

5 8 - 1 2

 1 β. of Sarkar and Maitra and the bound of Corollary 1 for various values of β = log N (|d 1 -d 2 |).

β

  = log N (|d1 -d2|) β = 0.6 β = 0.5 β = 0.4 β = 0.3 β = 0.25Bound for δ in[START_REF] Sarkar | Cryptanalysis of RSA with two decryption exponents[END_REF] 0.325 0.375 0.425 0.475 0.5 Bound for δ in Corollary 1 0.326 0.379 0.434 0.489 0.517

  ] is the nearest integer to x. The determinant of L is det(L) = C n and the dimension is n + 1. Applying the LLL algorithm, we find a reduced basis(b 1 , • • • , b n+1 ) with b 1 ≤ 2 n/4 det(L) 1/(n+1) = 2 n/4 C n/(n+1) .

C Proof of Lemma 2

Proof. Suppose that S > 2N 1 2 and let D = √ S 2 -4N . We have

Dividing by p -q + D, we get

Combining with p -q + D > p -q, we deduce

Now, set P = 1 2 (S + D). We have

where we used 1 2 • p-q 3(p+q) < 1 2 . This terminates the proof.


Tony Prat

Dominique Delande

Nicolas Cherroret

Quantum boomeranglike effect of wave packets in random media

We unveil an original manifestation of Anderson localization for wave packets launched with a finite average velocity: after an initial ballistic motion, the center of mass of the wave packet experiences a retroreflection and slowly returns to its initial position, an effect that we dub "Quantum Boomerang" and describe numerically and analytically in dimension 1. In dimension 3, we show numerically that the quantum boomerang is a genuine signature of Anderson localization: it exists if and only if the quantum dynamics if localized.

Anderson localization (AL), the absence of wave diffusion due to destructive interference in disordered potentials [1], is ubiquitous in condensed-matter systems, wave physics or atom optics. This offers many experimental platforms for its characterization, as was demonstrated experimentally with light [2,3] (see however [4,5]) or ultrasound waves [6]. Recently, AL of atomic matter waves has also been observed [7][8][9][10][11], as well as its many-body counterpart [12,13]. A precious asset of atom optics experiments is to allow for direct tests of fundamental manifestations of AL, such as the time evolution of wave packets. In this context, a common experimental scenario for probing localization consists in preparing a spatially narrow atomic wave packet in a trap, then opening the trap and monitoring the time evolution of the gas [14,15]. After release, the wave packet spreads symmetrically around its initial position and quickly becomes localized in space. What happens, now, if a nonzero average velocity is additionally imprinted to the gas? In a classical picture, one expects the randomization of velocities due to scattering on the random potential to stop the initial ballistic motion of the wave packet center-ofmass (CoM) at roughly a mean free path , and then a symmetric localization of the packet around this new central position due to AL. We show in this article that the evolution is in fact very different: if the quantum dynamics is Anderson localized, after an initial ballistic motion where the CoM indeed increases up to , the wave packet slowly returns to its initial position, recovering a symmetric shape at long time. In contrast, if the quantum dynamics is diffusive, e.g. in dimension 3 above the mobility edge, the CoM evolves at long time toward a final position different from the initial one.

In this article, we thoroughly study this phenomenon that we dub Quantum Boomerang (QB) effect. In dimension 1, we give an exact solution. In dimension 3, we show numerically that the QB effect exists for strong disorder where the dynamics is Anderson localized, and is partly destroyed for disorder strengths where the long time dynamics is diffusive: the CoM evolves ballistically at short time, makes a U-turn at intermediate time, but does not completely return to its initial position. We further show that it is a faithful signature of AL, allowing to precisely pinpoint the position of the mobility edge.

Let us start with a one-dimensional (1D) system described by the Hamiltonian H = -2 ∆/(2m) + V (x), where V (x) is a Gaussian, uncorrelated random potential: V (x) = 0 and V (x)V (x ) = γδ(x -x ), where the overbar denotes averaging over disorder realizations. We wish to study the time evolution of a normalized Gaussian wave packet, Ψ k0 (x) ∝ exp -x 2 /(2σ 2 ) + ik 0 x , to which a finite momentum k 0 > is imprinted. To simplify the discussion, we assume throughout this article a sharp initial velocity distribution, k 0 σ 1, and weak disorder, k 0 1, thereby allowing for a simple description of the wave packet in terms of two velocity components ± k 0 /m, with energy E 0 = 2 k 2 0 /2m. Its long-time asymptotics, Eq. ( 6), is shown as a solid red curve. The re-summation of the short-time series, Eq. ( 10), (solid green curve) perfectly overlaps with the numerical result (blue dots). The dashed curve is the classical result, Eq.

(1). Inset: center of mass multiplied by (t/τ ) 2 as a function of time. The asymptotic result (6) (red curve) is compared to the numerical prediction, displayed with its statistical error bars. The parameters used are given in the main text.

The average evolution in the random potential is governed by two microscopic scales, the scattering mean free time τ and the scattering mean free path = v 0 τ , where v 0 = k 0 /m. In the following, τ and are calculated to the leading order in 1/k 0 1, using the Born approximation at energy E 0 [START_REF] Akkermans | Mesoscopic physics of electrons and photons[END_REF]. The assumption of uncorrelated random potential is not crucial for our discussion: all the results hold as well for short-range correlated potentials, provided that and τ are replaced by the transport mean free path and time, respectively [START_REF] Gogolin | [END_REF].

By numerically propagating Ψ k0 (x), we obtain the disorder-averaged density profile |Ψ(x, t)| 2 , from which we compute the CoM x(t) ≡ x|Ψ(x, t)| 2 dx. The result is shown in Fig. 1 : x(t) first increases rapidly, reaches a maximum at t ∼ τ and then slowly decreases to zero. In other words, after a transient motion rightward, the wave packet slowly returns to its initial position x = 0. For these simulations we discretize the Hamiltonian on a 1D grid of size 16000π/k 0 , divided into 251352 grid points. The initial wave packet width is set to σ = 10/k 0 , and γ = 0.0058 4 k 3 0 /m 2 (k 0 = 4 k 3 0 /2m 2 γ 86.5). The results are averaged over 45000 disorder realizations. In the simulations, the evolution operator is expanded in a series of Chebyshev polynomials, as explained in [18,19]. The behavior observed in Fig. 1 is dramatically different from the classical expectation, which can be simply deduced from Ehrenfest theorem:

∂ t x class = p /m = k 0 (n + -n -)/m where n ± is the population of particles with momentum ± k 0 (n + +n -= 1). Using the classical Boltzmann equations ∂ t n ± = (n ∓ -n ± )/(2τ ) with the initial condition n + = 0, we find x(t) class = 1 -e -t/τ . (1)
Within the classical picture, the CoM thus quickly saturates to the mean free path , but never experiences retroreflection. The reason why quantum wave packets behave so differently can be understood by the following argument. At any time, the density distribution can be expanded over the eigenbasis

{ n , |φ n } of H as |Ψ(x, t)| 2 = n,m φ n |Ψ k0 Ψ k0 |φ m × φ n (x)φ * m (x)e -i( n -m)t/ . (2)
Since eigenstates are localized, the system is constrained to a volume set by the localization length ξ = 2 . This defines a typical mean level spacing ∆ = 1/ρξ (ρ : density of states per unit volume), with a corresponding localization time τ loc = 2π /∆ = 4τ beyond which the off-diagonal oscillatory terms n = m in Eq. ( 2) vanish, leaving:

|Ψ(x, ∞)| 2 = n | φ n |Ψ k0 | 2 |φ n (x)| 2 . ( 3
)
Due to time-reversal invariance, the φ n (x) are real so that φ n |Ψ k0 = φ n |Ψ -k0 * : Eq. ( 3) is independent of the sign of k 0 , and thus coincides with the long-time, spatially symmetric density distribution that would have been obtained with an initial wave packet having a symmetric velocity distribution. This shows that the CoM must return to its initial position at long times, as a result of AL. Note that this conclusion is also valid in Let us now be more quantitative and analyze the CoM at finite times. For this purpose, we start by applying the Ehrenfest theorem to the mean-square displacement, ∂ t x 2 = x 2 , p 2 /2i m, and split the particle distribution into two classes of positive and negative velocities: |Ψ(x, t)| 2 = n + (x, t)+n -(x, t). This leads to [START_REF]This can be justified more rigorously by using the phase space Wigner representation W (x, p, t) of the wave packet. In the weak-disorder approximation, W (x, p, t) is non vanishing only near p = ± k0, so that[END_REF]

∂ t x 2 = 2v 0 x + -2v 0 x -. (4)
Here x ± = ∞ -∞ x n ± (x, t) dx, with obviously x = x + + x -. We now consider an arbitrary path contributing to x -[Fig. 2(a)]. The path starts at x = 0 with momentum k 0 and reaches x with momentum -k 0 at time t. By time-reversing and translating this path of a distance -x, one can always find a complementary path starting with momentum k 0 at x = 0 and reaching -x at time t [Fig. 2(b)]. Due to time-reversal and translational invariance, these two paths contribute with the same weight to n -(x, t), which is thus an even function of x, yielding x -= 0. This reasoning does not apply to x + since the time-reversed/translated counterpart of an arbitrary path contributing to x + starts with momentum -k 0 which is not initially populated [see Figs. 2(c)-(d)]. We have thus

∂ t x 2 = 2v 0 x , (5)
a property that we can use to infer the long-time limit of

x from x 2 , previously computed in [START_REF] Nakhmedov | [END_REF]. It yields [22] x

(t) = 64ln(t/4τ )τ 2 t 2 + O 1 t 2 . (6)
Eq. ( 6) is shown in Fig. 1 and matches well the exact numerical prediction at long time. The inset of Fig. 1 also confirms the presence of the logarithmic term in Eq. ( 6).

One can go one step further and exploit Eq. ( 5) to compute x(t) at any time. For this purpose, we use the Berezinskii diagrammatic technique [23] which, combined with Eq. ( 5), gives [22]

x(t) = dω 2π e -iωt   - 2 iω ∞ m=0 P 1 m (ω)Q 1 m (ω)   , (7)
where P 1 m (ω) = sΓ(m+1)[Ψ(m+1, 2; -s)-(m+1)Ψ(m+ 2, 2; -s)], with s = 4iωτ , Γ the Gamma function and Ψ the confluent hypergeometric function of the second kind. The Q 1 m (ω) are solutions of

[4iτ (m + 1/2)ω -(m + 1) 2 -m 2 ]Q 1 m (ω) +(m + 1) 2 Q 1 m+1 (ω) + m 2 Q 1 m-1 (ω) + P 1 m (ω) = 0. ( 8
)
At short time, one can solve these equations with the expansion Q 1 m (ω) = +∞ n=0 q m,n /(iω) n . To compute the q m,n , we first notice that q m,i = 0 if i ≤ m, which follows from the large-frequency expansion of P 1 m (ω) (which has no terms 1/ω i with i < m). We use this result to expand Eqs. (8) order by order in 1/ω and reduce them to a triangular system. This method provides us with the coefficients χ n of the expansion x(t) = n χ n (t/τ ) n at arbitrary order.We find for instance

x(t) = t τ - t 2 2τ 2 + t 3 6τ 3 - 3t 4 64τ 4 + O t 5 . (9)
The method cannot be directly used to estimate x(t) at any time because the series has a finite convergence radius, estimated at 4τ from the first 100 terms. Nevertheless, the observed exponential decay of the χ n makes this series a good candidate for a Padé resummation. The knowledge of the long-time limit (6) suggests to express the CoM at any time under the form

x(t) = ln(1 + t/4τ )τ 2 t 2 lim n→∞ R n (t), (10)
where R n (t) is a diagonal Padé approximant of order n, deduced from the χ n coefficients [START_REF] Baker | Essentials of Padé Approximants[END_REF]. In practice, R n (t) converges quickly, and an excellent approximation of x(t) for times up to 120τ is obtained with n = 7. This is demonstrated by the solid green curve in Fig. 1, which perfectly coincides with the numerical results. In order to clarify which specific behavior of the spatial distribution |Ψ(x, t)| 2 actually gives rise to the QB phenomenon, we show in Fig. 3 of the average density profile |Ψ(x, t)| 2 as a function of space and time, indicating on the top the position of the center of mass. Figure 3(b) also shows the x > 0 (blue curve) and x < 0 (red curve) components of |Ψ(x, t)| 2 at three successive times. The profiles display a ballistic peak responsible for the increase of x(t) at short times. After this peak has been attenuated, the profile re-symmetrizes itself around x = 0, which gives rise to the QB effect. As discussed above, at long time the distribution converges toward a symmetric one, Eq. ( 3), the so-called Gogolin density profile [START_REF] Gogolin | [END_REF]25]:

|Ψ(x, ∞)| 2 = ∞ 0 dηπ 2 32 η 1 + η 2 2 sinh(πη)e -(1+η 2 )|x|/8 [1 + cosh(πη)] 2 ,
(11) which is shown in Fig. 3(b) for comparison. Note that although we start from a rather narrow wave packet with σ < in our simulations, the QB phenomenon is present as well when σ > . It is however less dramatic because the forth and back motion of the CoM then has an am-plitude smaller than the wave packet size.

A natural question is whether the QB effect also exists in higher dimension. The Berezinskii technique is specific to 1D systems and cannot be used, but the general spectral argument discussed above -based on Eqs. (2,3)suggests that the QB effect should occur if the eigenstates are Anderson localized. In contrast, if the eigenstates are extended, no minimum energy difference exists for the non-diagonal parts of Eq. ( 2), so that the argument does not apply. This is especially the case in diffusive systems, where quantum interference effects are very small. In order to test this scenario, we have performed numerical experiments using the three-dimensional (3D) Anderson model, that is a 3D cubic lattice with Hamiltonian

H = i i |i i| - <i,j> |i j| ( 12
)
where i, j denote sites of the 3D lattice, i are independent random energies uniformly distributed in [-W/2, W/2] and the second sum involves only neighboring pairs of sites, with the hopping amplitude taken as the energy unit. The phase diagram of this model is well known [START_REF] Kroha | [END_REF]. In particular, states with energy near E = 0 undergo a transition -known as the Anderson transitionbetween extended states at low disorder W and localized states at strong disorder. The "mobility edge" separating the two regimes is given by W c ≈ 16.54 [27].

We first prepare a moving Gaussian wave packet at the center of the system, ψ(r) ∝ exp(-r 2 /2σ 2 + ik 0 .r), with σ = 10 lattice sites and an initial momentum k 0 = (π/2, π/2, π/2) in units of the inverse of the lattice step. We numerically propagate this wave packet in the presence of disorder and monitor the CoM position ψ(t)|r|ψ(t) [28]. The system size is chosen sufficiently large for the wavefunction to be negligibly small at the system edges at the longest times considered, so that the CoM position is computed for a virtually infinite system. ψ(t)|r|ψ(t) is averaged over many (typically few thousands) realizations of the disorder. Because the system is statistically invariant by permutation of the 3 axes of the cubic lattice, the averages x(t) , y(t) , z(t) are equal. In the following, we use x(t) as a shorthand notation for an additional averaging along the 3 directions.

Fig. 4 shows the temporal evolution of x(t) for various disorder strengths W up to t = 1000 (with time in units of the inverse of the hopping amplitude). In all cases, the short time dynamics -not shown in the figure -is ballistic, with x(t) increasing with t, but soon the wave packet performs a U-turn so that x(t) decreases. For W < W c , x(t) tends to a finite non-zero value at long time, indicating a breakdown of the QB effect. In contrast, for W > W c , x(t) tends to zero, a manifestation of the QB. The long-time behavior is approximately ∝ 1/t, that is slower than in 1D, Eq (6). The numerical results are not accurate enough to assess whether there is e.g an additional logarithmic dependence. We performed Here position is in units of the lattice spacing and time in units of the inverse of the hopping matrix element. For W < Wc ≈ 16.5, x(t) saturates to a finite value. In contrast, for W > Wc, a full quantum boomerang effect is clearly visible, with the center of mass returning to its initial position, with an asymptotic behavior ∝ 1/t. For W = Wc (thick cyan line), the critical behavior is such that x(t) ∝ t -1/3 . The dashed lines indicate the asymptotic dependences at long time for the extended, critical and localized regimes. These results show that the quantum boomerang effect is a clear-cut signature of Anderson localization.

similar calculations in dimension 2, where Anderson localization is the generic scenario and observed a similar 1/t asymptotic behavior (data not shown).

At the critical point of the Anderson transition, W = W c , the QB effect is present, albeit with a slower decay, very accurately described by a t -1/3 law. This law is reminiscent of the anomalous diffusion at the critical point with the size of a wave packet increasing like t 1/3 , predicted theoretically [START_REF] Kroha | [END_REF]29,30] and experimentally observed on the atomic kicked rotor [31]. Indeed, by extrapolating Eq. ( 5) to 3D and using x 2 ∝ t 2/3 one readily obtains x ∝ t -1/3 . The same argument explains why x is constant above the critical point, as x 2 ∝ Dt in this regime, with a diffusion coefficient D getting smaller and smaller as one approaches the Anderson transition. These different scaling law can be used to pinpoint precisely the critical point. To this aim, we show in Fig. 5 the quantity x(t) t 1/3 vs. W for increasingly long times. As expected, all curves cross near W = W c . From our numerical data, we observe the crossing of long-time curves at W = 16.55±0.03, in excellent agreement with the most accurate published value W c = 16.543 ± 0.002 [27,32].

To summarize, we have demonstrated that wave packets launched with some initial velocity in disordered systems quantum-mechanically return to their initial position, an effect absent in the classical limit. An exact analytical treatment for 1D weakly disordered systems is in excellent agreement with numerical results. In dimen-FIG. 5. Quantum boomerang effect in the vicinity of the Anderson transition (same units as in Fig. 4). Solid curves show the quantity x(t) t 1/3 versus the disorder strength W, for increasing times, from t = 25, flattest curve in red, to t = 1000, top black curve (times are equally spaced in t 1/3 ). All curves intersect at Wc ≈ 16.55±0.03, making it possible to accurately pinpoint the critical point of the Anderson transition. sion 3, the quantum boomerang effect exists only when the eigenstates are Anderson localized; In the diffusive regime, the center of mass displays only a partial retroreflection and does not end at the initial position. We thus expect the quantum boomerang to be very general for disordered systems displaying Anderson localization. Based on the discussion around Eqs. (2,3), it only requires time-reversal symmetry, statistical invariance by translation and parity of the disorder. Whether it persists when these symmetries are broken or for many-body localized systems will be the subject of further studies. From an experimental point of view, this signature of Anderson localization could be observed in experiments on cold atomic gases, where wave-packet spatial distributions are customarily imaged. In optics, the retroreflection could be probed as well in transversally disordered photorefractive crystals or optical fibers where the coordinate of the optical axis plays the role of time: by illuminating such systems with a spatially narrow beam, one should observe a quantum boomerang of the beam center of mass in the transmitted, near-field intensity distribution [33,34].

FIG. 1 .

 1 FIG. 1. Main plot: center of mass as a function of time.Its long-time asymptotics, Eq. (6), is shown as a solid red curve. The re-summation of the short-time series, Eq. (10), (solid green curve) perfectly overlaps with the numerical result (blue dots). The dashed curve is the classical result, Eq. (1). Inset: center of mass multiplied by (t/τ ) 2 as a function of time. The asymptotic result (6) (red curve) is compared to the numerical prediction, displayed with its statistical error bars. The parameters used are given in the main text.

FIG. 2 .

 2 FIG.2. Scattering paths contributing to the center of mass. a) A typical multiple scattering path going from x = 0 to x, contributing to x -(the path is unfolded to the top for clarity). The momentum reverses at each scattering event. By time-reversing and translating this path by -x, we obtain path b), which gives an opposite contribution to x -, ensuring that x -vanishes. c) Path contributing to x + . Its time-reversed and translated counterpart d) starts with momentum -k0, not populated at t = 0, so that x + = 0.

  (a) a numerical density plot

FIG. 3 .

 3 FIG. 3. (a) Numerical density plot of the average density profile as a function of space and time, showing localization at long time. The dashed black curve is the position of the center of mass x(t) which first increases and eventually comes back to its initial value. (b) Average density profile at three successive times. The solid upper blue and lower red curves are the x > 0 and x < 0 components of the profile, respectively. The long-time limit of the profile, Eq. (11), is shown as a dashed black curve.

FIG. 4 .

 4 FIG.4. Average center of mass versus time in three dimensions. Data are for the 3D Anderson model, at various values of disorder W, from 10 to 24 (with step 1). Here position is in units of the lattice spacing and time in units of the inverse of the hopping matrix element. For W < Wc ≈ 16.5, x(t) saturates to a finite value. In contrast, for W > Wc, a full quantum boomerang effect is clearly visible, with the center of mass returning to its initial position, with an asymptotic behavior ∝ 1/t. For W = Wc (thick cyan line), the critical behavior is such that x(t) ∝ t -1/3 . The dashed lines indicate the asymptotic dependences at long time for the extended, critical and localized regimes. These results show that the quantum boomerang effect is a clear-cut signature of Anderson localization.

We thank Christian Miniatura and Kean-Loon Lee for discussions at the early stages of this work, and Bogdan Damski for suggesting the name "quantum boomerang".