$p \equiv 3 \pmod 4$ means that $p = 4 k + 3$ for some $k$, or in other words that the remainder when you divide $p$ by $4$ is $3$.

Note that if you take an odd number and divide it by 4, you'll either get 1 or 3 as a remainder, because if you got 0 or 2 as a remainder then the original number would have had to have been even.

So every odd number (and hence every prime other than 2) satisfies either $p \equiv 1 \pmod{4}$ or $p \equiv 3 \pmod{4}$.

There is no dearth of primes congruent to 3 (mod 4), so there is no shortage of ways to find them. You can use pretty much any technique you'd use to generate primes and then just check the the resulting prime is congruent to 3 (mod 4).

In fact, $2^{16}$ is a small enough number that you can simply calculate every prime with 16 or fewer bits by brute force and then throw out all the ones that are congruent to 1 (mod 4), with the whole process finishing in a fraction of a second.