Return to Answer

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 \cdot \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 equation

$$(X + p)^2 - 2^{2n}q = X^2 + 2pX + (p^2 - 2^{2n}q) = 0.$$

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.

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 \cdot \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 equation

$$(X + p)^2 - 2^{2n}q = X^2 + 2pX + (p^2 - 2^{2n}q) = 0.$$

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.

I'll end with the canonical (and very flashy but perhaps slightly unfair!) quote from von Neumann, found in his paper Various techniques used in connection with random digits:

Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin. For, as has been pointed out several times, there is no such thing as a random number --- there are only methods to produce random numbers, and a strict arithmetic procedure of course is not such a method.

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 equation

$$(X + p)^2 - 2^{2n}q = X^2 + 2pX + (p^2 - 2^{2n}q) = 0.$$

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.

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 \cdot \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 equation

$$(X + p)^2 - 2^{2n}q = X^2 + 2pX + (p^2 - 2^{2n}q) = 0.$$

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.

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.

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 equation

$$(X + p)^2 - 2^{2n}q = X^2 + 2pX + (p^2 - 2^{2n}q) = 0.$$

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.