Factoring Integers_Part 1 

How do we know a number is not prime unless we find its factors?
We can use any of several tests for this  there are things that
are true about all primes, so if one of them is not true about this number
we have, then it's not prime.
For example, Fermat's Little Theorem says that if p is prime, and a
is coprime to p (so GCD(a,p)=1) then $a^{p1}\equiv1$ (mod p).
That means that if n is not even, and $2^{n1}1$ is not a multiple
of n, then n is not prime, and we know that without knowing any factors.
Example, $2^{(151)}1$ = $2^{14}1$ = 163841 = 16383 is not a multiple of 15,
so 15 is not prime.
Try that with 17.


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^2y^2=(x+y)(xy)$ 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=1009, then 91 must be $(10+3)\times(103),$
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^25183,$ which is 1,
which is a square.
That means $72^21=5183,$ so $(721)\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$
 $56255609=16$
 So $75^24^2=5609$
 And we have $(75+4)\times(754)=5609$
This doesn't seem to help with, say, 14981. Square root, round up, square,
subtract, the difference is not a square.
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 premultiplier.
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 premultiplied 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 "BSmooth" if all its prime factors are less than B.
Then we call a number "Smooth" if it's BSmooth 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 premultiplying
by a "smooth" number, one with lots of small factors. If we premultiply
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?
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