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:
“The question confronting the Church today is not any longer whether the man in the street can grasp a religious message, but how to employ the communications media so as to let him have the full impact of the Gospel message.”
—Pope John Paul II (b. 1920)
“As in political revolutions, so in paradigm choice—there is no standard higher than the assent of the relevant community. To discover how scientific revolutions are effected, we shall therefore have to examine not only the impact of nature and of logic, but also the techniques of persuasive argumentation effective within the quite special groups that constitute the community of scientists.”
—Thomas S. Kuhn (b. 1922)