I am facing the following algorithm to generate an RSA public key:
e = 0x10001 def generate_p(): r := random odd 128-bit number p := (3*r^4 + 1)/4 if is_prime(p) and gcd(p-1, e) = 1: return p else: return generate_p() def generate_q(): r := random odd 128-bit number q := (11*r^4 + 1)/4 if is_prime(q) and gcd(q-1, e) = 1: return q else: return generate_q() p = generate_p() q = generate_q() N = p*q d = modinv(e, (p-1)*(q-1))
So essentially $s$ and $t$ are random 128-bit integers, $4p = 3s^4 + 1$ and $4q = 11t^4 + 1$ with $p$ and $q$ prime. Does the way $p$ and $q$ are generated give us information that helps factor $N$ (which is 1024 bits in size)?
I considered Coppersmith's attack to compute $s$ and $t$ as small roots mod p/q, but they are not small enough for the algorithm to be applicable.