There is to be virtually impossible to solve the very large digits of prime number p and q fromcomposite number n=pq using integer factorization in typical public-key cryptosystems, RSA.
When the public key e and the composite number n are known but the private key d remainsunknown in an asymmetric-key RSA, message decryption is carried out by first obtaining φ(n)=(p-1)(q-1)=n+1-(p+q) and then using a reverse function of d=e-¹(modn)). Integerfactorization from n to p,q is most widely used to produce φ(n), which has been regarded asmathematically hard. Among various integer factorization methods, the most popularly used is thecongruence of squares of a² ≡b²(modn), a=(p+q)/2, b=(q-p)/2 which is more commonly used then n/p=q trial division. Despite the availability of a number of congruence of scares methods,however, many of the RSA numbers remain unfactorable. This paper thus proposes an algorithmthat directly and immediately obtains φ(n). The proposed algorithm computes 2kβj≡2t(modn), 0≤ i ≤ γ-1,k=1,2,⋯or 2kβj=2βj for 2j≡βj(modn),2 γ-1＜n＜2γ, j=γ-1,γ,γ+1 to obtain thesolution. It has been found to be capable of finding an arbitrarily located φ(n) in a range of n-10 ⌊√2⌋＜ φ(n) ≤ n-2⌊√2⌋ much more efficiently than conventional algorithms.