대표적인 공개키 암호방식인 RSA에 사용되는 합성수 n=pq의 큰자리 소수 p,q를 소인수분해하여 구하는 것은사실상 불가능하다. 공개키e와 합성수 n은 알고 개인키 d를 모를 때, φ(n)=(p-1)(q-1)=n+1-(p+q)을 구하여 d=e-¹(modn))의 역함수로 개인키 d를 해독할수 있다. 따라서 φ(n)을 알기위해 n으로부터 p,를 구하는 수학적 난제인 소인수분해법을 적용하고 있다. 소인수분해법에는 n/p=q의 나눗셈 시행법보다는 a² ≡b²(modn), a=(p+q)/2, b=(q-p)/2의 제곱합동법이 일반적으로 적용되고 있다. 그러나 다양한 제곱합동법이 존재함에도 불구하고 아직까지도 많은 RSA 수들이 해독되지 않고 있다. 본 논문은 φ(n)을 직접 구하는 알고리즘을 제안하였다. 제안된 알고리즘은 2j≡βj(modn),2 γ-1＜n＜2γ, j=γ-1,γ,γ+1에 대해 2kβj≡2t(modn), 0≤ i ≤ γ-1,k=1,2,?또는 2kβj=2βj로 φ(n)을 구하였다. 제안된 알고리즘은 n-10 ?√2?＜ φ(n) ≤ n-2?√2?의 임의의 위치에 존재하는 φ(n)도 약 2배 차이의 수행횟수로 찾을 수 있었다.
본고는 φ(n)을 직접 구하는 알고리즘을 제시했다. 제시된 알고리즘은 2j≡β j(modn),2 γ-1＜n＜2γ, j=γ-1, γ, γ+1에 대해 2kβ j ≡2t(modn), 0≤ i ≤ γ-1, k=1,2, ?또는 2kβ j=2β j로 φ(n)을 구했다.