Continued fractions and factoring

MaRDI QIDQ5149076zbMATH OpenFDO

Authors

Publication date 6 February 2021

Full work available at URL https://arxiv.org/abs/1905.10704, http://www.seminariomatematico.polito.it/rendiconti/78-1/Elia.pdf

zbMATH Keywords

continued fractioncontinued fraction expansionfactorizationShanks' method

Mathematics Subject Classification ID

Factorization; primality (11A51) Continued fractions (11A55)

Abstract: Legendre found that the continued fraction expansion of $sqrtN$ having odd period leads directly to an explicit representation of $N$ as the sum of two squares. Similarly, it is shown here that the continued fraction expansion of $sqrtN$ having even period directly produces a factor of a composite $N$. Shanks' infrastructural method is then revisited, and some consequences of its application to factorization by means of the continued fraction expansion of $sqrtN$ are derived.

Recommendations

• scientific article; zbMATH DE number 4158701
• scientific article; zbMATH DE number 1766654
• Continued fractions and parallel SQUFOF
• Subconstituents of unitary graphs over finite fields
• On continued fractions of given period

Cited in

(13)

• Continued fractions and number-theoretic computations
• The completion of Euler's factoring formula
• Application of continued fractions
• scientific article; zbMATH DE number 4158701 (Why is no real title available?)
• Legendre symbols and continued fractions
• Continued fractions and parallel SQUFOF
• scientific article; zbMATH DE number 1919527 (Why is no real title available?)
• scientific article; zbMATH DE number 1766654 (Why is no real title available?)
• On two Fermat's discoveries
• Factorisation in fractional powers
• Factorization and palindromic continued fractions
• A generalization of continued fractions
• An O(log n) algorithm for computing periodic continued fractions and its applications

This page was built for publication: Continued fractions and factoring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5149076)