Improvement of Integer Factorization with Elliptic Curve and Complex Multiplication Method

In 2019, Y.Aikawa, K.Nuida and M.Shirase proposed a variant of Elliptic Curve Method combined with Complex Multiplication method that can factor integers with prime factors of specific type. The method found a nontrivial factor of N by computing the resultant of two polynomial that have a common root in F_p. It used Hilbert polynomial H_-D associated to the discriminant D then specified a root j_0 in F_p. In order to find another polynomial with root j_0, they construct an elliptic curve over function ring and extended the coefficient ring to find a rational point. In this work, we provide an improvement which can find rational point in the basic polynomial ring based on N and an algorithm which combines the computation of different discriminant D. Finally this work also makes numerical experiments evaluation left by the previous work.

In 2019, Y.Aikawa, K.Nuida and M.Shirase proposed a variant of Elliptic Curve Method combined with Complex Multiplication method that can factor integers with prime factors of specific type. The method found a nontrivial factor of N by computing the resultant of two polynomial that have a common root in F_p. It used Hilbert polynomial H_-D associated to the discriminant D then specified a root j_0 in F_p. In order to find another polynomial with root j_0, they construct an elliptic curve over function ring and extended the coefficient ring to find a rational point. In this work, we provide an improvement which can find rational point in the basic polynomial ring based on N and an algorithm which combines the computation of different discriminant D. Finally this work also makes numerical experiments evaluation left by the previous work.