Fool-Proof Test for Primes - Numberphile
Вставка
- Опубліковано 7 лют 2025
- The AKS Test has been a major break-through in the search for Prime Numbers.
More links & stuff in full description below ↓↓↓
See the previous video about Fermat's Prime Test at: • Liar Numbers - Numberp...
The video features Dr James Grime - singingbanana.com
The AKS Test paper: bit.ly/primetest
Support us on Patreon: / numberphile
NUMBERPHILE
Website: www.numberphile...
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberph...
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumb...
Videos by Brady Haran
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanb...
Sign up for (occasional) emails: eepurl.com/YdjL9
Numberphile T-Shirts: teespring.com/...
Other merchandise: store.dftba.co...
This video will be properly listed in the next day or two, but I have it viewable for people who watched the "Fermat's Little Theorem Video" and can't wait! :)
+Numberphile It's faster to just find the Pth entry in Pascal's triangle and remove the 1s on each end, no? That's what the coefficients are.
I have only just watched this video and I came to exactly the same conclusion.
paulscoombes There are on the order of P/2 coefficients
to check though (half due to symmetry), so I won't
be replacing the trial division algorithm in my own
prime generator with some other test very soon.
Since the second term is px^(p-1) and the second to last is px, you can disregard them too. Etc.
Numberphile why not simply construct the pascal's triangle and determine primes ?? we can construct only the left half of pascal's triangle to determine primes.
'If you have a p.'
*writes x*
You've lost me.
x marks the spot
and then you still watch more to see if it becomes any easier... alas no.
@@JasonKaler I don't even see how this is faster. From a programming perspective this, this would be insanely slow with big numbers.
Bro same
@@resphantom
You're partially right. It's complexity is O(log⁶n) which is way better than the alternative of checking primes up to square root of n which is about O(n^0.5). But there is for example the Miller-Rabin test, that has a complexity of O(k*log³n). (k is the number of rounds youre testing). Technically, the Miller-Rabin test is not 100% accurate, but the probability of a composite number to pass this test as a prime is at worst case: 0.25^k, so when k is, say, 150, the probability of it being wrong is about one over googol.
I can appreciate the need to make the calculation faster, but I was kind of hoping they'd just made a *really* huge Pascal's Triangle to figure things out with.
Binomial Theorem. Instant Pascal.
@@mirmarq429 not really?
This would take exponential space and exponential time for an n-bit candidate prime, far slower than the O(n^6) AKS test, let alone the GRH dependent (probably correct) O(n^4) Miller test, and the many much faster probabilistic O(n^2) tests, or special-form tests such as Lucas-Lehmer which is also O(n^2) (where O means soft-O notation)
@@marios1861 yes really. do some maths bro.
@@Chainless_Slave7 the recursion needed to construct a pascal triange is encapsulated through the factorial operator of the binomial theorem, thus it is not "instant". Learn some math _bro_
This primality test is known as AKS primality test because it was developed by three indian mathematicians Manindra Agarwal, Neeraj Kayal, Nitin Saxena. They are currently working as professor at Indian Institute of Technology Kanpur Computer Science Department.
But they all got their training from a Swedish professor over skype - if what I've heard rumors about is correct. If so this should be attributed as a Swedish discovery.
@@swedishpsychopath8795 lol
@@swedishpsychopath8795 Username checks out.. 😅:)
@@swedishpsychopath8795 cope
@@swedishpsychopath8795 That's not how it works.. it doesn't matter who they were trained by dude.
That is very cool. Amazing that polynomials are one of the first bits of algebraic maths that you do in school and it ends up being the solution to finding primes - not something outrageously complicated!
Yeah it's always amusing when something so simple can solve something like this
Its not 100% test for primes ,the sum of the binomial coefficients make this (2^n -2)/2=2^(n-1)≡1 mod n. this is just a base-2 fermat's prime test lol
@@KulakOfGulag You're wrong, it is 100%. Go do some reading.
in other words, if the (p+1)th row of pascals triangle only contains multiples of p (excluding the 1s on either end), then p is prime?
I was thinking the same thing
So you're counting from the peak, C(0,0) = 1? So that the (p+1)st row is C(p,k), for k = 0...p.
Then, I think yes, because you can generate that row by:
C(p,0) = 1 ; then for k = 1...p-1:
C(p, k) = [(p-k+1)/k] C(p, k-1)
So that, as you proceed along that row, you're successively removing (by that division by k) each integer factor from 1 through p-1, while only appending (by the multiplication by p-k+1) factors smaller than p.
Sometimes you will remove prime factors that you've earlier (or simultaneously!) multiplied into the number, but if p is prime, it will never be removed, because it's always larger than the {1...p-1} that are being divided out.
Harder, but I believe, possible, to show, is that if p is composite, then at some point, some part of its prime factorization will get reduced enough that p won't divide C.
nathanisbored yes but determining half the terms in a horizontal row of Pascal's triangle is O(n) time complexity operation - which is dependent on , n more rows which come before it.
so overall this method will perform slower once you are hunting for large primes as it takes O(n*n) time.
Sieve of Eratosthenes takes O(n log n) time , so its faster.
+Subhadeep, As I mentioned on another post, while this method using binomials is terribly slow, it isn't AKS. Both it and the SoE are exponential in the size of the input, while AKS is polynomial. The complexity is O(log^6 n). AKS is much, much faster than the SoE for large numbers. The SoE isn't properly a primality test for a single input, as it is just trial division when run on a single number. For generating small primes, the segmented SoE is the right tool. It's still used for ranges of large number though there just to remove small factors, then a primality test on the remaining candidates.
I understand that, I was just making a connection because I noticed the dualism at a glance. I think the pascal's triangle is a more intuitive way to explain what the formula means, even if it's not a more efficient way to calculate it.
Do mathematicians just have brown paper and sharpies on their person at all times?
don't you?
When a reply gets more likes than the comment.
+Bread Breadmen Come back to this thread. Your comment is no longer true, lol.
Right now it's 121 to the comment, 118 to the reply.
Shane's Book Corner
Substitute Professor for mathematitian and chalk board for brown paper and chalk for sharpie.
Brady, I want to thank you very much from the heart for creating and constantly updating this channel. Throughout my entire life, except for geometry, I have been simply awful at math. I've been watching this channel now for over a year now, and you have helped my brain finally start grasping some number theorems. James has also been such a great help as well. His enthusiasm and child-like adoration of numbers has made (re)learning math more accessible. God has gifted me with the ability to excel in science, English, and art, but math always escaped me. Ironically, I love watching people who excel at it work it out. (That might explain why Numb3rs is one of my all-time favorite tv dramas.) And now, Numberphile is in my top 5 favorite UA-cam channels. (Blushing) Admittedly, I find Dr. James Grime to be absolutely attractive and handsome in addition to being a very sharp dressed man! James, if you ever come visit Los Angeles, please let us know. I'd love to come see you and Simon's Enigma Machine. (I loved U-571!)
This test is equivalent at looking if the coefficients of the line number p (excluding the first and the last ones) of Pascal's triangle are divisible by p. I like your channel, you are great teachers and can be understood by anyone :-)
It happens so, a few days ago I discovered the relation between binomials and Pascal's triangle. When writing out the triangle I noticed that if a row number was a prime, I could divide the numbers in the triangle (corresponding to that row number), except for the first and last number (that's why they subtract (x^p-1) from (x-1)^p) by that row number, thus a prime. It's so logical! The easiest way to calculate a binomial is using that triangle to identify the coefficients.
So... all this time trying to find complex tests to prove primality and the answer was always in Pascal's triangle? Oh god...
I love all of your videos on Primes
I'm still impressed that our math teacher managed to adequately prepared us for our finals back in 2010 and still found time to teach us an entire lesson about this particular result.
I'd love to know more about the Theory behind this method, and how it relates to the Fermat test. In other words, how come it works, and what it says about primeness. I've always liked the name of the Sieve of Eratosthenes, because that's essentially what prime numbers are: unfilled holes in the whole number line. Think of a number line stretching to infinity. It starts out unmarked. So you mark off 1 to get started. Then you begin with the multiples. Mark off all the multiples of 2 up to infinity. The next unmarked integer will be prime, in this case, 3. Mark off very multiple of 3 up to infinity. Again, the next hole in the line, 5, is prime. Mark off every multiple of 5. Rinse and repeat ad infinitum. Now, of course you can't actually do this mechanical thing (but possibly a quantum computer could do). So instead, by Eratosthenes' method, you attempt to divide each number by all the primes that precede it, and if it is indivisible by all the primes, it is prime. Now along comes Fermat and this new test, which both still require divisibility to be tested, but they significantly enhance the process, but do they point to a possible algorithm that could generate primes? For example, input the highest known prime, out comes the next prime... Sadly, no. I would be interested to discover whether it has been established that no such algorithm is possible, and if not, why not.
I understand about 10% of what Dr. Grimes, says, but I watch him because he's such a pleasant person.
It's crazy to think that even now people are innovating in the field of prime numbers and primality testing!
Cool - I'll have to check out the AKS test a bit more later.
Good thing we have computers now. I'd jump off a bridge if I was the guy responsible to figure out if the 1024 bit numbers are prime or not by expanding via the AKS test.
This is such a beautiful result. I'm moved.
This method is found by two students and one professor of IIT Kanpur.
My teacher showed me this in class and suddenly it’s on my recommended
Cool!
Primes for Grimes! :D
The AKS primality test (also known as Agrawal-Kayal-Saxena primality test and cyclotomic AKS test): work of Indian mathematicians from IIT Kanpur.
Note that this is *not* the AKS test, but a not very efficient test that has been know for centuries. (Basically, if choose(p, 1) through choose(p, p-1) are all divisible by p, p is a prime number.) The AKS test builds upon that, see: en.wikipedia.org/wiki/AKS_primality_test
Can somebody correct me, if I am wrong, but doesn't this follow from Pascal triangle being made out of combinatorial numbers (n,k) and if n is prime that by calculating it k never divides n from n!(unless k=0 or k=n)
Pretty much
Equivalent to the first test: if p divides nCr(p,n) for each n=1,2,...,p-1, then p is prime.
who disliked this??? why!! seriously this deserves 0 dislikes
It's not actually the AKS primality test. That's probably why.
Prove the sum of 4 prime numbers are divisible by 60 if
5 < p < q < r < s < p + 10
It was very cool to think through why this is true! The x^k coefficient of (x-1)^n is nCk = n! / (k! (n - k)!).
So if n is prime, there's no way to get factors in the denominator to cancel the n in the numerator, so nCk is divisible by n.
This is a test in order to check if a number is prime. So the opposite must be true.
I've never thought that the mathematics would be so fascinating. Best greetings from Poland.
Great couple of videos here :) this second result is incredible, as I'm reading it as "Iff p is a prime, then all the numbers (excluding 1) on the pth row of Pascal's triangle are divisible by p" and I have no idea why that ought to be the case! Would like to read the paper.
Excellent video, as always. On a different note, with no disrespects to others, am happy and proud that AKS test was discovered/devised by three brilliant Indian minds from IIT-Kanpur. So happy for them!!
You're bluffing, aren't you?
@@OrchestratedChicanery Check the Wikipedia page of AKS test..
So can you just use Pascal's Triangle to find all the primes?
Basically yes, since this triangle gives you the coefficient of a binomial expansion. You do have to ignore the 1's at the ends
@@muzammilshafique7629 .. actually yes you can. if n choose k mod n == 0 for 0
Yep!
Yes
Kind of. Pascal’s triangle is why the algorithm works, but you don’t really use the triangle. Instead, you exploit the fact that modular exponentiation is much faster than traditional exponentiation, not only with numbers but also with polynomials.
I think Fermat's Little Theorem should be used to as an initial check, then run through the latest one to be sure. This allows Fermat's test to act like a filter allowing he slower test to pick out the Carmichael numbers leaving only the primes.
In practice you use the Miller-Rabin test. If you run it 20 times your chance of being wrong is: 1/4^20 ~ 9.095 x 10^-13. If you want to be sure, then run AKS.
That's what's already being done.
was thinking the same thing. that could save us some time!
You are patrially right. AKS is too slow for real life application. But your idea is in use. Usually, Fermat's test is followed by Solovay-Strassen algorithm. That one is not accuarate as well, but it never fails on the same number with Fermat's (or Miller-Rabin, to be exact)
Also known as Agrawal-Kayal-Saxena primality test and cyclotomic AKS test. A deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists at the Indian Institute of Technology Kanpur, on August 6, 2002.
Gotta love a little bit of certainty when looking for new primes. :)
Always enjoying James's zeal! Here a new law: Shirt+marker-lid+enthusiasm=be careful.
Oh I get it. So in the binomial coefficient, if it's prime then it won't be cancelled out by any of the denominator of the coefficient. You subtract the last binomial because obviously the first and last coefficient will be 1.
It all makes sense! :) I just wonder why it works if and _only if_ the number is prime!
Yea, I was thinking that, too! I figured something for n even: If n is composite and even, then n choose 2 is not divisible by n.
mikecmtong
For n even you also get (when subtracting (x^p-1)) a +2 at the very end which also is divisible by n if and only if n is a prime! :)
Zardo Schneckmag
mikecmtong
It ONLY works for primes because if you take the first and last coefficients away from (x-y)^p you get sum(n=1..p-1){pCn*x^(p-n)*(-y)^n} so the binomial coefficient parts (p choose n or pCn) go from 1 to p-1. So if for all of those ones, p is NEVER canceled out by something in the denominator, then it means that p is not divisible by any number less than p other than 1 so it's prime.
ImAllInNow
I just don't get why. Why can't it be that you additionally multiply by a component of n, so it doesn't cancel out? After all there are more factors in the numerators.
My Fool-Proof Test to find Primes.
1. Divide your Number by Every Number Below It (Except 1)
If you get a whole number as a result in one or more of the divisions, the number is composite (Not Prime)
You guys should do a video explaining the intuition behind the Fundamental theorem of calculus. Its pretty complex as to why the difference of the antiderivatives is equal to area under the curve.
Prime numbered rows in Pascal's triangle only consist of 1 and the numbers divisible by the prime. Like 5 would have 1,5,10,10,5,1. 7 will have 1,7,21,35,35,21,7,1 and so on
And we know that nth row of Pascal's triangle sums up to 2^n. So for every n where (2^n - 2)/n equals a positive integer, n is prime
so basically what this is saying is that a number "p" is prime if every combination from "pC1" to "pC(p-1)" is divisible by "p". that's what I gathered at least, and it seems easier to think of it like that than they way they explained haha
Geez. This is amazing.
the answer should be around a list of 115600 moves because the square root of 1161=34.07 and the square root of 12=3.46 fairly close right movement of the decimal on incredibly similar numbers so if the decimal was moved once more hypothetically then it should approx. 115600 for four steps either way to be certain death.
I think aks-test is one of the biggest discoveries of 2000-2010. Not only it is definitive, it is polynomial. (There is not point of a test that is exponential, because you could simple do factorization).
Thanks Brady! Great videos!
By taxing in the test x=2, one has: for any prime p there exists a hole number h such (2^p - 2)/p=h which looks like a direct formulae of primes.
I got the same, trank you, because my way was very complicated and now I could maybe remember it.
So basically, you can look at pascal's triangle right? If a number is prime, then all the numbers in its row in pascal's triangle are divisible by it. For example,if we look at the number 5, in the row in Pascal's triangle is 1, 5, 10, 10, 5, 1. Excluding the 1's, every single number in that row is divisible by 5.
Finding the k-th pascal's row is still of O(k) time complexity so the modulo test would still give faster results at O(sqrt(n)) complexity. Where is AKS test applied?
Thats what I was thinking the whole time. This seems cool at first but it is really slow algorithm unless they do have some other means to make it faster.
(x-1)^p is a sum of p+1 numbers. Subtracting x^p and 1 it is still a sum of p-1 numbers (with p-1 coefficients).
Now you have to perform a division by p p-1 times.
Doing a sieve of Eratosthenes up to SqRt(p) and trial divide p with all primes up to SqRt(p) you only need to perform ~ SqRt(p)/ln(SqRt(p)) divisions.
F.e: prime 1000003 (first prime > 1e6):
With AKS you need to do 1000002 divisions by 1000003.
With SoE and TD you need to do 168 divisions with numbers up to 997
AKS is certainly very interesting for mathematical reasons, but I don't see any acceleration in 'practice'
So you take Pascal's triangle, and for row n, you remove the first and last entry and check if the remaining elements divide the n? That's wicked! How did they go about determining that?!? How do you think so abstractly and see that? Truly incredible and wonderfully elegant.
What they did was quite simple, so it can be further broken down.
If 2^(p-1) - (1 + p) is divisible by p, then p is a prime, where p is natural numbers, EXCLUDING {1,2,3}
I got a chance to be interviewed by the person who found this algorithm for a Phd position under him. The best day of my life.
Do you mean, "As for all n, pCn is divisible by p iff p is prime?"
yes, the prime just stays in the numerator
Dr. Grimes- "I have a fool proof test for primes."
Me- "Fool proof you say? Hold my beer."
Never underestimate the power of a determined fool…
Can I aks you if this is prime?
Wow, very cool. It helps to look at Pascal's Triangle to see it
Wait a minute, it doesn't work for 7,423,811!
1373 × 5407 is the prime factorization, and therefore, the number you listed is not prime. Apologies if you've received this response already :)
حسين فرّاج Those aren’t primes, either; 341 and 561 are divisible by 11 (easily determined in both cases because the middle digit is the sum of
the .other two), and 1105 is obviously a multiple of 5
Also, sorry about the messed-up formatting; UA-cam’s app can’t seem to handle the Arabic text in your screen name properly.
@@HocineFerradj all the numbers you mentioned in your comment are composite my dear. Instead of finding mistakes in the algorithm of a renowned Indian mathematician you need to first make sure that you are yourself correct in your logic.
To add to the historical accuracy of my comments of 6 years ago the simple algebra of the AKS test was derived and proved by no other than that well known mathematician Leonhard Euler.
It is theorem 1 in his 'Theorems on the Divisors of Numbers' which is published as E134 in the Enestrom Index of the Euler Archives.
Give credit where credit is due!
Doesn't this generate as many terms (give or take) as there are numbers between 1 and p? If so doesn't it make sense to just do divisibility tests on all numbers from 2 to square root p?
Wait, if you wanted to test if 100 was prime, would you need to do that thing 100 times or something? If so, why don't you just do 100 divided be the first half of all the numbers before it? That would be quicker IMO.
Thanks! I just tweeted asking about this the other day :-)
this is very interesting test. one can now use Pascal's triangle to test prime numbers. Pascal's triangle gives coefficients of the polynomial as shown in the video. so all you have to do is to find numbers in Pascals triangle , which will be coefficients and if they are all divisible by p, then p is prime. is that right?
If you used Pascal's triangle here instead of generating a polynomial every time it may be faster. If all values in row (n+1) of the triangle besides the 1s at the ends are divisible by n, n is prime
Great illustration
Are composite numbers that pass certain prime number tests in any way speial or all in all interesting?
wsadhu composite numbers are just any number that has factors (so not prime). An example of a highly composite number would be 12 compared to 10
@@alandouglas2789 I think that wsadhu is referring to tests for primes that, unlike this test, can have false positives, and is asking whether numbers that pass those tests but are not in fact primes are in any way interesting. (A fairly broad question, admittedly, as a specific rest isn't mentioned.)
@@alandouglas2789 I know what composite numbers are. The question is, if there is anythong special in a composite number that passes a certain prime number test and what can it tell about the test.
Why involve the powers at all? All one needs is the binomial coefficients. Also, since I don't have the time to read all of the comments to determine if this is old news, I apologize in advance, but has anyone else noticed that when the number isn't prime, the remainders of the coefficients which aren't evenly divisible by that number share a common factor with that number? In other words, if the number is not prime, the coefficients which caused it to fail the prime test hands its factors over on a silver platter.
Here's another way you can test if P is prime
Cosine pi times a fraction where the numerator is (P - 1)! +1 and the denominator is just P . All of that gets squared at the end.
If prime=1
If composite=0
Simple Proof:
Use Binomial Theorem
Excluding the first and last term, every coefficient is of the form pCr are integers. Since p is prime no denominator of pCr will eliminate it (since they are products of smaller numbers). So all terms are 100% divisible.
What makes it so slow? Couldn't they just use pascal's triangle to determine the coefficients?
Calculating the whole of pascal's triangle is O(n^2) for the nth level that you complete and you would end up throwing out most of that work. I think that a single line is order O(n). I think you're looking for other information I don't have with the first question.
try generating the pascal's triangle till larger number of rows, like 10^6 or 10^7 rows, then you'll realize how slow and memory-abusing the process becomes. If it were me, I would never have gone with using pascal's triangle but instead would have used the (n choose r) formula.
On a computer, (which I assume they are using for larger calculations), Powers in them selves take a while to calculate. Pascal's triangle is also not the fastest thing you can compute, due to its recursive nature.
To me, it still seems like it would be faster to do the good-ol' test if a number is divisible by every number up to that number.
But how much time do you think it would take to calculate pascal's triangle up to the 2^(57,885,161) − 1th row (the largest known prime number). Pretty long, I dare venture :)
And it's certainly slower than just calculating the coefficients outright using factorials.
Meet Udeshi It would indeed be much faster to use that formula, but still that is simply a more effective way to find the numbers in any given row in pascal's triangle. I can't fathom how the polynomial method can be much slower than the other one, not to mention that it's much more reliable.
I will sleep easier tonight knowing that there is a fool-proof test for primes. I no longer feel like a fool.
Now do the Computerphile interview asking about the importance of this discover to the computer science community! Also, would be nice to see this theorem turned into a algorithm.
In Pascal's triangle, the GCD of all internal (neither first, neither last) terms of row n, n >= 2:
* equals n iff n is prime;
* equals prime p iff n = p^k, k >= 1;
* equals 1 iff n is not the power of a prime.
That's actually really cool
Could you guys make a video on the Collatz problem? Thanks for your awesome videos.
Seeing as the coefficients of binomial expansion line up with Pascal's triangle always, the does this mean that if all the numbers on the nth level of Pascal's triangle (but the ones) are divisible by n then n is prime.
Aprendi o método: 👏👏👏👏👏👏👏
If you take the length of this video, ignore the colon between the minutes and seconds digits and read it as one single three-digit number, "343", you get the cube of "7".
Thank you, I have discovered a whole new way to test for primes that is much faster and more accurate than any existing formula, I have also discovered a couple of formulas that predict prime numbers a lot more often than any existing one. Plus one formula that predicts twin primes and brings us closer to solving the twin prime conjecture. I can even go as far as saying that I have solved it and I am 100 percent certain that there is an infinite number of twin primes, I don't have the equipment to test it any further but did manage to test it to 114 digits. I have contacted several entities to get help on how to publish my work but none have answered my emails, not even you sir in the video.
I guess the world might just have to wait another 2000 years like they did before. I am very upset because I turn 40 in a few days, and you know what you get when you publish great work after the age of 40? A pad on the shoulder...
Sounds close to Gauss's Lemma in relation to ring theory and polynomials
Mind suitably blown. Love it!
So basically, if the row of the number in Pascal's Triangle is completely divisible by the number, it's prime. Genious.
I don't understand how this is breakthrough. I've always noticed that Pascal's triangle is only divisible by the row it's in when it's prime (1 7 21 35 35 21 7 1). Was that never proven before or was it the shortcut that's new?
+Nicholas Pipitone Exactly, just remove the 1s from the Pth row of the triangle. The only problem is that if you're testing a number such as 80207, you have to check if 80206 coefficients are divisible by 80207. Sounds like trial division up to the square root of the number is still faster.
@@coopergates9680 Seems like AKS works by proving you only have to check a few values of "a" for the whole polynomial to be correct. Still seems like a complicated proof!
The most underrated video on UA-cam
i found a prime tester, n is the number you are testing, it dose not work for numbers divisible by 3
it is 2n - (first digit of n + second digit of n) and if the first digit of the output is a Fibonacci then n is prime.
e.g
127*2 = 254 - 1+2 = 251 and i is a Fibonacci number, so 127 is prime
Can you explain why this works
Try this, i can't see the other replies:
en.wikipedia.org/wiki/AKS_primality_test#Concepts
This test should have been obvious since prime-number rows on Pascal's Triangle are ones whose elements are all divisible by their row number, and (x - 1)^p - (x^p - 1) is the same thing as just looking at the coefficients that are not 1 in the p'th row of the pascal's triangle
I guess the trick was proving it.
Vi Su how will it not hold for 341 if Pascal's triangle and the coeficents of those polynomials are always the same thing??
I definitely prefer the AKS test, greater accuracy with less double checking sounds like a winner to me. I don't see how AKS is slower since you have to double check so many numbers for the Fermat's test to catch all the sneaky, composites, liars and witnesses.
Very good explained
Well explained*
Why the fuck was this video not shown before? This is outrageously significant.
WAIT A SECOND!
The expansion of (x-1) ^y follows row y of Pascal's triangle. Which means that ever member of all prime rows of Pascal's triangle are divisible by the prime of the row. AND you can calculate the members in each row of Pascal's triangle with permutations and combinations. And this can be used for any number! So the rows numbers can be MASSIVE, but it is still quick.
Pascal you beautiful man!
Although, it makes you think why only primes behave in this way. Why the simple addition of numbers can produce primes and ONLY multiples of primes. The elegance of the prediction of primes leads me to believe that the subsequent formula would be beautifully simplistic.. Pascal's triangle is beautifully simplistic, and with so many patterns already....
Maybe the simple compound addition of 1's in the shape of a triangle holds the key to the prediction of primes. Or maybe, I'm a little insane.
Yet another great video! By the way, I saw matt on the discovery channel today, he was explaining all sorts of science behind some really viral videos's :p Really cool!
The way I test if a number is prime is I find the square root of the number I want to test and round to the nearest whole number (n) and try dividing the number by all the whole numbers from 2 to n. If it cannot divide by any of the numbers then the number is prime.
This is awesome!
So, is the idea to run numbers through Fermat's test, then all that pass, run them through the new test, so you don't have to run as many numbers through the slow process?
+JMan Nitpicking, but there were already two NON-probabilistic algorithms that were much faster, and we still use them in practice. AKS is polynomial, but the constants and exponents are quite large. So we knew we could quickly and correctly test primality, but the question was if it was in P. It was long suspected the problem was in P, but nobody had an actual method until AKS.
APR-CL is general, unconditional, deterministic, and sub-exponential. The exponent does not exceed AKS for any physically computable number. That is what I mean. We also had ECPP, which is general, unconditional, randomized, and polynomial. In practice it does indeed run in the expected time, which is faster than AKS.
I'm trying to make a distinction, because so many people confuse them, between asymptotically fast (e.g. polynomial) and fast in actual practice (which AKS fails miserably at). Lots of people also seem to think the only solutions for general inputs are probabilistic tests (e.g. randomized Miller-Rabin, but there are lots more), and AKS. There are perfectly usable deterministic tests, which we still use. We do not actually use AKS because it is very slow.
I know 1 isn't a prime, but doesn't this test technically work for 1? You end up with 0, but 0 is divisible by 1.
well 1 shares some properties of primes, and doesnt have some other properties of primes, so its not fully prime, so that's why we say it's prime. this is an example of a shared property
Basically, the right way to talk about this is not *really* "a 100% primality test", but instead a "100% *compositeness* test". Ultimately, 1 is not composite, and the union of the list of prime and composite numbers are exhaustive for all larger natural numbers. :3
Division by zero is illegal.
@Aidan DePeri OP stated "0 is divisible by 1", not the other way around
0/1=0; 1/0=UNDEF
Awesome!
To everyone raving about this test, I have to ask them about its practicality. You do realize that to test a number (let's call it n), you need to check all the coefficients in the nth row of Pascal's triangle. Okay, I suppose we can take advantage of the symmetry in the triangle and not bother to test half the coefficients, but that means if the number being testing is, say, around 10^50, then about 10^50/2 computations have to be executed. That does not sound like a fast calculation to me. It's more like one of those "end of the universe" calculations that our eminent professor insists is not the case with this test.
what do you think will happen to the RSA encryption if some day mathematicians will find a (relative) fast way to factorize huge numbers (specially huge numbers who's only factors are 2 huge primes)?
Can you make a video on the proof!? This can be conjectured from pascal's triangle
More Dr James Grime please