Anonymous user
Talk:AKS test for primes: Difference between revisions
→This isn't AKS
Line 40:
:::Brent's implementation in the 2010 presentation I referenced includes Lenstra and at least one of Bernstein's improvements (it looks like this is not the 2006 k=4 randomized algorithm nor the additional improvements Bernstein's 2002 paper mentions, but just his first ''s/r'' reduction plus Lenstra's improvement), and still gets quite long times. Bornemann's 2002 Pari implementation uses the Lentra, Voloch, and Bernstein improvements, and is quite small and runs much faster than many others, but is still pretty far off APR-CL / ECPP. Going to the best "AKS-class" algorithm plus basic improvements would seem like it could be competitive. I don't think those fastest versions are deterministic however (unlikely to matter in practice).
::: [[User:Danaj|Danaj]] ([[User talk:Danaj|talk]]) 18:10, 21 February 2014 (UTC)
:::: I agree with you on both of your complaints. I also have not seen implementations of the advanced versions (which, as you say, are not deterministic). - [[User:CRGreathouse|CRGreathouse]] ([[User talk:CRGreathouse|talk]]) 15:57, 25 February 2014 (UTC)
| |||