Is there a security problem with this prime generation algorithm? 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.
This is the approach that finally let us factor $N$ for the competition. I believe it completely breaks the given scheme. Let's write down the formula for $N$:

$N = pq = \frac{3s^4+1}{4}\cdot\frac{11t^4+1}{4}$ for some $s, t \in [2^{128}, 2^{129})$

After some rearranging:

$\frac{16}{33}N = (st)^4 + \frac{1}{11}s^4 + \frac{1}{3}t^4 +\frac{1}{33}$

In our case, we had $\frac{1}{11}s^4 + \frac{1}{3}t^4 +\frac{1}{33} &lt; (st)^2$ and thus after we substitute $x := (st)^2$:

$x^2 \le \frac{16}{33}N &lt; x^2 + x = x(x+1) &lt; (x+1)^2$

So we could compute $x = \lfloor\sqrt{\frac{16}{33}N}\rfloor$ and then factor $\sqrt x$ (which has only 256 bits) to get $s$ and $t$. 

I feel like the above inequality holds generally if $s$ and $t$ have somewhat similar value, but I haven't tried to prove this.