Generating random factorisations of polynomial values

Dmitry Badziahin

paper

Generating random factorisations of polynomial values

arXiv:2508.08929

Abstract

We construct algorithms that efficiently generate random factorisations of values $P (n)$ as products of two integers, where $P \in Z [x]$ is a given quadratic or cubic monic polynomial. In other words, the algorithms produce random triples $(n, d_{1}, d_{2}) \in Z^{3}$ that solve the Diophantine equation $P (n) = d_{1} d_{2}$ . 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, d_{1}, d_{2})$ with the ratio $d_{1} / d_{2}$ arbitrarily close to any given positive real number. This proves that among all solutions $(n, d_{1}, d_{2})$ of $P (n) = d_{1} d_{2}$ the ratios $d_{1} / d_{2}$ are dense in $(0, + \infty)$ .

14 pages