best way to do "fermat" primalty checks

[Emanuele Laface]

Dear all...
the problem of primality check is not very simple, today the fastest
algorithms to check primality are probabilistic.
So you can know is a number is prime or not with a little error, and
if you try the same check many times your probability to have a true
prime number is near 1.
The best of this algorithms is already implemented into GMP library,
so it's enough to read the manual and to use it.
But if you need something of special I can say that the best algorithm
to check primality is the Agrawal, Kayal, Saxena (or AKS) test.
It is based on little fermat theorem and is polinomial in the number of ciphers.
The main problem of this algorithm is that use the polinomial
division, and I don't know a fast way to implement them. So the
algorithm is theoretically polinomial but all implementation that I
saw (I also wrote one by myself) are very slow respect to
probabilistic algorithms.

Regards
Emanuele