As said in the previous post, we will now present Dixon’s algorithm, which is a straightforward implementation of the ideas discussed so far. As we will see, it is still not very fast, but at least it is significantly better than trial division.

# Monthly Archives: December 2013

# Factoring integers—Factor bases

We are now facing the following problem: given an integer $n$ which we wish to factor, find integers $x_1,\dots,x_k$ such that $\prod \left(x_i^2-n\right)$ is a square. We mentioned in the previous post that Kraitchik basically used trial and error to find such values, but still he did not try completely random values.

# Factoring integers—Fermat and Kraitchik

### Fermat

Some integers with no obvious small divisor, such as for example $8051$, are nonetheless easily factored on paper. One need only notice that

\[ 8051 = 8100-49 = 90^2 – 7^2, \]

and use the well-known identity $a^2-b^2 = (a+b)(a-b)$ to find that $8051 = 83\times 97$.

# Polynomial factorisation over finite fields, part 3: Final splitting (Cantor-Zassenhaus)

*(Part of this.)*

We are left with the following problem: given a polynomial $A \in \mathbf{F}_p[X]$ which is known to be squarefree and the product of irreducible factors which are all of degree $d$, find these factors. One algorithm to do this was introduced by Cantor and Zassenhaus in 1981.