Since $r$ is represented with 100 bits, any candidate $p$ that the eavedropper might use to try to divide $r$ uses also at most $100$ bits. Thus, this very naive algorithm requires $2^{100}$ divisions, which would take about $2^{80}$ seconds, or at least $2^{55}$ years. Even if the eavesdropper uses the fact that a candidate $p$ need not ever be more than $50$ bits, the problem is still difficult. For in this case, $2^{50}$ divisions would take about $2^{30}$ seconds, or about 34 years. \par Since each division takes time $O(n)$ and there are $2^{4n}$ total divisions, the asymptotic running time is $O(n \cdot 2^{4n})$.