Generating random factorisations of polynomial values
Preprint
Abstract
We construct algorithms that efficiently generate random factorisations of values $P(n)$ as products of two integers, where $P\in\mathbb{Z}[x]$ is a given quadratic or cubic monic polynomial. In other words, the algorithms produce random triples $(n,d_1,d_2)\in\mathbb{Z}^3$ that solve the Diophantine equation $P(n) = d_1d_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_1d_2$ the ratios $d_1/d_2$ are dense in $(0,+\infty)$.
Keywords
All Related Versions
This publication has 3 references indexed in Scilit:
- On RSA moduli with half of the bits prescribedJournal of Number Theory, 2013
- On RSA moduli with almost half of the bits prescribedDiscrete Applied Mathematics, 2008
- Generating RSA Moduli with a Predetermined Portion1998