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?:

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.

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.

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.

prime$p$. If it is not polynomial or the result is wrong then $p$ is composite. $\endgroup$1more comment