Friday, July 01, 2005
Primality Proving 4.3: A polynomial-time algorithm
Primality Proving 4.3: A polynomial-time algorithm
"As we mentioned before, many of the primality proving methods are conjectured to be polynomial-time. For example, Miller's test is polynomial if ERH is true (and Rabin gave a version of this test that was unconditionally randomized polynomial-time [Rabin80]). Adleman and Hang [AH1992] modified the Goldwasser-Killian algorithm [GK86] to produce a randomized polynomial time algorithm that always produced a certificate of primality... So it is not surprising that there exists a polynomial-time algorithm for proving primality. But what is surprising is that in 2002 Agrawal, Kayal and Saxena [AKS2002] found a relatively simple deterministic algorithm which relies on no unproved assumptions. We present this algorithm below then briefly refer to a related algorithm of Bernstein."
"As we mentioned before, many of the primality proving methods are conjectured to be polynomial-time. For example, Miller's test is polynomial if ERH is true (and Rabin gave a version of this test that was unconditionally randomized polynomial-time [Rabin80]). Adleman and Hang [AH1992] modified the Goldwasser-Killian algorithm [GK86] to produce a randomized polynomial time algorithm that always produced a certificate of primality... So it is not surprising that there exists a polynomial-time algorithm for proving primality. But what is surprising is that in 2002 Agrawal, Kayal and Saxena [AKS2002] found a relatively simple deterministic algorithm which relies on no unproved assumptions. We present this algorithm below then briefly refer to a related algorithm of Bernstein."
0 Comments:
