账号 自动登录 找回密码 密码 欢迎注册
 搜索

# [求助] 椭圆曲线素数判定的原理是什么？

### 马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

×

 我正在写一个md文档，准备把所有实用素性测试算法都写一遍

楼主| 发表于 2021-12-2 17:14:41 | 显示全部楼层
 无心人 发表于 2021-12-2 16:05 我正在写一个md文档，准备把所有实用素性测试算法都写一遍 BPSW算法+随机的miller rabin足够了，别的算法基本都是浪费，素数判定除非有更快或者更确定的算法，否则没多大价值

### 点评

BPSW其实是Lucas测试加Miller-Rabin测试的，但是两者都存在伪素数，而且比例极高，没发现通过两个测试的伪素数，并不代表不存在。  发表于 2021-12-6 08:22

楼主| 发表于 2023-8-16 13:19:28 | 显示全部楼层
 本帖最后由 nyy 于 2023-8-16 13:21 编辑 https://members.loria.fr/PZimmermann/papers/ecm-entry.pdf THE ELLIPTIC CURVE METHOD PAUL ZIMMERMANN The Elliptic Curve Method (ECM for short) was invented in 1985 by H. W. Lenstra, Jr. [5]. It is suited to find small — say 9 to 30 digits — prime factors of large numbers. Among the different factorization algorithms whose complexity mainly depends on the size of the factor searched for (trial division, Pollard rho, Pollard p − 1, Williams p + 1), it is asymptotically the best method known. ECM can be viewed as a generalization of Pollard’s p − 1 method, just like ECPP generalizes the n − 1 primality test. ECM relies on Hasse’s theorem: if p is prime, then an elliptic curve over Z/pZ has group order p + 1 − t with |t| ≤ 2 √p, where t depends on the curve. If p + 1 − t is a smooth number, then ECM will — most probably — succeed and reveal the unknown factor p. Since 1985, many improvements have been proposed to ECM. Lenstra’s original algorithm had no second phase. Brent proposes in [2] a “birthday paradox” second phase, and further more technical refinements. In [7], Montgomery presents different variants of phase two of ECM and Pollard p − 1, and introduces a parameterization with homogeneous coordinates, which avoids inversions modulo n, with only 6 and 5 modular multiplications per addition and duplication on E, respectively. It is also possible to choose elliptic curves with a group order divisible by 12 or 16 [7, 8, 1]. Phase one of ECM works as follow 这儿有介绍 来自链接 http://www.fermatsearch.org/links.html

 您需要登录后才可以回帖 登录 | 欢迎注册 本版积分规则 回帖并转播 回帖后跳转到最后一页

GMT+8, 2023-11-30 06:30 , Processed in 0.074861 second(s), 21 queries .