椭圆曲线素数判定的原理是什么？

nyy

椭圆曲线素数判定的原理是什么？

无心人

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

nyy

无心人 发表于 2021-12-2 16:05
我正在写一个md文档，准备把所有实用素性测试算法都写一遍

BPSW算法+随机的miller rabin足够了，别的算法基本都是浪费，素数判定除非有更快或者更确定的算法，否则没多大价值

nyy

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