Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.