Lattice based attack on RSA
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).