Deleted text in red / Inserted text in green

WM

HEADERS_END

So in Factoring Integers_Part 3 we saw how Continued Fractions can be used to

create lots of small quadratic residues, and then those, in turn, can be used

to create a difference of two squares and thereby get a factorisation.

Let's see that in action.

Let's factor 4429. We need to find the continued fraction for EQN:\sqrt{4429},

which is 66.550733... or so. So to start with, EQN:\sqrt{4429} is 66 and a bit,

and then we take the reciprocal of "the bit", and repeat:

COLUMN_START^

| | *q* | |>> *r* <<| | |>> 1/r <<| |

| 66.550733... | 66 | 0.550733... | 1.815763... |

| 1.815763... | 1 | 0.815763... | 1.225846... |

| 1.225846... | 1 | 0.225846... | 4.427805... |

| 4.427805... | 4 | 0.427805... | 2.337514... |

| 2.337514... | 2 | 0.337514... | 2.962839... |

| 2.962839... | 2 | 0.962839... | 1.038595... |

| 1.038595... | 1 | 0.038595... | 25.910147... |

| 25.910147... | 25 | 0.910147... | 1.098724... |

| ... | ... | ... | ... |

COLUMN_SPLIT

We use *q* for the integer part.

After a time these sums become less and less accurate because of rounding errors.

There is a way to compute using exact integer arithmetic, but that's a detail

we won't go into here.

COLUMN_END

Now we remember, successive truncations of the continued fraction give

rational approximations and get closer and closer, converging to the

true value. These truncations are called the convergents, and we now

compute them.

[[[> Yes, it's a bit of magic:

]]]

The top row of this table is the *q* column from above, then middle row

produces the numerators of convergents, and the last row is the denominators.

|>>

| | | 66 | 1 | 1 | 4 | 2 | 2 | 1 | 25 | ... |

| 0 | 1 | 66 | 67 | 133 | 599 | 1331 | 3261 | 4592 | ... | ... |

| 1 | 0 | 1 | 1 | 2 | 9 | 20 | 49 | 69 | ... | ... |

<<|

See if you can see the rule being used to compute the table.

So the convergents are:

* 66/1, 67/1, 133/2, 599/9, 1331/20, 3261/49, 4592/69, ...

* 66.0, 67.0, 66.5, 66.556, 66.55, 66.551..., 66.55072...

As a quick check, if we take 4592/69 (for example)

and square it, we get almost exactly 4429.

But it's the middle row we're interested in. When squared and reduced modulo 4429,

each number in the middle row should turn out to be a comparatively small number:

[[[>

| a | EQN:a^2 | EQN:a^2 /mod/n/ | |

| 66 | |>> 4356 <<| | |>> -73 <<| | |

| 67 | |>> 4489 <<| | |>> 60 <<| | 2*2*3*5 |

| 133 | |>> 17689 <<| | |>> -27 <<| | -1*3*3*3 |

| 599 | |>> 358801 <<| | |>> 52 <<| | |

| 1331 | |>> 1771561 <<| | |>> -39 <<| | |

| 3261 | |>> 10634121 <<| | |>> 92 <<| | |

| 4592 | |>> 21086464 <<| | |>> -5 <<| | -1*5 |

----

Why not try this with rows 133, 599 _

and one other row?

]]]

But it's the middle row we're interested in. When squared and reduced modulo 4429,

each number in the middle row should turn out to be a comparatively small number:

As you can see, the third column is mostly quite small numbers. We've

included the factorisations of some of these, and combining those we get

(2*2*3*5)*(-1*3*3*3)*(-1*5) which is (2*3*3*5)^2, or 90^2.

So, working modulo 4429, (67*133*4592)^2=90^2

So, ~working modulo 4429, (67*133*4592)^2=90^2

We compute 67*133*4592 /mod/n/ is 4210, so we have EQN:4210^2=90^2

That means, if this has worked, that (4210+90)*(4210-90) is 0 /mod/n/ and

That means, if this has ~worked, that (4210+90)*(4210-90) is 0 /mod/n/ and

hence is a multiple of /n./ We hope, then, that some of the factors of /n/

are in 4210-90, and some are in 4210+90.

And they are. Using the GCD we can extract the factors from 4429 as follows:

* gcd(4210-90,4429) = 103

* gcd(4210+90,4429) = 43

And it's right: 43*103 = 4429, and we're done.

[[[> Why not try this with rows 133, 599 and one other row?

]]]

----

Next, Factoring Integers_Part 5 (not yet uploaded), where we see how to find factorisations

Next, Factoring Integers_Part 5, where we see how to find factorisations

that can be combined to produce a square.