# RSALib prime generation - derive number of primes

I'm working on factorizing a ~450 bit key that I know has been generated with RSALib and thus is vulnerable to ROCA. Now reading the original paper, I can see that the primes are generated in the following form:

$$p = k \cdot M + (65537^{\,\large{a}} \bmod M)$$

where $k$ and $a$ are unknown value to us but where $M$ is known and is in fact the product of the first $j$ primes. Now in the original paper I was able to find that we know $j$ for some intervals but I'm not quite sure how to derive it for key length that are below 512 bits. Is there a way to do it?

• I'm a little bit confused, are you asking for the number of primes below a certain number, say the number of primes below 1000? – AleksanderRas Aug 31 '18 at 9:09
• No, basically RSALib has a predefined method for generating primes but I couldn't find any documentation for primes where the keysize is < 512 bits. – S. L. Aug 31 '18 at 16:04