I thought primality proving was O~(n^6) unconditionally (using AKS) and O~(n^4) conditional on GRH (using deterministic Miller-Rabin). (Where, more precisely, the ~ is hiding a 'log n log log n'.)
Sent: Monday, February 19, 2018 at 9:50 PM From: "Hilarie Orman" <ho@alum.mit.edu> To: math-fun@mailman.xmission.com Subject: Re: [math-fun] xkcd CVE list today
I imagine Hilarie is referring to the (commonplace, albeit incorrect) use of 'factor primes' to mean 'factor integers into primes'.
And it is such a common error, even among those who are familiar with the principles, that I do not believe it was deliberate. However, it would be fun to know, and even more fun if it resulted in an errata.
Factoring a prime is O(1).
Proving a prime is O~(n^3).
Factoring an integer is O(e^(64/9 * log n * (loglog n)^2)^(1/3)).
Hilarie
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun