Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2508.08929 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
Sommario:
- 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)$.