MathJax

Syntax Highlighter CSS (shCore.css)

Syntax Highlighter CSS (shThemeDefault.css)

Syntax Highlighter JS (shCore.js)

Syntax Highlighter JS (shAutoloader)

Highlight CSS (default.css)

Highlight JS (highlight.pack.js)

Syntax Highlighter CSS (custom.css)

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...
Post a Comment