ГлавнаяАрхивО вычислении группы классов идеалов мнимых мультиквадратичных полей

О вычислении группы классов идеалов мнимых мультиквадратичных полей | Прикладная дискретная математика. 2022. № 58. DOI: 10.17223/20710410/58/3

Расширены эксперименты Биассе - ван Вредендал (OBS, 2019, vol. 2) по вычислению группы классов идеалов с действительных мультиквадратичных полей на мнимые мультиквадратичные поля. Представлена адаптированная и оптимизированная для работы с мнимыми полями реализация алгоритма Биассе - ван Вредендал. Оптимизации включают в себя введение и использование явных формул для подъёма простых идеалов и замену вычислений эрмитовой нормальной формы на LLL-редукцию. Представлены примеры вычисления группы классов для мнимых мультквадратичных полей степени 64 и 128, недостижимые ранее.
  • Title О вычислении группы классов идеалов мнимых мультиквадратичных полей
  • Headline О вычислении группы классов идеалов мнимых мультиквадратичных полей
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 58
  • Date:
  • DOI 10.17223/20710410/58/3
Ключевые слова
мультквадратичное числовое поле, группа классов идеалов
Авторы
Ссылки
Buchmann J. and Paulus S. A one way function based on ideal arithmetic in number fields. LNCS, 1997, vol. 1294, pp. 385-394.
Biehll., Buchmann J., Hamdy S., and Meyer A. A signature scheme based on the intractability of computing roots. Des. Codes Cryptogr., 2002, vol. 25, pp. 223-236.
Meyer A., Neis S., and Pfahler T. First implementation of cryptographic protocols based on algebraic number fields. LNCS, 2001, vol. 2119, pp. 84-103.
Lyubashevsky V., Peikert C., and Regev O. On ideal lattices and learning with errors over rings. LNCS, 2010, vol. 6110, pp. 1-23.
Lyubashevsky V. and Micciancio D. Generalized compact knapsacks are collision resistant. LNCS, 2006, vol. 4052, pp. 144-155.
Bauch J., Bernstein D. J., de Valence H., et al. Short generators without quantum computers: the case of multiquadratics. Ann.Intern. Conf. on the Theory and Applications of Cryptographic Techniques, 2017, vol. 84, no. 291, pp. 27-59. Source code: https://multiquad.cr.yp.to/software.html.
Pellet-Mary A, Hanrot G., and Stehle D. Approx-SVP in ideal lattices with pre-processing. LNCS, 2019, vol. 11477, pp. 685-716.
Bernard O. and Roux-Langlois A. Twisted-PHS - Using the product formula to solve Approx-SVP in ideal lattices. LNCS, 2020, vol. 12492, pp. 349-380.
Buchmann J. A subexponential algorithm for the determination of class groups and regulators of algebraic number fields. Seminaire de Theorie des Nombres (Paris 1988/1989), Progr. Math., Birkhauser, Boston, 1990, no. 91, pp. 27-41.
Cohen H., Diaz Y Diaz F., and Olivier M. Subexponential algorithms for class group and unit computations. J. Symbolic Computation, 1997, vol. 24, pp. 433-441.
Biasse J.-F. An L(1/3) Algorithm for Discrete Logarithm Computation and Principality Testing in Certain Number Fields. arXiv preprint, 2012. https://arxiv.org/abs/1204.1292.
Biasse J.-F. and van Vredendaal C. Fast multiquadratic S-unit computation and application to the calculation of class groups. The Open Book Series, 2019, vol. 2, pp. 103-118. Source code: https://scarecryptow.org/publications/multiclass.html.
Lenstra A. K., Lenstra H. W., and Lovasz L. Factoring polynomials with rational coefficients. Math. Ann., 1982, vol. 261, pp. 515-534.
Bach E. Explicit bounds for primality testing and related problems. Mathematics of Computation, 1990, vol. 55, no. 191, pp. 355-380.
Grenie L. and Molteni G. Explicit bounds for primality testing and related problems. Mathematics of Computation, 2018, no. 313, pp. 2483-2511.
Cohen H. A Course in Computational Algebraic Number Theory. Berlin, Springer Verlag, 1993.
Bach E. Improved approximations for Euler products. Number Theory, CMS Conf. Proc., 1995, vol. 15, pp. 13-28.
Belabas K. and Friedman E.Computing the residue of the Dedekind zeta function. Mathematics of Computation, 2015, vol. 84, no. 291, pp. 357-369.
Fieker C., Hart W., Hofmann T., and Johansson F. Nemo/Hecke: computer algebra and number theory packages for the Julia programming language. Proc. ISSAC’17, 2017, pp. 157164. https://www.thofma.com/Hecke.jl/dev/.
Bezanson J., Edelman A., Karpinski S., and Shah V. B. Julia: A fresh approach to numerical computing. SIAM Review, 2017, vol. 59, no. 1, pp. 65-98.
Cohen H. Advanced Topics in Computational Number Theory. N.Y., Springer Science + Business Media, 2000.
The Sage Developers. SageMath, the Sage Mathematics Software System (Version 9.4). 2022, https://www.sagemath.org.
О вычислении группы классов идеалов мнимых мультиквадратичных полей | Прикладная дискретная математика. 2022. № 58. DOI: 10.17223/20710410/58/3
О вычислении группы классов идеалов мнимых мультиквадратичных полей | Прикладная дискретная математика. 2022. № 58. DOI: 10.17223/20710410/58/3