Edit made on March 01, 2014 by YuenNg at 12:05:08
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.