The complexity of class polynomial computation via floating point approximations
Andreas Enge (INRIA Futurs, Lix)
我们分析了计算类多项式的复杂性,这是椭圆曲线CM结构的重要成分,通过复杂的浮点近似其根源。 算法的核心是在几个参数中评估模块化函数。 最快的方法使用Dupont设计的技术,通过牛顿迭代评估涉及算术几何均值的表达式的模块化函数。 它运行在时间 O (|D| log^5 |D| loglog |D|) = O (|D|^1 + ε) = O (h^2 + ε)对于任何 ε > 0,其中 D 是 CM 判别器,h 是类多项式的程度。 另一种快速算法使用符号计算已知的多点评估技术;其渐近复杂度因日志 |D| 的因子而更糟。 高达对数因素,此运行时间与构造多项式的大小相匹配。 该估计还依赖于一个新的结果,即列举一个假象-二次顺序的类群的复杂性,以及严格证明的类多项式高度的上限。
We analyse the complexity of computing class polynomials, that are an important ingredient for CM constructions of elliptic curves, via complex floating point approximations of their roots. The heart of the algorithm is the evaluation of modular functions in several arguments. The fastest one of the presented approaches uses a technique devised by Dupont to evaluate modular functions by Newton iterations on an expression involving the arithmetic-geometric mean. It runs in time O (|D| log^5 |D| l...