> One algorithm that results in a polynomially verifiable witness is: > > Almost All Primes Can be Quickly Certified > http://theory.lcs.mit.edu/~cis/pubs/shafi/1986-stoc-gk.pdf
That's a very old algorithm. It was an intersting result at the time (1986) because it is a primality proving algorithm that is not based on any hypothesis and runs in *expected polynomial time* on almost all inputs (note the *expected*). It uses elliptic curves. However, the algorithm is not efficient in practice, and we have better theoretical results today (Agrawal-Kayal-Saxena that is a true primality test that works in polynomial time on all inputs. Note that such a deterministic polynomial-time primality testing algorithm implicitly provides a trivial certificate of primality, which simply consists of the prime number itself). Goldwasser and Kilian's result was extended by ADleman and Huang, later Atkin developed a simialr algorithm known as the Elliptic Curves for Primality Proving (ECPP), which I also referred to in my initial post. Morain worked on implementing Atkin's algorithm. This is efficient. Morain has a web page with lot's of info and nice working code: http://www.lix.polytechnique.fr/~morain/Prgms/ecpp.english.html The advantage of Maurer's construction, however, is that it is much simpler to code. --Anton --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
