Is there a security problem with this prime generation algorithm?
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.