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.