1.Previous
3.Next

** In 1976, G. Miller showed that the Miller-Rabin test is guaranteed to run in polynomial time. In 2002, Manindra Agrawal, Neeraj Kayal and Nitin Saxena proved unconditionally that the AKS primality test is guaranteed to run in polynomial time.
** The Shanks-Tonelli algorithm is guaranteed to run in polynomial time.
** The Ivanyos-Karpinski-Saxena deterministic algorithm for factoring polynomials

1.Previous
3.Next