Impact of PRIMES in P
Because primality testing can now be done deterministically in polynomial time using the AKS primality test, a prime number could itself be considered a certificate of its own primality. This test runs in Õ((log n)6) time. In practice this method of verification is more expensive than the verification of Pratt certificates, but does not require any computation to determine the certificate itself.
Read more about this topic: Primality Certificate
Famous quotes containing the words impact of and/or impact:
“Conquest is the missionary of valour, and the hard impact of military virtues beats meanness out of the world.”
—Walter Bagehot (1826–1877)
“Too many existing classrooms for young children have this overriding goal: To get the children ready for first grade. This goal is unworthy. It is hurtful. This goal has had the most distorting impact on five-year-olds. It causes kindergartens to be merely the handmaidens of first grade.... Kindergarten teachers cannot look at their own children and plan for their present needs as five-year-olds.”
—James L. Hymes, Jr. (20th century)