Editing FactoringIntegers_Part2
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 Fri Apr 26 03:58:19 2024.
Press
to finish editing.
Who can edit this page?
World editing disabled
Members
Council
Admin
!! 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: * EQN:x^2-y^2=n * EQN:x^2-y^2=2n * EQN:x^2-y^2=3n * EQN:x^2-y^2=4n * /etc./ So really we are solving EQN:x^2-y^2{\equiv}0 /(mod/n),/ which is to say EQN:x^2{\equiv}y^2 /(mod/n)./ That suggests that we are interested in squares modulo n. The concept of "Squares mod n" is so important we actually give them a name of their own - they're called "Quadratic Residues" or QRs for short. They turn up many, many times in number theory. So let's look at a few of them. Here are a few Quadratic Residues (QRs) modulo 5959, along with their factorisations: |>> COLUMN_START | *a* | EQN:a^2 | Factors | | 77 | -30 | -1, 2, 3, 5 | X | | 386 | 21 | 3, 7 | Y | | 1145 | 45 | 3, 3, 5 | | | 1962 | -70 | -1, 2, 5, 7 | Z | | 2779 | -23 | -1, 23 | | | 4252 | -102 | -1, 2, 3, 17 | | | 5397 | 17 | 17 | | COLUMN_SPLIT^ COLUMN_SPLIT We're pretending -1 is a prime, _ because we are factoring both _ positive and negative numbers, _ and we need the -1 to complete _ the factorisation. COLUMN_END <<| 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. |>> EQN:(-30)\times{(21)}\times{(-70)} _ EQN:=(-1{\times}2{\times}3{\times}5){\times}(3{\times}7){\times}(-1{\times}2{\times}5{\times}7) _ EQN:=2^2\times{3^2}\times{5^3}\times{7^2} _ EQN:=(2\times{3}\times{5}\times{7})^2 _ EQN:=210^2 <<| Of course, the QRs themselves are squares of the numbers in the first column. So multiply the numbers in the first column: |>> EQN:77{\times}386{\times}1962=58314564=5749 /(mod/5959)/ <<| So EQN: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. Bother. |>> COLUMN_START^ 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 _ times. COLUMN_SPLIT^ COLUMN_SPLIT^ | *a* | EQN:a^2 | Factors | | 77 | -30 | -1, 2, 3, 5 | A | | 386 | 21 | 3, 7 | | | 1145 | 45 | 3, 3, 5 | B | | 1962 | -70 | -1, 2, 5, 7 | | | 2779 | -23 | -1, 23 | | | 4252 | -102 | -1, 2, 3, 17 | C | | 5397 | 17 | 17 | D | COLUMN_END <<| Now we get: * EQN:(77{\times}1145{\times}4252{\times}5397)^2=(2{\times}3{\times}3{\times}5{\times}17)^2 /(mod/5959)/ * EQN:1833^2=1530^2 /(mod/5959)/ That gives us the factorisation: [[[>50 We might look at this in a little more detail. We have a solution to EQN:x^2\equiv{y^2} /(mod/n)/ so that means we get: * EQN:x^2-y^2{\equiv}0 /(mod/n)/ * EQN:x^2-y^2=kn for some /k/ * EQN:(x+y)(x-y)=kn for some /k/ That means the prime factors of /kn/ appear in the numbers /x+y/ and /x-y./ We hope that the prime factors of /n/ are split between these two numbers. So we look for prime factors in /x+y/ and /n,/ and the easy way to do that is to take the gcd of /x+y/ and /n./ ]]] * 1833-1530= 303 ** gcd(303,5959)=101 * 1833+1530=3363 ** gcd(3363,5959)=59 So we're done! 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: * find lots and lots of QRs (quadratic residues) that we can factor completely, * find a way to combine them to give us a square on the right hand side. In Factoring Integers_Part 3 we look at one way of solving the first problem - there are more than one.