3 ms·
Because it grows exponentially. ( And it is interesting ) In reality you will use a O( (log n)^6 ) algorithm.
by readerrrr 12y ago
Because it grows exponentially. ( And it is interesting )
In reality you will use a O( (log n)^6 ) algorithm.
- schoen 12y agoI think n² grows quadratically rather than exponentially.
- readerrrr 12y ago::blush::
- pbsd 12y agoNobody in their right mind uses AKS for primality testing. You use Miller-Rabin with an appropriate constant number of iterations, with complexity (log n)^(2 + o(1)). Or if you want provability, you use some fast variant of ECPP with (log n)^(4 + o(1)) complexity.