主题
Search

椭圆曲线素性证明

椭圆曲线素性证明，缩写为 ECPP，是一类算法，它使用椭圆曲线理论的复杂结果来提供素性证书。Atkin 和 Morain (1990, 1993) 给出了详细的描述和参考文献列表。

Adleman 和 Huang (1987) 设计了一种使用亏格为 2 的超椭圆曲线的独立算法。

ECPP 是已知最快的通用素性测试算法。ECPP 的运行时间为 O((lnN)^4)。截至 2004 年，程序PRIMO可以使用这种技术在 1 GHz 处理器上大约 2000 小时的计算（或近三个月的不间断计算）中验证一个 4769 位数的素数。截至 2009 年，使用此技术验证的最大的素数是第 11 个 Mills 素数 (http://primes.utm.edu/primes/page.php?id=77907)

(((((((((2^3+3)^3+30)^3+6)^3+80)^3+12)^3+450)^3+894)^3+3636)^3+70756)^3+97220,

它有 20562 位十进制数字。该证明是通过分布式计算执行的，该计算始于 2005 年 9 月，结束于 2006 年 6 月，需要累积 CPU 时间，相当于 2.39 GHz 运行 2219 天（略多于 6 年）。

2021 年 3 月，P. Underwood 使用椭圆曲线素性证明证明了单位重复数素数 R_(49081) (https://primes.utm.edu/primes/page.php?id=133761) 是素数。认证在配备 64 核的 AMD 3990x 计算机上花费了 20 个月，验证花费了大约 13 个小时 (Underwood 2022)。

另请参阅

Atkin-Goldwasser-Kilian-Morain 证书, 椭圆曲线分解法, 椭圆伪素数, Mills' 常数, 素性测试

使用 Wolfram|Alpha 探索

参考文献

Adleman, L. M. and Huang, M. A. "Recognizing Primes in Random Polynomial Time." In Proc. 19th STOC, New York City, May 25-27, 1986. New York: ACM Press, pp. 462-469, 1987.Alpern, D. "Factorization Using the Elliptic Curve Method." http://www.alpertron.com.ar/ECM.HTM.Atkin, A. O. L. Lecture notes of a conference, Boulder, CO, Aug. 1986.Atkin, A. O. L. and Morain, F. "Elliptic Curves and Primality Proving." Res. Rep. 1256, INRIA, June 1990.Atkin, A. O. L. and Morain, F. "Elliptic Curves and Primality Proving." Math. Comput. 61, 29-68, 1993.Bosma, W. "Primality Testing Using Elliptic Curves." Techn. Rep. 85-12, Math. Inst., Univ. Amsterdam, 1985.Chudnovsky, D. V. and Chudnovsky, G. V. "Sequences of Numbers Generated by Addition in Formal Groups and New Primality and Factorization Tests." Res. Rep. RC 11262, IBM, Yorktown Heights, NY, 1985.Cohen, H. Cryptographie, factorisation et primalité: l'utilisation des courbes elliptiques. Paris: C. R. J. Soc. Math. France, Jan. 1987.Kaltofen, E.; Valente, R.; and Yui, N. "An Improved Las Vegas Primality Test." Res. Rep. 89-12, Rensselaer Polytechnic Inst., Troy, NY, May 1989.Martin, M. "PRIMO--Primality Proving." http://www.ellipsa.net.Martin, M. "20 Greatest Candidates Verified with Primo." http://www.ellipsa.net/primo/top20.html.Underwood, P. "R49081 is Prime!" Mar. 21, 2022. https://mersenneforum.org/showpost.php?p=602219&postcount=35.

在 Wolfram|Alpha 中被引用

椭圆曲线素性证明

引用为

Weisstein, Eric W. “椭圆曲线素性证明。” 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/EllipticCurvePrimalityProving.html

主题分类