# Which composites pass this probabilistic primality test?

If a composite integer resembles a prime too closely, it must pass algorithmic tests designed to find primes and in addition avoid nontrivial factorization.

Given an integer $p$, assume it is prime and run some testing algorithms for primality. If $p$ fails verification then declare $p$ composite and stop.

Which composites $p$ pass the following probabilistic primality test?:

1. Pick random integers $a,b$ and count the points modulo $p$ on the elliptic curve $E : y^2=x^3+ax+b$. Let the number of points be $o$. For point counting use Schoof's algorithm.

2. Verify $o$ is a multiple of the order by finding a point $P$ on $E$ and check if $oP=0$. For finding $P$, chose deterministic algorithm for square roots, say the implementation in sagemath 7.0.

3. Pick a random integer $X$ and compute $d=\psi_o(X) \mod p$ where $\psi_n$ is the $n$-th division polynomial. Verify $\gcd(d,p) \mod p \in \{0,1\}$. This step might find a nontrivial factor, since counting points modulo composites is probabilistically equivalent to factoring.

The running time of this algorithm is polynomial in $\log{p}$ if $p$ is prime. I believe explicit bounds for the running time are known for prime $p$.

Similar algorithm is via computing square roots modulo $p$. Square roots modulo composite are probabilistically equivalent to factoring, so just try to factor $p$ with square roots and if you fail to compute the square root of known square then $p$ is composite.

• A websearch will turn up something called "elliptic pseudoprime" but I don't think it's quite what you have here. – Gerry Myerson Oct 2 '17 at 12:07
• I highly doubt that the points on $E$ over $\mathbb{Z}/p\mathbb{Z}$ can be counted in time polynomial in $\log p$ if $p$ is not prime and you do not know the factorization of $p$. In particular, counting points on $y^{2} = x^{3} + 1$ mod $pq$ where $p$ and $q$ are both primes congruent to $2 \pmod{3}$ is equivalent to factoring $pq$. – Jeremy Rouse Oct 2 '17 at 13:10
• @JeremyRouse I meant it is polynomial for prime $p$. If it is not polynomial or the result is wrong then $p$ is composite. – joro Oct 2 '17 at 13:24
• This will be sensitive to exactly how you compute the number of points in step 1 then. – Watson Ladd Oct 2 '17 at 17:06
• If you use Schoof in step 1 and attempt to find the trace of Frobenius in the $\ell$-torsion $E[\ell]$, you need to see if $(x^p,y^p)$ behaves like Frobenius in $E[\ell]$, which amounts to a Frobenius pseudoprime test in the field generated by $E[\ell]$. – Felipe Voloch Oct 2 '17 at 20:15

Schoof's algorithm computes, for each small $\ell$ and a point $(x,y) \in E[\ell]$, the element $a_{\ell} \in \mathbb{Z}/\ell$ such that $(x^{p^2},y^{p^2})+p(x,y) = a_{\ell}(x^p,y^p)$ (in the group law on $E$) and recovers the trace of Frobenius by applying the Chinese remainder theorem to the $a_{\ell}$.
We can try to do that when $p$ is not prime and it may fail in many ways. One way it can fail is that $(x^p,y^p)$ is not in $E[\ell]$ (or even in $E$). We can start by checking this, which is a polynomial time computation in the range of $\ell$ of interest. And, if $p$ is not a prime power, [1] proves that indeed there is an $\ell$ in the range of interest where this failure will happen, showing that $p$ is not prime.