Вычисление порядка действия Фробениуса на группу ℓ-кручения - это часть алгоритма Схоофа - Элкиеса - Аткина (SEA) для вычисления числа точек на эллиптических кривых. Идея алгоритма Схоофа заключается в вычислении следа эндоморфизма Фробениуса по модулю простых чисел ℓ с последующим восстановлением его значения по китайской теореме об остатках. Улучшение Аткина состоит в вычислении порядка действия Фробениуса r на E[ℓ] и ограничении списка возможных следов t (mod ℓ) для перебора по формуле t2 = q (ζ + ζ-1)2 (mod ℓ), где ζ - примитивный корень из единицы степени r. В данной работе мы обобщаем формулу Аткина на случай абелева многообразия размерности g и выводим свойства распределения порядков для случая абелевых поверхностей над конечным полем размера q ≡ 1 (mod ℓ) с целью заменить на вероятностный алгоритм трудоёмкое вычисление модулярных многочленов, которое используется в алгоритме SEA для нахождения порядка.
Скачать электронную версию публикации
Загружен, раз: 108
- Title О распределении порядков действия Фробениуса на группу ℓ-кручения абелевых поверхностей
- Headline О распределении порядков действия Фробениуса на группу ℓ-кручения абелевых поверхностей
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 48
- Date:
- DOI 10.17223/20710410/48/3
Ключевые слова
абелевы поверхности, конечные поля, эндоморфизм Фробениуса, группа ℓ-кручения, abelian varieties, finite fields, Frobenius action, ℓ-torsionАвторы
Ссылки
Schoof R. Counting points on elliptic curves over finite fields. J. de Theorie des Nombres de Bordeaux, 1995, vol. 7, no. 1, pp. 219-254.
Cohen H., Frey G., Avanzi R., et al. Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman and Hall/CRC, 2005.
Silverman J. H. The Arithmetic of Elliptic Curves. N.Y., Springer Verlag, 2009, vol. 106.
Martindale C. Counting points on genus 2 curves over finite fields. Talk at GAGA Seminar in Utrecht, Netherlands, 2017.
Ballentine S., Guillevic A., Garcia E. L., et al. Isogenies for point counting on genus two hyperelliptic curves with maximal real multiplication. Algebraic Geometry for Coding Theory and Cryptography, Springer, 2017, pp. 63-94.
Gaudry P. and Schost E. Genus 2 point counting over prime fields. J. Symbolic Computation, 2012, vol. 47, no. 4, pp. 368-400.
Broker R. and Lauter K. Modular polynomials for genus 2. LMS J. Computation and Math., 2009, vol. 12, pp. 326-339.
Gaudry P. and Schost E. Modular equations for hyperelliptic curves. Mathematics of Computation, 2005, vol. 74, no. 249, pp. 429-454.
Pila J. Frobenius maps of abelian varieties and finding roots of unity in finite fields. Mathematics of Computation, 1990, vol. 55, no. 192, pp. 745-763.
Kolesnikov N. S. and Novoselov S. A. On the order of the frobenius endomorphism action on ℓ-torsion subgroup of abelian surfaces. Prikl. Diskr. Mat. Suppl., 2019, no. 12, pp. 11-12.
Tate J. Endomorphisms of abelian varieties over finite fields. Inventiones Mathematicae, 1966, vol. 2, no. 2, pp. 134-144.
Ruck H.-G. Abelian surfaces and jacobian varieties over finite fields. Compositio Mathematica, 1990, vol. 76, no. 3, pp. 351-366.
Bray J.N., Holt D.F., and Roney-Dougal C. M. The Maximal Subgroups of the Low Dimensional Finite Classical Groups. LMS Lecture Note Series, Cambridge University Press, 2013.
Hurt N. E. Many Rational Points: Coding Theory and Algebraic Geometry. Springer Science & Business Media, 2013, vol. 564.
Stong R. The average order of a matrix. J. Combinatorial Theory, Ser. A, 1993, vol. 64, no. 2, pp. 337-343.
Schmutz E. The order of a typical matrix with entries in a finite field. Israel J. Mathematics, 1995, vol. 91, no. 1-3, pp. 349-371.
Fulman J. Random matrix theory over finite fields. Bull. Amer. Math. Society, 2002, vol. 39, no. 1, pp.51-85.
Schmutz E. The expected order of a random unitary matrix. J. Group Theory, 2008, vol. 11, no. 4, pp.495-510.
Aivazidis S. and Sofos E. On the distribution of the density of maximal order elements in general linear groups. Ramanujan J., 2015, vol. 38, no. 1, pp. 35-59.
Srinivasan B. The characters of the finite symplectic group Sp(4, q). Trans. AMS, 1968, vol. 131, no. 2, pp. 488-525.
Diaconis P. and Erdos P. On the distribution of the greatest common divisor. A Festschrift for Herman Rubin, Institute of Mathematical Statistics, 2004, pp. 56-61.
Achter J. and Williams C. Local heuristics and an exact formula for abelian surfaces over finite fields. Canadian Math. Bull., 2015, vol. 58, no. 4, pp. 673-691.
SageMath, the Sage Mathematics Software System (Version 8.9), 2019. https://www. sagemath.org.
Joux A. and Lercier R. “Chinese & Match”, an alternative to Atkin’s “Match and Sort” method used in the SEA algorithm. Mathematics of Computation, 2001, vol. 70, no. 234, pp. 827-836.
О распределении порядков действия Фробениуса на группу ℓ-кручения абелевых поверхностей | Прикладная дискретная математика. 2020. № 48. DOI: 10.17223/20710410/48/3