Factoring Integers_Part 2
So in Factoring Integers_Part 1 we saw how we can use the difference of two squares to factor, although the method works best when the factors are close together. We have also seen how we can use a pre-multiplier to help find factors even when they are not close together.
By using the pre-multiplier we are finding solutions to equations of the form:
So let's look at a few of them. Here are a few Quadratic Residues (QRs) modulo 5959, along with their factorisations:
We're pretending -1 is a prime, |
because we are factoring both
positive and negative numbers,
and we need the -1 to complete
Now, if any of these quadratic residues were themselves a square then, as we saw in Factoring Integers_Part 1, we'd be done. But they aren't.
The clever observation is this.
Look at lines X, Y, and Z. These have been chosen carefully because between them, the primes in the factorisations of the QRs all turn up an even number of times. That means the product of the QRs is a square.
Of course, the QRs themselves are squares of the numbers in the first column. So multiply the numbers in the first column:
So $5749^2=210^2$ when working modulo 5959.
Now we have manufactured exactly what we want - two squares that are equal mod n. That means that (5749-210)*(5749+210) is a multiple of 5959, and we'd expect to get a factorisation. Unfortunately, when we try to get the factorisation we find that 5749+210=5959, which is what we're trying to factor. So we've failed.
OK, let's try again. Here's our table, |
and this time let's combine lines A, B,
C, and D: Again, these have been chosen
so that the primes in the factorisations
of the QRs all turn up an even number of
Now we get:
So if we take lots of squares mod n and factor them completely, perhaps we can then find some combination of them which, when multiplied together, gives us the congruence we need.
The challenges now are: