Deleted text in red / Inserted text in green

WM

HEADERS_END

Recap on the Factoring Integers series:

* Factoring Integers_Part 1 : Fermat's method

* Factoring Integers_Part 2 : Quadratic residues

* Factoring Integers_Part 3 : Continued Fractions to find QRs

* Factoring Integers_Part 4 : CFrac in action

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 11 | -5

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 | -5/11

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 | -5/11

0 0 2 | -40/11

0 1 -1/11 | -5/11

0 0 58/11 | -40/11

}}}

Finally, divide the last row by 2:

Finally, divide the last row by 58/11:

{{{

1 -2 -1 | 3

0 1 1 | -5/11

0 0 1 | -20/11

0 0 1 | -40/58

}}}

That last row now interprets as z=-20/11. We can back-substitute

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:

[[[>50 Here I've gone back to my original table to re-extract that 15^2

[[[>50 Here I've gone back to my original table to re-extract that 10^2

is 3*3*5 modulo n. ]]]

* (15*10)^2 = 45*5 = 3*3*5*5 = (3*5)^2

* (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.

}}}

[[[>50 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.