n_is_prime_pseudosquare

n_is_prime_pseudosquare first trial-divides $n$ by up to FLINT_PSEUDOSQUARES_CUTOFF primes; if no factor is found and the square of the last prime does not exceed $n$, let $B_0$ be the next prime. The first pseudosquare $L_p > n/B_0$ is then looked up in a static table (OEIS A002189), and step 3 of the test checks that $p_j^{(n-1)/2} \equiv \pm 1 \pmod n$ for the primes $p_j$ up to $p$. Every prime passes this, and most composites fail. If $n \equiv 3, 7 \pmod 8$, $n$ is then prime. Otherwise step 4 proves primality: for $n \equiv 5 \pmod 8$ by checking $2^{(n-1)/2} \equiv -1 \pmod n$, and for $n \equiv 1 \pmod 8$ by finding some $p_j$ with $p_j^{(n-1)/2} \equiv -1 \pmod n$, trying further primes if necessary. Step 4 cannot fail for prime $n$; if it ever fails, an exception is thrown, since a composite passing step 3 would be of independent interest.