Tag: primality-testing

AKS settled a longstanding complexity question by giving the first unconditional deterministic polynomial-time algorithm for deciding whether an integer is prime.

Randomized algorithms made probability part of the algorithm itself. Work by Michael Rabin and by Robert Solovay with Volker Strassen helped show in the 1970s that controlled error or randomized choices could buy dramatic computational savings.