How can FactorInteger be so slow if PrimeQ is fast?

Question

My 8th grade son had a homework problem to find a prime factor of $99!-1$. I thought to be clever/lazy and used FactorInteger[99!-1], but it takes forever. PrimeQ[99!-1] very quickly gives False. It turns out Mathematica finds $101$ and $331$ quickly by FactorInteger[99!-1,3] but chokes on the 3rd long factor which still quickly gives a False with PrimeQ. What am I missing and how could my son be expected to find a prime factor? Any tricks?

Answer 1

PrimeQ and FactorInteger use different algorithms. In general asking whether a number is prime is an easier problem than finding its factors.

To quote the documentation, "PrimeQ first tests for divisibility using small primes, then uses the Miller–Rabin strong pseudoprime test base 2 and base 3, and then uses a Lucas test", while "FactorInteger switches between trial division, Pollard , Pollard rho, elliptic curve, and quadratic sieve algorithms."

Mathematica doesn't find any small prime factors in 99!-1 so PrimeQ is applying the Miller-Rabin primality test which will be faster than the factorising algorithms used by FactorInteger.

References:

http://reference.wolfram.com/language/tutorial/SomeNotesOnInternalImplementation.html#6849 http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

Answer 2

I want to answer the part of the question, "How could my son be expected to find a prime factor?"

Well, this depends on what your son has been taught, of course. A first thing to notice is that, since 99! is divisible by every prime less than 99, 99! - 1 is not divisible by any of those primes; so 101 is the smallest prime which could be a factor of it. So one can test if 101 is a factor.

In fact, for any prime $p$, $(p-2)! - 1$ is divisible by $p$. This is a consequence of Wilson's Theorem, which says that a number $p > 1$ is prime if and only if $(p-1)! \equiv p-1 \pmod p$. In other words, $$ \begin{align} (p-1)! - (p-1) \equiv 0 \pmod p \\ (p-1) \bigl((p-2)! - 1\bigr) \equiv 0 \pmod p \end{align} $$ so $p \mid (p-2)! - 1$.

I don't know if your son has been told Wilson's Theorem, or is just supposed to figure out that 101 is the smallest possibility and test it with a computer, or use some other technique he's been taught.

As for the question of speed: factoring large integers is a famously hard problem for which no polynomial-time algorithm is known, and everyone would be extremely surprised if such an algorithm were found. For one thing, all modern cryptographic security is based on this problem being hard, and if anyone found a fast solution, encryption would suddenly be worthless; online commerce would screech to a halt; everyone's emails would get leaked; the world would be thrown into chaos.

On the other hand, there are lots of fast probabilistic algorithms to find if a number is "almost certainly" prime very quickly. It can even be determined for certain in polynomial time: the paper proving this is "PRIMES is in P" by Agrawal, Kayal, and Saxena (2004).

Answer 3

In a nutshell, factoring integers is a harder problem than determining primality. This seeming asymmetry is exploited as a component in modern computer security systems (in the form of the RSA cryptosystem).

Determining primality has long been known to be doable in polynomial time using a variety of probabilistic algorithms, many of which (as mentioned by sn6uv) are implemented in Mathematica. Recently, it was also proven that determining primality is in fact solvable in polynomial time without requiring any randomness^[1]. This means that there exist, essentially, algorithms that can determine primality very fast, and which don't slow down too much as the numbers get bigger.

Factoring, on the other hand, is widely suspected (but not proven) to be unsolvable in polynomial time. In other words, no polynomial-time algorithm exists; all known algorithms take exponential or sub-exponential time. This means that these algorithms get very slow as the size of the prime factors increase.

This fact is exploited in the popular RSA cryptosystem, in which two large prime numbers (which can be tested for primality quickly) are multiplied together to give a "public key", which can be used by anyone to produce encrypted messages. The prime factorization forms the "private key", and is needed to decrypt these messages. If factoring were easy, such cryptosystems would not be secure.

---

The chief confusion here seems to be that you think the problem of determining compositeness necessarily implies finding a prime factor. This is perfectly understandable: after all, how do you know a number is composite, if you don't know any of its factors?

The answer is simply that primes have a set of properties quite distinct from that of composite numbers. All primality tests basically do is check these properties, and if enough properties hold, then we can conclude the number is prime. The math needed to prove these tests actually work is beyond the scope of this answer, but in essence, they non-constructively show that a number cannot be prime, without necessarily revealing their factors.

Answer 4

Some factors are: 101 * 331 * 8219124367748699129845858634653 * 4119842702492043412032706962320115960832703 * 824419205282115273977518371114490551823268642298276528536865748592310195781331.