Suppose that I find a small prime factor $p$ dividing a large number $n$ and I wish to prove that it is the least prime dividing $n$. There are two obvious approaches: either factor $n/p$, or divide $n/p$ by all the primes below $p$ (ideally with a Bernstein remainder tree).


But sometimes neither approach is practical, say if $p\approx10^{20}$ and $n\approx10^{200}$. Is there a method for determining whether $p$ is the smallest prime factor of $n$ or, equivalently, whether $n/p$ has any prime factors less than $p$, faster than either of the naive methods above?


Of course this is (fairly) easy to determine with high probability: run an appropriate number of ECM curves. But can this be done deterministically?



Proving a least prime factor
The Pollard-Strassen algorithm finds all factors up to a bound $B$ of some integer $m$ in $O(m^{\varepsilon} B^{1/4})$. 


See <https://math.stackexchange.com/questions/185524/pollard-strassen-algorithm> for info and links.


The mentioned deterministic ECM (up to $2^{32}$) is here 


<http://hal.inria.fr/docs/00/41/90/83/PDF/RR-7040.pdf>


ps. Sorry, for the rushed answer.


