Big Oh of LL test?
 

Just curious to find out.

The new primality test postulates that they can get it down to a cubic polynomial and I'm curious if that might beat out the LL-primality test.

O(n^2 log n)

where n is the number of bits in the Mersenne number.

You mean the bits of p or 2^p-1?

Bits of 2^p-1. In other words, O(p^2 log p)