Factoring Integers_Part 1

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

Factoring Integers - Part 1

So suppose we have a big number, and we've already determined that it's not prime. Where do we start to try to work out what its factors are? Clearly we can see if it's divisible by 2, 3, 5, 7, 11, 13, etc, but that's a potentially very long job. If p is the smallest factor, we'd need to trial divide by all the primes up to p. It would be nice to have something faster.

Fermat made an interesting observation. He started with the identity $x^2-y^2=(x+y)(x-y)$ and realised that if any number is the difference of two squares, and we know what they are, then that immediately gives us a factorisation. So if we note that 91=100-9, then 91 must be $(10+3)\times(10-3),$ which it is.

Now this works really well if n has two factors that are close together. Take, for example, 5183. Trial division is comparatively slow for that, but if we take the square root and round up we get 72, $72^2=5184.$ The difference between that and our target number is $72^2-5183,$ which is 1, which is a square. That means $72^2-1=5183,$ so $(72-1)\times(72+1)=5183,$ and we're done.

This, by the way, will make a lot more sense if you try it yourself. Try factoring 6887. The square root is 82.987950... so you round up to 83, square that, and look at the difference with 6887. The difference is not a square, so we haven't succeeded yet. But try it with 84 instead.

We can try that again with something like 5609:

• $\sqrt{5609}=74.893...$
• $75^2=5625$
• $5625-5609=16$
• So $75^2-4^2=5609$
• And we have $(75+4)\times(75-4)=5609$

It's worth taking a moment to talk about the "Greatest Common Divisor", or GCD of two numbers. The name says it all, but we use the tool constantly. Here we have started with 14981, multiplied by 3 to get 44943, factored that into 211*213, and now we have to recover the factors of our original number. The easiest thing to do is take the GCD of our original, and each the numbers we got. GCD(14981,211) = 211 GCD(14981,213) = 71 If we had multiplied first by something large and complex, this is a fast way to locate factors of the original number and discard the extra factors introduced by our pre-multiplier. The GCD will raise its head again and again as we go on.

Bother.

Try the next square up. No.

Bother.

Try the next square up. Still no.

Bother.

Still, you can keep going like that, but there's a trick.

Let's suppose that 14981 has two factors (not necessarily prime) that are close to a simple ratio of each other. Suppose one is three times the other, so n=a*b where $a\approx{3b}.$ That means $3n=a\times(3b)$ has two factors that are close together, so Fermat's technique would work.

If we take 14981*3=44943 and try Fermat's difference of squares method, we quickly get 211*213. We need to remove our additional factor of three that we pre-multiplied by, and that comes out of the 213, so the factorisation of our original number is 211*71.

Of course, in practice we have no way of knowing that the factors of the number we're working on are a ratio of 3 apart, or 5 apart, or anything else. This, for the moment, is a "just suppose..."

So sometimes it helps to multiply by a factor, but that, in turn, makes the number to be factored bigger, so if we use such a tactic we do need to balance the benefits against the disadvantages.

The real problem is that we have no clue about the ratio between the factors of n.

We call a number "B-Smooth" if all its prime factors are less than B. Then we call a number "Smooth" if it's B-Smooth for some comparatively small value of B. The exact sense of "comparatively small" can depend on the context.

We can also go for lots of possible ratios all at once by pre-multiplying by a "smooth" number, one with lots of small factors. If we pre-multiply by 24, say, then Fermat's method will be successful if the factors happen to be in the ratio of 1:24, or 2:12, or 3:8, or 4:6. Larger factors give more options, but again, at a cost of increasing the size of the number we are then trying to factor.

So can we improve this?

• FactoringIntegers_Part2 - Manufacturing squares.