# Tag Info

For part(a.ii), I am presuming that "enumerating candidate prime factors" means that we have a precomputed list of all 1536-bit primes, which we can simply test one at a time. To determine average running time we can use the prime number theorem, which states that the number of primes less that $N$ is approximately given by $\pi(x) \sim \frac{N}{\ln N}$. ...