# Factoring Integers_Part 5

Recap on the Factoring Integers series:

So we have seen how to use Continued Fractions to create a collection of "small" numbers that are squares modulo n, where n is the number we are trying to factor. Because these are small we can probably factor lots of them, and then we can combine those factorisations into a congruence between squares. That might give us a factorisation of the original number.

So, recap:

• We are trying to factor some number n
• If we can write n as the difference of two squares, we're done
• It's probably enough to find two squares that are congruent mod n.
• If we can completely factor lots of quadratic residues, then
• ... we may be able to create two squares that are congruent mod n.
• We do that by finding combinations that have all primes occurring an even number of times.
How do we do that?

The basic idea is straight-forward, although the details of the most modern algorithms are quite tricky. Here we'll give a basic version.

In essence we use the same technique as we use for solving linear equations via matrices, but we do it module 2. Let's look at the usual matrix method of solving equations.

Suppose we have three linear equations:


3x + 5y - 4z =  4  [1]
2x -  y + 3z =  1  [2]
-x + 2y +  z = -3  [3]


We can rearrange [3] to get:


x = 2y + z + 3.

Substituting that into the other equations gets rid of the unknown x.


3(2y + z + 3) + 5y - 4z =  4
2(2y + z + 3) -  y + 3z =  1

(6y + 3z + 9) + 5y - 4z =  4
(4y + 2z + 6) -  y + 3z =  1

11y - z  = -5
3y + 5z = -5



However, think of this as a matrix of numbers:


3  5 -4 |  4
2 -1  3 |  1
-1  2  1 | -3


Firstly rearrange to put the last row on top:


-1  2  1 | -3
3  5 -4 |  4
2 -1  3 |  1


Now negate the top row:


1 -2 -1 |  3
3  5 -4 |  4
2 -1  3 |  1


Finally, add a nultiple of the top row to each of the others, choosing the multiple to make sure the first column comes out as zero. So we add -3 times the top row to the second row, and we add -2 times the top row to the third row:


1 -2 -1 |  3
0 11 -1 | -5
0  3  5 | -5


See how the result is the same as with the equations? This is called "row reduction" and it's an important algorithm or process in the manipulation of matrices. The idea is that if you have two equations, you can add each side together and you get a new one. That can then be used in place of one of the originals.

We can continued that process here. Divide the middle row by 11 and we get:


1 -2 -1    |  3
0  1 -1/11 | -5/11
0  3  5    | -5


Add -3 times the middle row to the bottom row:


1 -2 -1     |   3
0  1 -1/11  |  -5/11
0  0  58/11 | -40/11


Finally, divide the last row by 58/11:


1 -2 -1 |   3
0  1  1 |  -5/11
0  0  1 | -40/58


That last row now interprets as z=-40/58. We can back-substitute all the way up, and solve our original equations.

OK so far?

Notice, though, how the last line progressively got more and more zeroes in it. If we think about out factorisations of quadratic residues, we can see that we have:

Modulo 55:


9* 9 = 26 =  2^1 * 13^1
10*10 = 45 =  3^2 *  5^1
11*11 = 11 = 11^1
12*12 = 34 =  2^1 * 17^1
13*13 = 14 =  2^1 *  7^1
14*14 = 31 = ...
15*15 =  5 =  5^1
17*17 = 14 =  2^1 *  7^1


Remembering that we only care about even versus odd we can write this:


2  3  5  7  11  13  17
+-------------------------
9 |  1  0  0  0   0   1   0 |  9
10 |  0  0  1  0   0   0   0 | 10
11 |  0  0  0  0   1   0   0 | 11
12 |  1  0  0  0   0   0   1 | 12
13 |  1  0  0  1   0   0   0 | 13
15 |  0  0  1  0   0   0   0 | 15
17 |  1  0  0  1   0   0   0 | 17


Now what we want to do is create rows that have all zeros, but instead of adding in the normal way, we don't care about anything except even and odd, so we add modulo 2. This is also known as "exclusive or".

Adding the exponents corresponds to multiplying the numbers, so as we "add" two rows of the table, we multiply the numbers that created them.

Let's "add" row "9" to all the rows below that have a 1 in the first column:


2  3  5  7  11  13  17
+-------------------------
9 |  1  0  0  0   0   1   0 |  9
10 |  0  0  1  0   0   0   0 | 10
11 |  0  0  0  0   1   0   0 | 11
12 |  1  0  0  0   0   0   1 | 12
13 |  1  0  0  1   0   0   0 | 13
15 |  0  0  1  0   0   0   0 | 15
17 |  1  0  0  1   0   0   0 | 17

2  3  5  7  11  13  17
+-------------------------
9 |  1  0  0  0   0   1   0 |  9
10 |  0  0  1  0   0   0   0 | 10
11 |  0  0  0  0   1   0   0 | 11
|  0  0  0  0   0   1   1 | 12 * 9
|  0  0  0  1   0   1   0 | 13 * 9
15 |  0  0  1  0   0   0   0 | 15
|  0  0  0  1   0   1   0 | 17 * 9


Now we "add" the "10" row to all the rows underneath that have a 1 in the "5" column:


2  3  5  7  11  13  17
+-------------------------
9 |  1  0  0  0   0   1   0 |  9
10 |  0  0  1  0   0   0   0 | 10
11 |  0  0  0  0   1   0   0 | 11
|  0  0  0  0   0   1   1 | 12 * 9
|  0  0  0  1   0   1   0 | 13 * 9
|  0  0  0  0   0   0   0 | 15 * 10
|  0  0  0  1   0   1   0 | 17 * 9


That's given us an all-zero row for 15*10. So that means that, modulo 55, we have:

 Here I've gone back to my original table to re-extract that 10^2 is 3*3*5 modulo n.

• (15*10)^2 = 5*45 = 3*3*5*5 = (3*5)^2
So 150^2=15^2 modulo 55, and we have our congruence of squares. This yields:


55*k = (150+15)*(150-15)
= 165*135.

 Actually we're a bit lucky here, because 55 divides 165, so the congruence would work just because of that - it's pure coincidence that the 5 pops out of the other factor. Sometimes we are not so lucky, and all the factors of the number we're trying to factor turn up in one of the numbers. Then we have to try a different combination of rows.
Taking the GCD of 135 and 55 pops out the factor 5, and we're done.

In general you need a lot of rows and comparatively few columns to make sure you have the best chance of finding a combination that comes out to a row of all zeroes. This means you need to factor a lot of quadratic residues, and you hope that they can all be factored from a relatively small pool of prime numbers.

So using the basic ideas of row reduction from Linear Algebra lets us find combinations of factorisations of Quadratic Residues that may give us a factorisation. Which is cool.

Next we'll look at another way of producing small(ish) quadratic residues.