In the ROCA paper the authors define an integer $M$ (which they call a primorial) as follows:

$$M = \prod_{i=1}^{n} P_i = 2 * 3 * ... * P_n$$

Said another way, $M$ is the product of the first $n$ primes. What the authors observed is that the factors of a vulnerable RSA modulus $N$ have the following form:

$$p = k*M + (65537^a \text{ mod } M)$$

The $65537 (= \mathtt{0x10001})$ might look a little odd hardcoded, but it's a common choice for the public exponent of an RSA key as it has a low hamming weight and thus allows some speed gains in common public key operations.

In the case you are interested in, where $|N| = 512$ bits, we have $n = 39$ and thus $|M| = 219$ bits. Since the size of the prime factors of $N$ is $\frac{|N|}{2} = 256$ bits this implies:

$$|k| = \frac{|N|}{2} - |M| = 256 - 219 = 37$$ $$|a| = \mathbb{log}_{2}(\mathbb{order}_M(65537)) = 62$$

So to generate a vulnerable $512$ bit RSA public key do the following:

1. Randomly sample a $62$ bit value $a'$ and a $37$ bit value $k'$.
2. Compute $p' = k'*M + (65537^{a'} \text{ mod } M)$.
3. Check that $p'$ is prime, if yes it is one of your factors $p$, if not go back to step 1.
4. Sample another prime $q$ using steps 1-3.

Your vulnerable RSA public key $(N, e) = (p*q, 65537)$.

On to the attack. If $M$ is known, our prime factor $p$ now only has $|k| + |a| = 37 + 62 = 99$ bits of entropy rather than the $256$ bits of entropy that it should. This is not good. The "naive" ROCA attack works in the following way:

1. Select a guess for the value of $a$ and compute $65537^{a} \text{ mod } M$.
2. Given $65537^{a} \text{ mod } M$ and the relationship $p = k*M + (65537^a \text{ mod } M)$ use Coppersmith's Algorithm to recover $k$.
3. Compute $p$ using the recovered $k$ and check if $N \text{ mod } p = 0$. If so, $p$ is a factor of $N$. If not,go back to step 1. and select the next guess for $a$.

The time complexity for this attack is $\mathcal{O}(2^{|a|}) = \mathcal{O}(2^{62})$ since in the worst case we have to check every possible value of $a$. Note that the search space of $a$ is the size of the group that $65537$ generates $\text{ mod } M$.

Now I said "naive" ROCA attack above because the authors optimize this attack by finding a value $M'$ such that the following relationship still holds:

$$p = k*M' + (65537^a \text{ mod } M')$$

But they find $M'$ in such a way that the size of the group $65537$ generates $\text{ mod } M'$ is much smaller than $\text{ mod }M$. Thus the search space for $a$ is also much smaller, and ends up bringing the time complexity down to $\mathcal{O}(2^{20})$. The actually process for finding $M'$ is rather involved, if you'd like to know the details I'd suggest diving into the paper.

In the ROCA paper the authors define an integer $M$ (which they call a primorial) as follows:

$$M = \prod_{i=1}^{n} P_i = 2 * 3 * ... * P_n$$

Said another way, $M$ is the product of the first $n$ primes. What the authors observed is that the factors of a vulnerable RSA modulus $N$ have the following form:

$$p = k*M + (65537^a \text{ mod } M)$$

The $65537 (= \mathtt{0x10001})$ might look a little odd hardcoded, but it's a common choice for the public exponent of an RSA key as it has a low hamming weight and thus allows some speed gains in common public key operations.

In the case you are interested in, where $|N| = 512$ bits, we have $n = 39$ and thus $|M| = 219$ bits. Since the size of the prime factors of $N$ is $\frac{|N|}{2} = 256$ bits this implies:

$$|k| = \frac{|N|}{2} - |M| = 256 - 219 = 37$$ $$|a| = \mathbb{log}_{2}(\mathbb{order}_M(65537)) = 62$$

So to generate a vulnerable $512$ bit RSA public key do the following:

1. Randomly sample a $62$ bit value $a'$ and a $37$ bit value $k'$.
2. Compute $p' = k'*M + (65537^{a'} \text{ mod } M)$.
3. Check that $p'$ is prime, if yes it is one of your factors $p$, if not go back to step 1.
4. Sample another prime $q$ using steps 1-3.

Your vulnerable RSA public key $(N, e) = (p*q, 65537)$.

On to the attack. If $M$ is known, our prime factor $p$ now only has $|k| + |a| = 37 + 62 = 99$ bits of entropy rather than the $256$ bits of entropy that it should. This is not good. The "naive" ROCA attack works in the following way:

1. Select a guess for the value of $a$ and compute $65537^{a} \text{ mod } M$.
2. Given $65537^{a} \text{ mod } M$ and the relationship $p = k*M + (65537^a \text{ mod } M)$ use Coppersmith's Algorithm to recover $k$.
3. Compute $p$ using the recovered $k$ and check if $N \text{ mod } p = 0$. If so, $p$ is a factor of $N$. If not,go back to step 1. and select the next guess for $a$.

The time complexity for this attack is $\mathcal{O}(2^{|a|}) = \mathcal{O}(2^{62})$ since in the worst case we have to check every possible value of $a$. Note that the search space of $a$ is the size of the group that $65537$ generates $\text{ mod } M$.

Now I said "naive" ROCA attack above because the authors optimize this attack by finding a value $M'$ such that the following relationship still holds:

$$p = k*M' + (65537^a \text{ mod } M')$$

But they find $M'$ in such a way that the size of the group $65537$ generates $\text{ mod } M'$ is much smaller than $\text{ mod }M$. Thus the search space for $a$ is also much smaller, and ends up bringing the time complexity down to $\mathcal{O}(2^{20})$. The actual process for finding $M'$ is rather involved, if you'd like to know the details I'd suggest diving into the paper.