Factoring Integers_Part 4

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

Let's see that in action. Let's factor 4429. We need to find the continued fraction for $\sqrt{4429},$ which is 66.550733... or so. So to start with, $\sqrt{4429}$ is 66 and a bit, and then we take the reciprocal of "the bit", and repeat:

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

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.

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.

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

a $a^2$ $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 $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

Next, Factoring Integers_Part 5, where we see how to find factorisations that can be combined to produce a square.