伦斯特拉椭圆曲线因式分解法或椭圆曲线因式分解方法(ECM)

简介：
ECM（椭圆曲线因式分解法）是由伦斯特拉提出的一种高效的整数分解算法，特别擅长找到大整数的较小因子。该方法利用了椭圆曲线上点的加法性质，在密码学和数学领域有着重要应用。 ECM被认为是一种专门用于寻找小因子的保理算法。它在处理不超过50至60位数的除法问题上表现最佳，因为其运行时间取决于最小因子p的大小，而非待分解整数n的整体规模。通常情况下，ECM被用来从包含大量因子的大数字中剔除较小的因子；如果剩余部分依然是复合数，则意味着它仅含有较大的因子，此时会采用通用技术进行进一步分解。迄今为止通过ECM找到的最大因子有83位十进制数字，并于2013年9月7日由R. Propper发现。增加测试曲线的数量可以提高发现因子的概率，但这种概率的增长并不与被检测数字的大小成正比关系。