I am trying to understand how Euler's primality test works. I use this paper as a guide. To summarize Euler's criterion
Euler's criterion(in my uderstanding). For an integer $a$, and an odd prime $p$ where $1<a<p$ if $$a^{(p-1)/2} \bmod{p}$$ evaluates to either $1$ 0r $(-1)$ then $p$ is probably prime.
Am I understanding it correctly?
My second question is about the choice for $a$. In order to use the test properly do I check the Euler's criterion using every integer up to $p$?
I am trying to write code that will test for primality using the Euler's test. Also, if you know any good papers that explain Euler's test please let me know. Thanks.
Euler's criterion says that if $p$ is a prime, then $a^{(p-1)/2} \equiv [\frac ap] \pmod p$, where $[\frac ap]$ is the Jacobi symbol. It's also known that if $p$ is composite, then there exists an $a$ such that $a^{(p-1)/2} \not\equiv [\frac ap] \pmod p$.
So you would probably be implementing two computations: the calculation of $a^{(p-1)/2} \pmod p$, and the calculation of $[\frac ap]$ (using quadratic reciprocity). You would have to test more than one $a$, because composite numbers can sometimes accidentally satisfy Euler's criterion for some (but not all) $a$.