## Monday, January 25, 2010

### Project Euler #3: Largest prime factor

First, some clarification: I'm referring to the process of finding a non-trivial factor of a number (not one, and not itself) when I speak of factorization. This is not the same as finding the prime power decomposition of a number.

These algorithms are presented as more fun alternatives for solving project euler problem 3, rather than a bland trial and error approach.

# Fermat's Factorization Method

Fermat's factorization method is quite simple and forms the basis for faster algorithms. It works like this: suppose you have an integer n to be factored, and it can be expressed as the difference of two squares:

$$n = a^2-b^2$$

Then n can easily be factored like so:

$$n = (a+b)(a-b)$$

Luckily enough, all odd integers can be written like this (proof left to the reader). The problem that remains is to find out how to express n as the difference of two squares, and this can be done quite easily. For example, one can start at $$a = \sqrt{n}$$ and incrementing, checking whether or not $$a^2-n$$ is a perfect square.

Unfortunately, this naive process can take longer than trial division, so I would not recommend it (for the interested reader; however, there are many ways to speed up this method).

A more clever method exists if the integer in question has relatively small factors; however, before introducing it, I have to discuss some notation:

# Division

The notation $$a|b$$ means "a divides b". In other words, there exists an integer c such that $$ac=b$$.

# Congruences

The notation $$a \equiv b \pmod{m}$$ means that $$m|a-b$$, or that "m divides the difference of a and b". The notation may be unfamiliar, so a small exercise may help. Take a gander at the following statement:

$$a \equiv r \pmod{m}$$ and $$0 \leq r < m$$ This means that r is the remainder when a is divided by m, which is a more familiar concept.

# Pollard's Rho Method

This approach works well for large odd numbers with small factors. The first step is to generate some random Diophantine polynomial, such as:

$$f(x)=x^2+a$$ where $$a\not=0,-2$$

Now generate a sequence of $${x_k}$$ such that:

$$x_{k+1} \equiv f(x_k) \pmod{m}$$, with $$k \ge 0$$

The goal is to find some small, non-trivial factor $$d$$ of $$n$$. Since there are exactly $$d$$ congruent classes modulo $$d$$, and $$d < n$$, the integers $$x_k$$ must become periodic (modulo $$d$$). That is, there must exist residues $$x_i$$ and $$x_j$$ such that $$x_i \equiv x_j \pmod{d}$$, where $$i < j$$. Therefore, the strategy is to choose $$x_0$$ and $$f$$ such that $$x_i \equiv x_j \pmod{d}$$, but $$x_i \not \equiv x_j \pmod{n}$$. If suitable values can be chosen, note that $$d | x_j - x_i$$ but $$n \not | x_j - x_i$$. This means that $$gcd(x_j - x_i, n)$$ is a non-trivial factor of $$n$$. Pretty clever huh? Notice that knowledge of the value of $$d$$ is not used to compute $$gcd(x_j - x_i, n)$$.

# Conclusion: Trial Division

Despite it all, my preference is for a simple approach: trial division with a pre-generated list of primes. Most Project Euler problems can be solved pretty quickly if you've got a big enough list; the only problem that remains is how to efficiently generate such a list...