Let $p < 2^{1000}$ and $q=3 \cdot 2^n - 1$ for $500 < n < 1000$ be primes and set $n=pq$ to be the modulus of the RSA cryptosystem. Find an attack on this system and how many operations that are required to succeed.
My attempt at a solution: Set $m=pq$ and compute $d_n = \gcd(m, 3 \cdot 2^n - 1)$ for $500 < n <1000$ until we find a value $n=k$ such that $d_k>1$, then $q=(3 \cdot 2^k - 1)|m$ and we have cracked the system.
Is this correct? I saw a solution sketch for this using the same method iterating for $1\leq n \leq 1000$. Is it really necessary to test the first 500 values from the way this question is stated?
Your approach is correct; if the set of possible values of $q$ is so much restricted, the easiest solution is to search it exhaustively.
The tricky solution is to check the candidates for $q$ for primality first (this can be done once, even if we're trying to break multiple instances of the cryptosystem with different $p$ and $q$) to discover that the only case when it is prime occurs for $n=827$. Thus, the tricky guy could just plainly say: "$q=3\cdot 2^{827}-1$ and $p=n/q$", without doing any computation at all :-)