Editing FactoringIntegers_Part4
You are currently not logged in.
To change this, fill in the following fields:
Username
Password
Who can read this page?
The World
Members
Council
Admin
You have been granted an edit lock on this page
until Sat Apr 20 12:45:10 2024.
Press
to finish editing.
Who can edit this page?
World editing disabled
Members
Council
Admin
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. [[[> | 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 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 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. ---- Next, Factoring Integers_Part 5, where we see how to find factorisations that can be combined to produce a square.