Factoring Integers_Part 5

AllPages RecentChanges Links to this page Edit this page Search Entry portal Advice For New Users

• 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, 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.

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.

    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

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

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.