Tip:
Highlight text to annotate it
X
>> DR GRIME: In 2002 mathematicians published a new method to test for primes
and finally they found a fast way that was 100%. This is now one of the latest things.
So this is called that AKS test. And it's pretty much a very similar idea to what we
did with the Fermat Little Theorem. It's very similar to that. And the test is, that if
you've got a number p and we are going to do this. We're going to take (x - 1)
to the power p and then we're going to subtract (x^p - 1). Alright.
So it's a polynomial, I'll show you an example in a second. If all coefficients are divisible
by p then p is prime. And if they're not it's composite. it's 100% this test. I'll show
you an example. let's take (x - 1)³. Yeah, let's do that. (x - 1)³.
>> BRADY: So 3 is the number we're testing?
>> DR GRIME: Yeah, 3 is the number we're testing. We know it's a prime don't we? But we're going
to test it. We're going to take (x - 1)³ and so that's, to make it explicit,
(x - 1) by (x - 1) by (x - 1). OK. Multiply this out, you get a polynomial called
x³ - 3x² + 3x - 1. That's what you get. Now you're subtracting the x³,
I'm told- I'm told to that and you're, what's that, adding on the 1. So these, these dissapear.
This says these numbers are divisible by 3. If it is divisible by 3, 3 is the number we're
testing, then it is a prime. If it's not divisible by 3, it is not a prime. And that's our 100%
test. So this was really important, this was huge news when they published this. 2002 they
published it and it was huge news because it was a fast test as well. Or it could be
made in to a fast test. There's a little thing they do just to make it a bit faster because
it does get quite difficult, these polynomials get quite nasty. Just to make it a little
bit faster what they did is (x - a)^p minus (x^p - a), so 'a'
is a number like we had before. And they said this was equal to p lots of something plus,
there you go, a little (x^r - 1) multiplied by something. So that's not quite the same,
that's a little bit different, this was actually faster to work with, it makes a faster calculation.
And for this version you need to test a few candidates for 'a' here. You test a few.
And if it passes that test then you can determine that p, which is what we're trying to work
out. Try and work that out, you can find it's prime or not.
Mathematics is done all day, you know, every day. New mathematics is coming out all the
time. And only, well I say recently, 12 years ago they finally solved the problem.
It is still faster to do a Fermat test. it's still faster to do this, but this is not outrageously
slow anymore. This doesn't take us to the end of the universe anymore. So we can actually
run this test. It's slower than the Fermat test, but 100% true.