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

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 really we are solving $x^2-y^2{\equiv}0$ (mod n), which is to say $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:

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

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.

$(-30)\times{(21)}\times{(-70)}$
$=(-1{\times}2{\times}3{\times}5){\times}(3{\times}7){\times}(-1{\times}2{\times}5{\times}7)$
$=2^2\times{3^2}\times{5^3}\times{7^2}$
$=(2\times{3}\times{5}\times{7})^2$
$=210^2$

Of course, the QRs themselves are squares of the numbers in the first column. So multiply the numbers in the first column:

$77{\times}386{\times}1962=58314564=5749$ (mod 5959)

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.

Bother.

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

Now we get:

That gives us the factorisation:
We might look at this in a little more detail. We have a solution to $x^2\equiv{y^2}$ (mod n) so that means we get:
  • $x^2-y^2{\equiv}0$ (mod n)
  • $x^2-y^2=kn$ for some k
  • $(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.

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:

In Factoring Integers_Part 3 we look at one way of solving the first problem - there are more than one.
Links to this page / Page history / Last change to this page
Recent changes / Edit this page (with sufficient authority)
All pages / Search / Change password / Logout