2025/08/12 by Dzmitry Badziahin, Badziahin, Dmitry
Computer Science · Mathematics · #11D99 #11T71 #11Y05 #94A60 #Algebraic Geometry and Number Theory #Analytic Number Theory Research #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2508.08929
openalex publication_date 2025/08/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We construct algorithms that efficiently generate random factorisations of values P(n) as products of two integers, where P∈ℤ[x] is a given quadratic or cubic monic polynomial. In other words, the algorithms produce random triples (n,d1,d2)∈ℤ3 that solve the Diophantine equation P(n) = d1d2. In the case where P is cubic, such an algorithm allows the construction of an RSA key of k bits that can be described using about k/3 bits of information. We also show how to construct a solution (n,d1,d2) with the ratio d1/d2 arbitrarily close to any given positive real number. This proves that among all solutions (n,d1,d2) of P(n) = d1d2 the ratios d1/d2 are dense in (0,+∞).