Is there a probabilistic prime test with time complexity $log^p (p\lt 1)$?

Question

My question is: Is there a (possibly probabilistic) prime test with sub-logarithmic runtime complexity? Is it possible to construct one?

I have found the following complexities for the most common tests.

• fermat test has O(k*log2n *log log n * log log log n)
• elliptic curve tests with O($log^6$)
• cyclotomy test with O($log^{(c * log log log)}$)
• Miller-Rabin has O($log^4$)
• AKS has O($log^{12}$) improved to O($log^{7.5}$) and then to O($log^6$)

thank you.

Answer 1

For generic integers, it's not even possible to test whether it's a multiple of $3$ in sub-logarithmic time. (If you've given the base-$10$ or base-$2$ digits of the integer $p$, for example, you need to examine every single digit to answer the question, and there are $\asymp \log p$ digits.) So the answer is definitely no.