Primes $p$ are integers with no factors (composite allowed) in $[1,p]$. There is a polynomial time test for them.


Given an interval $[a,b]$ what is the best way to test given integer $q$ has no composite factor allowed in $[a,b]$? Can any non-trivial primality test be specialized?



Specializing non-trivial primality tests
Checking whether an integer $n$ has a divisor in a given interval is essentially equivalent to factorization. Factoring is essentially equivalent to finding the smallest prime factor. So suppose that $n$ is not prime. Then check whether $n$ has a prime factor in $[1, n^{1/4}]$. Depending on the outcome check whether $n$ has a factor in $[1, n^{1/8}]$ or in $[n^{1/4}, n^{3/8}]$. After $\frac{\log n}{\log 2}$ steps you have determined the smallest prime factor of $n$. So as far as we know, checking for factors in an arbitrary interval is a lot more difficult than checking for factors in $[2, n-1]$.


