2025/03/02 by Jacek Pomykała, Pomykała, Jacek, Mariusz Jurkiewicz +1
Computer Science · #Cryptography and Data Security #Cryptography and Residue Arithmetic #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2503.00950
openalex publication_date 2025/03/02 · openalex created_date 2025/10/12 · openalex updated_date 2026/08/03
An efficient integer factorization algorithm would reduce the security of all variants of the RSA cryptographic scheme to zero. Despite the passage of years, no method for efficiently factoring large semiprime numbers in a classical computational model has been discovered. In this paper, we demonstrate how a natural extension of the generalized approach to smoothness, combined with the separation of 2-adic point orders, leads us to propose a factoring algorithm that finds (conjecturally) the prime decomposition N = pq in subexponential time L(√ 2+o(1), min(p,q)). This approach motivated by the papers \citeLen, \citeMMV and \citePoZo is based on a more careful investigation of pairs (E,Q), where Q is a point on an elliptic curve E over \Z N. Specifically, in contrast to the familiar condition that the largest prime divisor P+(\ord Qp) of the reduced order \ord Qp does not divide #E(\Fq) we focus on the relation between P+(\ord Qr) and the smallest prime number lmin(E,Q) separating the orders \ord Qp and \ord Qq. We focus on the \calE2 family of even order elliptic curves over \ZN since then the condition lmin(E,Q)≤ 2 holds true for large fraction of points (x,y)∈ E(\ZN). Moreover if we know the pair (E,Q) such that P+(\ord Qr)≤ t