Cryptography plays a crucial role in today’s society. Given the influence, cryptographic algorithms need to be trustworthy. Cryptographic algorithms such as RSA relies on the problem of prime number factorization to provide its confidentiality. Hence finding a way to make it computationally feasible to find the prime factors of any integer would break RSA’s confidentiality.

The approach presented in this thesis explores the possibility of trying to construct φ(n) from n. This enables factorization of n into its two prime numbers p and q through the method presented in the original RSA paper. The construction of φ(n) from n is achieved by analyzing bitwise relations between the two.

While there are some limitations on p and q this thesis can in favorable circumstances construct about half of the bits in φ(n) from n. Moreover, based on the research a conjecture has been proposed which outlines further characteristics between n and φ(n).