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.

For relatively small $$$n$$$, you can use a deterministic version of the Miller-Rabin test, which is the fastest. From the Wikipedia page:

if n < 3,317,044,064,679,887,385,961,981, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, and 41.

This should be enough for all practical purposes, and it has time complexity $$$O(k*log^3(n))$$$, where $$$k$$$ is the number of primes tested, 13 in this case.

Additionally, there is the Pollard-Rho algorithm, which works in $$$O(n^{\frac{1}{4}})$$$ on average.