practical arithmetic in prime factorizations

Question

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?

Answer 1

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.

Answer 2

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.