My (very limited) understanding of the paper
Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers
is that bit strings of algebraic numbers are not "cryptographically secure". The authors (Kannan, Lenstra and Lovász) write as the first sentence of the abstract:
We show that the binary expansions of algebraic numbers do not form secure pseudorandom sequences
Edit: Here is a bit of their first paragraph:
We show that if a complex number $a$ satisfies an irreducible polynomial $h(X)$ of degree $d$ with integral coefficients in absolute value at most $H$, then given $O(d^2 + d \log H)$ bits of the binary expansion of the real and complex parts of $a$, we can find $h(X)$ in deterministic polynomial time (and then compute in polynomial time any further bits of $a$).
So in your case $a = 2^n \sqrt{q} - p$ solves the polynomial
$(X + p)^2 - 2^{2n}q = X^2 + 2pX + (p^2 - 2^{2n}q)$
This has degree $d = 2$. Both $p$ and $2^{2n}$ have bit-size $O(n)$. If $q$ also has bit-size $O(n)$, and if you provide $O(d^2 + d \log H) = O(4 + 2 n) = O(n)$ bits, then their attack applies.