Proving a least prime factor 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?
 A: 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.
A: Your problem is the following:
P1: Given $n$ and a prime $p$ such that $p$ divides $n$, does $n$ have a prime factor less than $p$?
However, the condition that $p$ divides $n$ can be removed; that is, your problem is equivalent to:
P2: Given $n$ and a prime $p$, does $n$ have a prime factor less than $p$?
(To solve P2 given an algorithm that solves P1, just apply P1 to the number $n\cdot p$.)
Problem P2 appears very close to the factoring problem: Given $n$ and any number $k$, does $n$ have a prime factor less than $k$? I don't see any reason why restricting $k$ to be prime should make things any easier.
So it would seem highly unlikely that there is a method that improves on testing whether $p/n$ has a prime factor less than $p$.
A: It sounds like $p$ is small compared to $n$. In this case there are a certain number of ECM curves known to find all factors below a certain bound. I don't remember the references off the top of my head.
A: Another approach, mentioned by Booker, Hiary, & Keating [1], is to use Pollard's $p-1$ algorithm (presumably with a very large B2). They used GMP-ECM.
[1] Andrew R. Booker, Ghaith A. Hiary, Jon P. Keating, Detecting squarefree numbers, Duke Math. J. 164, no. 2 (2015), 235-275.
