I just happened to hear about a prime number test which works 100% of the cases in an university lesson about cryptography.
It should be something like:
if $p$ divides every coefficient of $(x-1)^p - (x^p -1)$ then $p$ is a prime
My question is: why can't we use it? does it take too long to test? I would really appreciate some help on this subject, even just with a link for a paper about it, since I don't recall the name and I couldn't find useful stuffs on web yet. Thank you :)
This test, in combination with the words "fool proof" indicate that it almost certainly came from the numberphile video about the AKS test. The method you show is presented, called the AKS test (which it isn't), is claimed to be very fast (which it isn't), and then implies that we had no other way of figuring this out before -- that this was a revolution in practical use (which it isn't). Later in the video he mentions offhand that, well, there's a little fiddly other stuff that makes it a little faster. Which is to say, all of AKS.
I believe this method was first pointed out in ~1670 by Leibniz, according to a few sources (e.g. "Primality Testing and Integer Factorization in Public-Key Cryptography" by Yan, page 130). It's exponential time and much less efficient than just doing trial division to $\sqrt n$. It is stated on page 2 of the AKS paper as Lemma 2.1, which they immediately point out takes too much time. The rest of the paper finds clever ways to reduce the work done.
Wikipedia: AKS primality test
Primes is in P - the paper by Agrawal, Kayal, and Saxena.
"Why can't we use it?" We can, just like we can use Wilson's theorem or trial division. They work. They're just not computationally practical once the numbers get large (remembering that "large" is very subjective -- whatever you think of as a "large number" is someone else's "small number").
"Does it take too long to test?" Yes. We have much faster methods.
A brief further aside. Let's say you do everything mentioned in the paper. You have the real AKS. This is a theoretical breakthrough. A very simple method that shows what people long believed but had eluded proof: primality testing is deterministic polynomial time without any conjectures. We had deterministic polynomial time assuming the ERH. We had randomized polynomial time with no conjectures. We had deterministic almost-but-not-quite polynomial time with no conjectures. AKS lets us now say during discussions, "...and since primality testing is deterministic polynomial time, the whole algorithm is therefore ..."
The gotcha is that computationally even the proper AKS is still much slower than methods we were already using. APR-CL and ECPP are the typical methods used in practice. They are "fool proof" if you want to use that term. They are many orders of magnitude faster. There is also probable prime testing, such as BPSW or random-base Miller-Rabin, which is much faster yet, albeit with small chances of being wrong (both have deterministic methods for 64-bit inputs, so are "fool proof" for that size).