主題
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' 常數, 素性測試

使用 探索

參考文獻

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.

在 中被引用

橢圓曲線素性證明

引用為

Weisstein, Eric W. “橢圓曲線素性證明。” 來自 Web 資源。 https://mathworld.tw/EllipticCurvePrimalityProving.html

主題分類