Some Results on Pseudosquares

If $p$ is an odd prime, the pseudosquare $L_p$ is defined to be the least positive nonsquare integer such that $L_p\equiv1\pmod{8}$ and the Legendre symbol $(L_p/q)=1$ for all odd primes $q\le p$. In this paper we first discuss the connection between pseudosquares and primality testing. We then describe a new numerical sieving device which was used to extend the table of known pseudosquares up to $L_{271}$. We also present several numerical results concerning the growth rate of the pseudosquares, results which so far confirm that $L_p> e^{\sqrt{p/2}}$, an inequality that must hold under the extended Riemann Hypothesis.