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.