4
$\begingroup$

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?

$\endgroup$

4 Answers 4

5
$\begingroup$

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.

$\endgroup$
0
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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