Question

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?

Answer 1

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

See http://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.

Answer 2

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$.

Answer 3

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.