What does $p≡3\mod4$ mean, and how do you find a prime matching this pattern?

Question

I am reading How to Generate a Sequence of Unique Random Integers where it says:

---

---

What does that $p≡3\mod4$ mean? How do I find an 8-bit prime, and a 16-bit prime match that $p≡3\mod4$ statement?

Answer 1

$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.