Probabilistic Primality Testing

The aim of this talk is to give a strong probabilistic pseudoprimality test that recognises a maximal number of composite numbers as fast as possible. As a by-product, it is shown how to get ``free'' square-roots of certain elements of $\Z/p\Z$.