椭圆曲线素数判定的原理是什么？
椭圆曲线素数判定的原理是什么？ 我正在写一个md文档，准备把所有实用素性测试算法都写一遍 无心人 发表于 2021-12-2 16:05我正在写一个md文档，准备把所有实用素性测试算法都写一遍
BPSW算法+随机的miller rabin足够了，别的算法基本都是浪费，素数判定除非有更快或者更确定的算法，否则没多大价值 本帖最后由 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. . 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 a “birthday paradox” second phase, and further
more technical refinements. In , 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 .
Phase one of ECM works as follow
这儿有介绍
来自链接
http://www.fermatsearch.org/links.html
页:
[1]