Edit made on January 02, 2014 by RiderOfGiraffes at 11:09:36
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.