主題
Search

橢圓曲線分解法


橢圓曲線分解法,縮寫為 ECM,有時也稱為 Lenstra 橢圓曲線方法,是一種分解演算法,它計算隨機橢圓曲線上一個點的大的倍數,模數為要分解的數 N。它往往比 Pollard rho 分解Pollard p-1 分解方法 更快。

Zimmermann 維護著一個使用 ECM 找到的最大因子的表格。截至 2009 年 1 月,使用 ECM 找到的最大素因子有 67 位十進位制數字。這個 10^(381)+1 的因子是由 B. Dodson 於 2006 年 8 月 24 日發現的 (Zimmermann)。


另請參閱

Atkin-Goldwasser-Kilian-Morain 證書, 橢圓曲線素性證明, 橢圓偽素數, 素因數分解, 素因數分解演算法

使用 探索

參考文獻

Alpern, D. "使用橢圓曲線方法的因式分解。" http://www.alpertron.com.ar/ECM.HTM.Atkin, A. O. L. 和 Morain, F. "為橢圓曲線因式分解法尋找合適的曲線。" Math. Comput. 60, 399-405, 1993.Brent, R. P. "使用橢圓曲線的一些整數因式分解演算法。" Austral. Comp. Sci. Comm. 8, 149-163, 1986.Brent, R. P. "整數因式分解的並行演算法。" 收錄於 數論與密碼學 (J. H. Loxton 編輯). New York: Cambridge University Press, pp. 26-37, 1990.Brillhart, J.; Lehmer, D. H.; Selfridge, J.; Wagstaff, S. S. Jr.; 和 Tuckerman, B. b-n+/-1, b=2, 3, 5, 6, 7, 10, 11, 12 高次冪的因式分解,修訂版。 Providence, RI: Amer. Math. Soc., p. lxxxiii, 1988.Eldershaw, C. 和 Brent, R. P. "在一些向量和平行計算機上大整數的因式分解。" Australian National University, Technical Report TR-CS-95-01. 1995 年 1 月。 http://cs.anu.edu.au/techreports/1995/TR-CS-95-01.html.Lenstra, A. K. 和 Lenstra, H. W. Jr. "數論演算法。" 收錄於 理論計算機科學手冊,A 卷:演算法與複雜性 (J. van Leeuwen 編輯). Amsterdam: Netherlands, Elsevier, pp. 673-715, 1990.Lenstra, H. W. Jr. "用橢圓曲線分解整數。" Ann. Math. 126, 649-673, 1987.Montgomery, P. L. "加速 Pollard 和橢圓曲線分解方法。" Math. Comput. 48, 243-264, 1987.Zimmermann, P. "ECMNET 專案。" http://www.loria.fr/~zimmerma/records/ecmnet.html.Zimmermann, P. "ECM 前 100 名錶格。" http://www.loria.fr/~zimmerma/records/top50.html.

在 中被引用

橢圓曲線分解法

請這樣引用

Weisstein, Eric W. "橢圓曲線分解法。" 來自 —— 資源。 https://mathworld.tw/EllipticCurveFactorizationMethod.html

主題分類