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.