How to find prime factors of big numbers made up of big prime factors?

Question

How do I quickly find the prime factors of big numbers with difficult factors? What I mean by difficult factors is that the usual factors like $2,3,5,7,11$ may not be present. For eg: the prime factors of $4181$ are $37$ and $113$.

How do I find them quickly?

Answer 1

There are many ways to factor numbers. One approach I like is the Lehmer sieve which is a mechanical device that tries to find a pair of numbers $x,y$ such that $n=x^2-y^2$, hence $n=(x-y)(x+y)$ gives a factorization.

A naive version is looking for an $x$ such that $x^2-n$ is a perfect square. We get a lower bound $x\geq \sqrt{4181}>64$. For $x=65,66,\ldots$, we see if $\sqrt{x^2-n}$ is an integer, and $x=75$ is the first (after some effort). $\sqrt{75^2-4181}=38$, so we get factors $4181=37\cdot 113$, which we would need to verify are prime.

We can speed this calculation up by seeing when $x^2-n$ is a quadratic nonresidue modulo various primes. For example, $x^2-4181$ is a square modulo $3$ exactly when $x$ is a multiple of $3$, and it is a square modulo $5$ exactly when $x\equiv 0,\pm 1\pmod{5}$. Putting these together, $x$ must be $0,6,9\pmod{15}$. Even with these few considerations, the $x$'s we would have tried above would only have been $x=66,69,75$ before finding a partial factorization.

Answer 2

$4181$ is not very big; in the context of prime factorization "big" is something like hundreds of digits, at least when you're doing it with a computer.

As gammatester says in the comments, you only need to do trial division with the primes up to $\sqrt{4181}$. We have $61^2 = 3721$ and $67^2 = 4489$ so this means the primes up to $61$.

Here are two tricks for speeding this up.

1. Instead of directly doing trial division, start by trying to repeatedly write $4181$ as the sum or difference of two integers whose prime factorization you know. If their prime factorizations have no primes in common, it follows that $4181$ cannot be divisible by any of the primes that occur in any of them, which rules out several primes at once; if they do, you've found a prime factor.

2. If you rule out a bunch of small primes using 1) and are stuck testing bigger primes, again, instead of directly doing trial division, repeatedly subtract large multiples of the prime you're testing for divisibility by. This is a lot easier to do in your head because you only have to keep track of one number at a time.

Let me demonstrate:

• $4181 = 4200 - 19$, where $4200$ has prime factors $2, 3, 5, 7$ and $19$ is prime. It follows that $4181$ is not divisible by $2, 3, 5, 7$, or $19$.
• $4181 = 4400 - 219$, where $4400$ has prime factors $2, 5, 11$ and $219$ has prime factors $3, 73$. It follows that $4181$ is not divisible by $11$ or $73$.
• $4181 = 3900 + 260 + 21 = 13(320) + 21$, where $13(320)$ has prime factors $2, 5, 13$ and $21$ has prime factors $3, 7$. It follows that $4181$ is not divisible by $13$.
• $4181 = 3400 + 680 + 101 = 17(240) + 101$, where $17(240)$ has prime factors $2, 3, 5, 17$ and $101$ is prime. It follows that $4181$ is not divisible by $17$ or $101$.
• $4181 = 3800 + 380 + 1 = 19(220) + 1$, where $19(220)$ has prime factors $2, 5, 11, 19$. It follows that $4181$ is not divisible by $19$.
• $4181 = 4600 - 460 + 41 = 23(180) + 41$, where $23(180)$ has prime factors $2, 3, 5, 23$ and $41$ is prime. It follows that $4181$ is not divisible by $23$ or $41$.
• $4181 = 2900 + 1160 + 121 = 29(140) + 121$, where $29(140)$ has prime factors $2, 5, 7, 29$ and $121 = 11^2$. It follows that $4181$ is not divisible by $29$.

At this point we'll switch entirely to trick $2$; probably we should've done this earlier.

• $4181 = 3100 + 930 + 155 - 4$. It follows that $4181$ is not divisible by $31$.
• $4181 = 3700 + 370 + 111 = 37(113)$. We've finally found a prime factor!

Answer 3

Pollard's method works well for not too large numbers and it's a simple algorithm that doesn't require a lot of work to implement. You just need a calculator and do some arithmetic with it. This method is based on Fermat's little theorem, which states that:

$$a^{p-1} = 1\bmod p\tag{1}$$

where $a\neq 0 \bmod p$, and $p$ is prime number. We can then attempt to use Eq. (1) to find a prime factor $p$ of a composite number $N$, by computing powers of a number (commonly taken to be $2$) modulo $N$ and raise the output again to another power and iterate that process. The idea is then that computing modulo $N$ is consistent with computing modulo $p$ and at some point the outputs will get stuck at $1 \bmod p$. If that's the case then the output minus $1$ will be zero modulo $p$, which means that the output minus $1$ that we get will be some multiple of $p$. We can then take the GCD of the output minus $1$ and $N$ to find $p$.

Now, for the power to get stuck at $1$ means that the power needs to include some of the divisors of $p-1$ (note that while the $p-1$th power of $a$ equals $1$ modulo $p$, the least power that will yield $1$ can be any divisor of $p-1$). This means that we should start by raising $2$ to the power of powers of small primes that are likely present in the prime factorization of $p-1$.

In some cases you'll find that the power you've computed modulo $N$ itself becomes $1$, and that then allows you to extract $p$ via the exponent of $2$.

For $N = 4181$, let's start with:

$$2^{2^2}\bmod N = 16$$

This covers a factor of $4$ in $p-1$. Let's now deal with a factors of $3$, two of such factors should be good enough. The numbers have to remain exact integers when doing the computations, so we need to do this in steps. We have:

$$16^3\bmod N = -85$$

and

$$(-85)^3\bmod N = 482$$

Let's now cover a factor of $5$ in $p-1$:

$$482^5\bmod N =482^4\times 482$$

$$482^2\bmod N =2369$$

$$482^4\bmod N = 2369^2\bmod N = 1259$$

$$482^5\bmod N = 1259\times 482\bmod N= 593$$

Let's now do a test with this number. We then need to compute the GCD of $N$ with $592$ using Euclid's algorithm. This algorithm works by exploiting the fact that the GCD of two numbers doesn't change if we add a multiple of one number to the other number. This means that we can repeatedly reduce one number modulo the other number. This process will end when the smallest number becomes $0$, the GCD is given by the other number. Applying the algorithm yields:

$$\gcd(4181,592) = \gcd(592, 37) = \gcd(37,0) = 37$$

So, $37$ is a prime factor. We see that we didn't need to compute the fifth power as $5$ is not a factor of $36$, but since the output gets stuck at $1$ modulo $p$ there is no harm in going further than you need to go.