Edit made on August 27, 2014 by ColinWright at 13:41:44
Deleted text in red /
Inserted text in green
WM
HEADERS_END
!! Factoring Integers - Part 1
[[[>50
!!! How do we know a number is not prime unless we find its factors?
[[[>50 We can use any of several tests for this - there are things that
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 co-prime to /p/ (so GCD(a,p)=1) then EQN:a^{p-1}\equiv1 /(mod/p)./
That means that if /n/ is not even, and EQN:2^{n-1}-1 is not a multiple
of /n,/ then /n/ is not prime, and we know that without knowing any factors.
Example, EQN:2^{(15-1)}-1 = EQN:2^{14}-1 = 16384-1 = 16383 is not a multiple of 15,
so 15 is not prime.
Try that with 17.
]]]
!! 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
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
EQN:x^2-y^2=(x+y)(x-y) and realised that if any number is the difference of
EQN: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 EQN:(10+3)\times(10-3),
which it is.
Now this works really well if /n/ has two factors that are close together.
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, EQN:72^2=5184. The difference
between that and our target number is 1, EQN:72^2-5183=1 , which is a square.
between that and our target number is
EQN:72^2-5183, which is 1,
which is a square.
That means EQN:72^2-1=5183, so EQN:(72-1)\times(72+1)=5183, and we're done.
[[[>50 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:
* EQN:\sqrt{5609}=74.893...
* EQN:75^2=5625
* EQN:5625-5609=16
* So EQN:75^2-4^2=5609
* And we have EQN:(75+4)\times(75-4)=5609
This doesn't seem to help with, say, 14981. Square root, round up, square,
subtract, the difference is not a square.
[[[>50
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 EQN:a\approx{3b}. That means EQN:3n=a\times(3b) has two
factors that are close together, so Fermat's technique would work.
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.
[[[>50 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
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./
The ~real problem is that we have no clue about the ratio between the factors of /n./
[[[>50
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.