Integer Factorization via Continued Fractions and Quadratic Forms
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916573561749504 |
|---|---|
| author | Murru, Nadir Salvatori, Giulia |
| author_facet | Murru, Nadir Salvatori, Giulia |
| contents | We propose a novel factorization algorithm that leverages the theory underlying the SQUFOF method, including reduced quadratic forms, infrastructural distance, and Gauss composition. We also present an analysis of our method, which has a computational complexity of $O \left( \exp \left( \frac{3}{\sqrt{8}} \sqrt{\ln N \ln \ln N} \right) \right)$, making it more efficient than the classical SQUFOF and CFRAC algorithms. Additionally, our algorithm is polynomial-time, provided knowledge of a (not too large) multiple of the regulator of $\mathbb{Q}(\sqrt{N})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_03486 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Integer Factorization via Continued Fractions and Quadratic Forms Murru, Nadir Salvatori, Giulia Number Theory 11A51, 11Y05 We propose a novel factorization algorithm that leverages the theory underlying the SQUFOF method, including reduced quadratic forms, infrastructural distance, and Gauss composition. We also present an analysis of our method, which has a computational complexity of $O \left( \exp \left( \frac{3}{\sqrt{8}} \sqrt{\ln N \ln \ln N} \right) \right)$, making it more efficient than the classical SQUFOF and CFRAC algorithms. Additionally, our algorithm is polynomial-time, provided knowledge of a (not too large) multiple of the regulator of $\mathbb{Q}(\sqrt{N})$. |
| title | Integer Factorization via Continued Fractions and Quadratic Forms |
| topic | Number Theory 11A51, 11Y05 |
| url | https://arxiv.org/abs/2409.03486 |