Posts

Showing posts from October, 2018

Continued fraction factorization method

Image
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.