I am quite adept at doing arithmetic mentally or on paper, but I know little about the relatively sophisticated stuff that software experts use to crunch numbers. My question is whether the following idea is frequently used by such experts.

Say I'm trying to find the prime factorization of some immense number $N$, and I find that it's divisible by a bunch of small primes, e.g. $$ N = 2\cdot2\cdot2\cdot2\cdot3\cdot 7 \cdot19\cdot53\cdot79\cdots\cdots\cdots. $$ I've still got a long way to go to get anywhere near $\sqrt{N}$, but then I notice that the quotient of $N$ by the product of the prime factors I've found so far has a square root just smaller than the biggest prime I've found so far. So I draw this conclusion: That quotient is prime.

Might this method of establishing primality be used in actual software?

  • $\begingroup$ You already know that N is not 2 but is divisible by 2, so N is not prime! But yes - if you have determined that (say) 5 does not divide N, then of course it won't divide any quotient of N. This is certainly well known and frequently used whenever it's required, but I would guess that breaking numbers into lots of primes isn't something that's often required. $\endgroup$ – Billy Jun 24 '13 at 18:28
  • $\begingroup$ @Billy : What exactly is the relevance of the conclusion of your first sentence, that $N$ is not prime? That hardly seems worth saying. $\endgroup$ – Michael Hardy Jun 24 '13 at 18:31
  • $\begingroup$ Your question was "Might this method of establishing primality be used in actual software?". My answer: you have already established the non-primality of N. I answered the obvious question with an obvious answer, and then followed up with your other question (which is the question I think you intended to ask). $\endgroup$ – Billy Jun 24 '13 at 18:37
  • $\begingroup$ @Billy : I don't see that you've answered the question I intended to ask. The question of whether $N$ is prime is not even hinted at in my posting as far as I can see. $\endgroup$ – Michael Hardy Jun 24 '13 at 20:07
  • $\begingroup$ What else did you mean by "establishing primality", then? More to the point, what did you intend to ask? $\endgroup$ – Billy Jun 24 '13 at 21:13

All general-purpose factorization software does trial division by a (usually) very large list of small primes before switching to the heavy machinery.

[I say "general-purpose" factorization because there are special-purpose algorithms for cases where the target number is a semi-prime and very large. See Number Field Sieve, for example.]

In the case you cite above, your trick is correct (of course) but I have never seen it used. Instead what normally would happen is this: all small factors are divided out, as you indicated, and then the remaining number is submitted to a primality test. The primality test can be slow if the remaining quotient $Q$ is large, but in your case it's not: you suppose that $\sqrt{Q}$ is slightly smaller than the largest prime in your list. In practice, the largest prime in the "small primes list" will be around, say, $2^{30}$. This means $q \approx 2^{60}$ and a primality test (which is $O(n^3)$ for an $n$-bit number) will be very fast. Your trick requires only a square-root (or even trickier: square the largest prime in your list and compare, which requires one multiplication), which is definitely faster but we're talking about milliseconds here.

Note: There is no denying that by-hand your idea is a very worthwhile step to take.


If you are using trial division from a list of primes, you can certainly do that. Assume I have a list of primes less than $1,000,000$. Each time I find a factor, I divide it out of $N$ as many times as possible. In your example, you would be down to $N/26729808$. If this were less than $79^2$ you could conclude it is prime. If I keep going through my list and get to the end, if the remaining number is less than $10^{12}$ it is prime.

  • $\begingroup$ Ross, I don't get your answer. You seem to be reiterating his idea rather than answering his question regarding the use of this technique in actual software. $\endgroup$ – Fixee Jun 24 '13 at 19:00
  • $\begingroup$ @Fixee: Yes I am confirming that it works. $\endgroup$ – Ross Millikan Jun 24 '13 at 19:34
  • $\begingroup$ +1 However, I am somewhat concerned with the question of whether occasions to use this method arise in practice, so the answer is not complete. $\endgroup$ – Michael Hardy Jun 24 '13 at 21:12

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.