Hello. Does anyone know any (non-pseudo) primality tests with complexity better than O(√n)? The thing is, I was reading about a simple one that has O(∛n) or O(∜n) complexity, but now I just can't find it! I remember that the core idea was checking some divisors (not up to square root) and then analyzing cases of prime decomposition. Thank you.
Miller–Rabin primality test is the fastest algorithm, but it is not deterministic. You need to run the test multiple times to reduce the failure probability.