Lattice based attack on RSA Let $n=pq$ be the RSA module and at least one of $p,q$ is a weak prime.It is proved that  the number of such $1024$bit $n$ is at least $2^{759}$. With lattices we can factor these $n$ in a second (I implemented it). Are you know the methods that  are more powerful than this method?
This is not quite an answer, because what I'll discuss is only about as powerful as the attack in the question, which refers to section 3 onwards in: Abderrahmane Nitaj and Tajjeeddine Rachidi, Factoring RSA moduli with weak prime factors (preliminary 2015-05 eprint).

The method I'll discuss is acknowledged in section 2.3 of the above article. It was exposed in the seminal: Don Coppersmith, Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known, in proceedings of Eurocrypt 1996; and in section 11 of his Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities in Journal or Cryptology, 1997 (paywalled; or try blind Googling).

The idea is to consider RSA moduli $N=pq$, with $N$ of $n$ bits, $p$ and $q$ prime, perhaps $q&lt;p&lt;2q$; and within that consider the moduli with a "weak prime factor" $p$ having the top $n/4$ bits matching some known arbitrary value (that also works with the low bits). Using a lattice attack (that is, based on the Lenstra-Lenstra-Lovász lattice basis reduction algorithm), $N$ is factored in polynomial time, and efficiently so for common RSA key sizes.

A preliminary version of Nitaj and Rachidi article stated (page 9 below table 2) that for  $N=pq\in[2^{1024},2^{1026}]$, the $\ge2^{759}$ moduli that their new method can factor


  is much larger than the number of RSA moduli with a weak Coppersmith
  prime factor in the same interval, which is actually $N^{0.25}\approx2^{256}$.


Fact is, the authors had grossly miscounted; their exponent $256$ in this quote is too small by a factor of nearly $3$. We get $&gt;768$ is we assume all integers are prime (which in the circumstance is a fine approximation); or $&gt;751$ if we consider that among 513-bit integers, one in about $2^{8.5}$ is prime. So the new method is at best claimed to improve Coppersmith's by a mere $8$ bits. Further, the set of weak Coppersmith prime factors can be trivially extended by a factor of $2^k$ by varying the low $k$ bits of the known arbitrary value.

As noted by poncho, neither method is likely to succeed for randomly seeded $p$ and $q$, for there are $&gt;2^{1008}$ RSA moduli in the interval considered, and odds that a weak one is selected by chance are entirely negligible (in the order of $2^{-248}$).



What's notable with Nitaj and Rachidi's method is that it extends Coppersmith's attack to a more flexible set (not a much wider set) of RSA moduli; and has found applications in factoring more moduli actually deployed (that have been poorly generated) than in:  Daniel J. Bernstein, Yun-An Chang, Chen-Mou Cheng, Li-Ping Chou, Nadia Heninger, Tanja Lange: Factoring RSA keys from certified smart cards:
Coppersmith in the wild aka smartfacts, initially in proceedings of Asiacrypt 2013.



Update: the issue pointed above was promptly corrected in a revised version: Abderrahmane Nitaj and Tajjeeddine Rachidi, Factoring RSA moduli with weak prime factors (2015-12-31).