Scholarlink

<p>The Elliptic Curve Method (ECM) is an efficient integer factorization algorithm for identifying medium-sized prime factors of large integers. Elliptic Divisibility Sequences (EDSs) are a class of non-linear divisibility sequences associated with elliptic curves, which can be efficiently computed when evaluated successively. This paper introduces a new implementation of stage 2 in ECM using EDSs. The main idea is to use the recursive formulas of EDSs to replace the group operations on elliptic curve points. We demonstrate that for parameter <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(e=1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>e</mi> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> (e.g. degree-<i>e</i> Dickson polynomial), our variant achieves a <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(10.09\%\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>10.09</mn> <mo>%</mo> </mrow> </math></EquationSource> </InlineEquation> speedup factor in Stage 2 compared to the ECM using Edwards curves.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Accelerating Stage 2 in ECM Using Elliptic Divisibility Sequences

  • 期刊论文

  • 发表日期：

    2026年6月18日

查看全文
  • Ziwen Liao,
  • Fangguo Zhang

摘要

The Elliptic Curve Method (ECM) is an efficient integer factorization algorithm for identifying medium-sized prime factors of large integers. Elliptic Divisibility Sequences (EDSs) are a class of non-linear divisibility sequences associated with elliptic curves, which can be efficiently computed when evaluated successively. This paper introduces a new implementation of stage 2 in ECM using EDSs. The main idea is to use the recursive formulas of EDSs to replace the group operations on elliptic curve points. We demonstrate that for parameter \(e=1\) e = 1 (e.g. degree-e Dickson polynomial), our variant achieves a \(10.09\%\) 10.09 % speedup factor in Stage 2 compared to the ECM using Edwards curves.