Factoring one of many RSA moduli

Assume we have m RSA moduli nj of b-bit, generated in
such a way that each nj has unknown factorisation into
pj*qj, where pj and qj are random primes with
2^(b/2-1/2) < pj < qj < 2^(b/2) [1]

We may assume 512 <= b <= 2048 and m>1000.

Is there an algorithm that can be expected to factor at
least one of the nj with less work than factoring n0
using GNFS?

How does the expected effort scale with m ?


TIA,

Francois Grieu


Note [1]: Established RSA key generation standard ANSI X9.31
do this, with more criteria on the factors.

[Reposted with typo fixes]
.

Quantcast