The factorization problem is typical for a wide range of mathematical problems. The solution of many mathematical problems is due to the fact that the result of the decomposition of numbers is known in advance.
This work is devoted to the study of factorization problems using elliptic curves. The possibility of using structures such as elliptic curves for the purpose of factorization has given a new impetus to the search for a solution to this problem. The article discusses the main problems of the elliptic curve method, which is based on the construction of a pseudocurve, and possible ways to optimize it. The relations between the number of generated curves and the necessary boundary of the basic elliptic curve method are investigated. The study of this problem was carried out using a software implementation of the method based on the described algorithm for numbers whose divisors do not exceed five decimal places. The results of this study are presented for various cases of the initial limit. The results obtained indicate the dependence of the time spent, the final boundary during the factorization process and the number of curves used during factorization on the number of curves after which the boundary of the elliptic curve method increases. As a result of the analysis of this method, a study was conducted on the number of cases of obtaining divisors of a composite number using a curve discriminant.
U.K. TURUSBEKOVA
PhD, Acting Associate Professor, Institution «Esil University», Astana, Kazakhstan E-mail: umut.t@mail.ru https://orcid.org/0000-0002-0591-2143
G.T. AZIEVA
Master's degree, Senior Lecturer, Institution «Esil University», Astana, Kazakhstan, E-mail: gulmira_azieva@mail.ru, https://orcid.org/0000-0002-7329-6768
- Pomerance, C. B. Smooth numbers and the quadratic sieve /C. B. Pomerance // Cambridge University Press, New York: Algorithmic Number Theory MSRI Publications, 2008. – V. 44.-P.1‒14.
- Чернов, В. М., Чичева, М. А. Алгебро-арифметические методы синтеза быстрых алгоритмов дискретных ортогональных преобразований/ В. М. Чернов, М. А. Чичева. - Самара: Изд-во СГАУ, 2010. – 102 с.
- Турусбекова У.К., Муратбеков М.М., Алтынбек С.А., Ахатова Ж.Е. Исследование свойств структур рекурсивных циклов первообразных корней // Вестник КазНПУ им. Абая, серия «Физико - математические науки», 2023. - №83(3). С.59-66. doi:
- https://doi.org/10.51889/2959-5894.2023.83.3.007.
- Complexity Zoo., Wayback Machine Class SUBEXP: Deterministic SubexponentialTime,2008. https://complexityzoo.uwaterloo.ca/Complexity_Zoo:S#subexp.
- Regev, O. A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space, 2004. https://arxiv.org/abs/quant-ph/0406151.
- Crandall, R. E., Pomerance, C. B. Prime numbers: A Computational Perspective/ R. E. Crandall, C. B. Pomerance // Springer-Verlag, New York, 2001.- P. 293‒420. DOI: https://doi.org/10.1007/978-1-4684-9316-0
- Lenstra, H. W. Factoting integerswith elliptic curves/ H. W. Lenstra // Annual of Mathematics, New-Jersey, 1987.- V. 126.- P. 649‒673. DOI: https://doi.org/10.2307/1971363
- Ишмухаметов, Ш.Т. Методы факторизации натуральных чисел/Ш.Т. Ишмухаметов-Казань: Казанский университет, 2011. -190 с.
- Ефимов, С.С., Макаренко, А.В., Пыхтеев, А.В. Параллельная реализация и сравнительный анализ алгоритмов факторизации в системах с распределённой памятью/ С.С. Ефимов, А.В. Макаренко, А.В. Пыхтеев//Омский государственный университет им. Ф.М. Достоевского, Математические структуры и моделирование, 2012. - №26.- С.94-109.