Continued Fractions, Quadratic Fields, and Factoring: Some Computational\n Aspects

2021/03/27 by Michele Elia, Elia, Michele
Computer Science · Mathematics · #11A51 #11A55 #Analytic Number Theory Research #Cellular Automata and Applications #FOS: Mathematics #Mathematics and Applications #Number Theory (math.NT) #Numerical Methods and Algorithms #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.2103.14861

openalex publication_date 2021/03/27 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28

Abstract

Legendre discovered that the continued fraction expansion of \√ N having\nodd period leads directly to an explicit representation of N as the sum of\ntwo squares. In this vein, it was recently observed that the continued fraction\nexpansion of \√ N having even period directly produces a factor of\ncomposite N. It is proved here that these apparently fortuitous occurrences\nallow us to propose and apply a variation of Shanks' infrastructural method\nwhich significantly reduces the asymptotic computational burden with respect to\ncurrently used factoring techniques.\n

Related

• Continued Fractions and Factoring
• On the period of the continued fraction for values of the square root of power sums
• Integer Factorization via Continued Fractions and Quadratic Forms
• A commentary on the continued fraction by which the illustrious La Grange has expressed the binomial powers
• A short history of some recent research on continued fractions in function fields