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.