Showing posts from October, 2018

Continued fraction factorization method

Prime factorization of composite integers has many applications in number theory,  especially in computing many important arithmetic functions for large non-trivial inputs.

One such function is Euler's totient function `φ(n)`, which it's practically impossible to compute it for a "hard" large random composite `n`, if the prime factorization of `n` is not known.

This led to the creation of public-key cryptography systems (such as the RSA algorithm), which are systems responsible for secure communication online and rely on the assumption that it's very hard to factorize a large integer `n` that is the product of two large random prime numbers.