I am currently analyzing the AKS algorithm and I saw that for practical purpose usually only probabilistic test are used due to faster runtime. I know that the probabilities in these test can be made so small such that it becomes irrelevant for any practical application. Nevertheless I am bothered by the fact that all test seem to have their error such that they might return a composite as a prime and was wondering if anybody knows about (or if they even exist) probabilistic test that might return a prime as a composite but we can be absolutely certain that the number is prime if prime is returned? I can't seem to finde anything of that sort.
Thank you in advance.