Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.08929 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915442238423040 |
|---|---|
| author | Badziahin, Dmitry |
| author_facet | Badziahin, Dmitry |
| contents | 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)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_08929 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Generating random factorisations of polynomial values Badziahin, Dmitry Number Theory 11Y05, 11T71, 11D99, 94A60 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)$. |
| title | Generating random factorisations of polynomial values |
| topic | Number Theory 11Y05, 11T71, 11D99, 94A60 |
| url | https://arxiv.org/abs/2508.08929 |