Another Approach to Factoring by Continued Fractions

Abstract

The problem of prime factorization is particularly important in fields such as cryptography, where it plays a crucial role, especially in the security of public key cryptosystems like RSA. There are numerous factorization algorithms that have been developed over time, each with varying levels of complexity. These algorithms have played a crucial role in fields like mathematics and cryptography, where prime factorization remains a key challenge. In this study, the continued fraction method one of the factorization methods, is examined. To highlight the importance of the continued fraction factorization method, a brief mention is made of RSA's vulnerability to attacks, such as Weiner's attack, which exploits small private keys. Our approach aims to enhance the efficiency of factorization by integrating this method with relevant theorems by giving concrete examples with detailed tables.

Keywords

• Factorization algorithms
• continued fractions
• RSA algorithm
• cryptography.

References

1. Boneh, D., Durfee, G., Cryptanalysis of RSA with private key d < N0.292, Advances in Cryptology - Proceedings of Eurocrypt ’99, Lecture Notes in Computer Science 1952, 1–11, 1999.
2. Boneh, D., Twenty years of attacks on the RSA cryptosystem, Notices Amer. Math. Soc., 46(1999), 203–213.
3. Brillhart , J., A note on Euler’s factoring problem, The American Mathematical Monthly, 116(10)(2009), 928–931.
4. Lenstra H.W., Pomerance, C., A rigorous time bound for factoring integers, Journal of the American Mathematical Society, 5(1992), 483–516.
5. Mollin, R.A., Fundamental Number Theory with Applications, CRC Press, Boca Raton, New York-London-Tokyo, 1998.
6. Mollin, R.A., An Introduction to Cryptography, Discrete Mathematics and Its Applications, 2007.
7. Pinch, R.G.E., Extending the Wiener attack to RSA-type cryptosystems, Electronics Letters, 31(1995), 1736–1738.
8. Pollard, J.M., Theorems on factorization and primality testing, Proceedings of the Cambridge Philosophical Society, 76(1974), 521–528.

9. Pollard, J.M., A Monte Carlo method for factorization, BIT Numerical Mathematics, 15(3)(1975), 331–334.
10. Pomerance, C, Analysis and comparison of some integer factoring algorithms, Computational Methods in Number Theory, 154(1982), 89–139.
11. Pomerance, C., The quadratic Sieve Factoring Algorithm in Advances in Cryptology — EUROCRYPT ’84, Springer-Verlag, Berlin, LNCS 209, 1985.
12. Pomerance, C., A tale of two sieves, The Notices of the Amer. Math. Soc., 43(1996), 1473–1485.
13. Rivest, R., Shamir, A., Adleman, L., A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, 21(2), 120–126.
14. Rosen, Kenneth H., Elementary Number Theory and Its Applications, Addison-Wesley Publishing Company, 1986.
15. Wiener, M.J., Cryptanalysis of short RSA secret exponents, IEEE Transactions on Information Theory, 36(1990), 553–558.
16. Williams, H.C., A p + 1 method of factoring, Mathematics of Computation, 39(159)(1982), 225–234.