Edit made on March 02, 2014 by YuenNg at 13:19:14
Deleted text in red /
Inserted text in green
WM
HEADERS_END
!! Factoring Integers - Part 3
So in Factoring Integers_Part 2 we saw that we want to
* generate lots of QRs that we can factorise completely, and
* find a way to combine them to create a square.
The second part of that we'll deal with next time. Firstly, let's generate the QRs.
There's more than one way to do this. The first one we'll look at is now considered out-of-date, but it's instructive.
[[[>50 Of course, if /n/ is itself a square then we have factored it.
We can then take the square root, and our challenge is to factor that.
]]]
Firstly, consider the square root of /n./ This is not an integer so we write it as:
* EQN:\sqrt{n}=q_0+e_0
where EQN:e_0 is between 0 and 1. Since EQN:e_0 is between 0 and 1 we can take
its reciprocal, and write that as EQN:q_1+e_1 ...
* EQN:\sqrt{n}=q_0+1/(q_1+e_1)
... where EQN:q_1 is the largest possible integer to leave EQN:e_1 between 0 and 1.
Then we repeat this process, and we can compute
* EQN:\Large{\sqrt{n}=q_0+\frac{1}{q_1+\frac{1}{q_2+\frac{1}{q_3+\frac{1}{q_4+...}}}}}
[[[>50 Continued Fractions are cool, and there's lots you can do with them,
including a simple proof that EQN:\sqrt{2} is irrational.
But I digress ...
]]]
We can write this as
EQN:[q_0;q_1,q_2,q_3,...]
and this is called a "Continued Fraction," or "CF" for short.
We can then look at the truncations of this object:
| EQN:\Large{\frac{a_1}{b_1}=q_0+\frac{1}{q_1}} |
| EQN:\Large{\frac{a_2}{b_2}=q_0+\frac{1}{q_1+\frac{1}{q_2}}} |
| EQN:\Large{\frac{a_3}{b_3}=q_0+\frac{1}{q_1+\frac{1}{q_2+\frac{1}{q_3}}}} |
| EQN:\Large{\frac{a_4}{b_4}=q_0+\frac{1}{q_1+\frac{1}{q_2+\frac{1}{q_3+\frac{1}{q_4}}}}} |
...
[[[>50 If you look at the sequence of truncated fractions they get
closer and closer, first above, then below, bouncing back and
forth around, and getting ever closer to, the value of the CF.
The sequence converges to the value, and that's why the individual
terms are called the "convergents."
]]]
These are called the convergents of the CF (Continued Fraction), and they give
a sequence of rationals. We can prove that these rationals are in some sense
the best possible rational approximations to EQN:\sqrt{n}.
So we have
EQN:\frac{a_i}{b_i}\approx\sqrt{n}
and that means that
EQN:\frac{a_i^2}{b_i^2}\approx{n},
and so
EQN:a_i^2\approx{b_i^2n}.
Since this is supposed to be a good approximation (although admittedly some of the convergents
are better than other) that means that EQN:a_i^2 is "small" modulo /n./
[[[>50 We need to allow the EQN:a^{}_i to be negative. If it's close to, and just a little less
than, /n,/ we can think of it as a negative number that's close to zero. Again, it's "small." ]]]
In other words, the numerator of each convergent is fairly small, compared with /n./ That probably
means it's fairly easy to factor.
And that's what we wanted! We were trying to find a way of creating QRs that are easy to factor
(by some definition of "easy" and we've done that. The numerators of the convergents of the
(by some definition of "easy"), and we've done that. The numerators of the convergents of the
continued fraction of EQN:\sqrt{n} are "small" and therefore likely to be easy to factor.
And now we return to an earlier trick. We don't need to consider just the CF of EQN:\sqrt{n}, we
can also look at the CF of EQN:\sqrt{2n}, and EQN:\sqrt{3n}, and so on.
So we have a veritable factory producing QRs that are easy to factor.
In Factoring Integers_Part 4 we'll run through an example to see how this
works in practice, before moving on to using them.