Is there a better way to factor $375007$ with out testing first $612$ primes ?

I know this factors to $31\times 12097$ by testing the primes $2,3,5,\ldots,31$. Is there any other clever way to work this ? I have tried Fermat's factorization by writing the number as $x^2-y^2$ but it is also taking too many iterations because the factors differ by large magnitude.

Also I have been trying to factor it by changing the base to 10^2 : $37x^2 + 50x+7 = (ax+b)(cx+d)$ and other bases but no success yet.

  • $\begingroup$ because it is a dumb method - I wouldn't know in advance how small/large the least prime factor of a given number can be. I am looking for alternate ways to factor numbers whose factors differ by large magnitudes $\endgroup$ – pooja Jan 6 '15 at 4:35
  • $\begingroup$ Not dumb, but heuristic. A dumb method wouldn't really lead you to any sort of solution. $\endgroup$ – daOnlyBG Jan 6 '15 at 4:40
  • 4
    $\begingroup$ There are a lot of ways. See Wikipedia's article on integer factorization, which has a list of methods. The Pollard rho algorithm is a good method of intermediate complexity that is not too hard to implement. $\endgroup$ – MJD Jan 6 '15 at 4:41
  • $\begingroup$ Well that method works always. My question was if we can do better than that and yes I am also going through wiki and getting myself confused $\endgroup$ – pooja Jan 6 '15 at 4:46
  • 1
    $\begingroup$ @MJD The other nice thing about Pollard rho is that it runs (on average) faster if the least prime factor is small. In effect it beats trial division except in small cases where both run extremely quickly regardless. $\endgroup$ – Erick Wong Jan 6 '15 at 4:51

The last prime I need to know to factorize that number is $113$, the $30$th prime number. This is because $\sqrt{12097}\approx110$. After $110$, I know that any higher value to divide $12097$ would force its counterpart to be smaller: $\frac{12097}{113}\approx107$. Thus, if a number higher than $110$, like $113$, divided $12097$, I would have already found its counterpart. Once I hit $113$, I know that $12097$ is prime, because I've crossed the square root barrier.

  • 1
    $\begingroup$ This is, of course, only using the naive trial division method. Both this and, if I understand correctly, Pollard rho, will not do nearly as well with $617\times619=381923$; in this case, trial division will take 113 primes (this by the way is coincidence, don't take it as meaning anything) to get anywhere. $\endgroup$ – Dan Uznanski Jan 6 '15 at 5:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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