편집을 취소할 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
최신판 | 당신의 편집 | ||
92번째 줄: | 92번째 줄: | ||
#<math>\phi</math> | #<math>\phi</math> | ||
#:<math>\phi=\left(p-1\right)\left(q-1\right)=pq-p-q+1=n-p-q+1</math>이므로, <math>p+q=n-\phi+1</math>. 또한, <math>pq=n</math>. 따라서, <math>p,q</math>는 이차 방정식 <math>x^2-\left(n-\phi+1\right)x+n=0</math>의 두 근이다. 근의 공식을 이용하면, <math>p,q=\frac{\left(n-\phi+1\right)\pm\sqrt{\left(n-\phi+1\right)^2-4n}}{2}</math>. 한편, <math>d</math>는 유클리드 호제법을 이용하면 된다. | #:<math>\phi=\left(p-1\right)\left(q-1\right)=pq-p-q+1=n-p-q+1</math>이므로, <math>p+q=n-\phi+1</math>. 또한, <math>pq=n</math>. 따라서, <math>p,q</math>는 이차 방정식 <math>x^2-\left(n-\phi+1\right)x+n=0</math>의 두 근이다. 근의 공식을 이용하면, <math>p,q=\frac{\left(n-\phi+1\right)\pm\sqrt{\left(n-\phi+1\right)^2-4n}}{2}</math>. 한편, <math>d</math>는 유클리드 호제법을 이용하면 된다. | ||
#<math>d</math>: | #<math>d</math>: 2가지 방법이 알려져 있다. | ||
##<math>r=de-1</math>이라 하자. 그럼, 적당한 홀수 <math>m</math>에 대해 <math>r=2^km</math>로 나타낼 수 있다. 이제 적당한 <math>a</math>에 대해, <math>b_0\equiv a^m\pmod n</math>이라 하자. 이제 <math>b_0</math>을 연속 제곱하여 <math>b_{u+1}\equiv{b_u}^2\pmod n</math>를 1이 나올 때까지 구한다. <math>k</math>번 연속 제곱하면 반드시 1이 나오게 되어 있으므로 1이 나오지 않을 염려는 할 필요 없다 (이유는 직접 생각해보자). 만약 1이 나오지 않았다면 <math>a</math>와 <math>n</math>이 서로소가 아니라는 뜻이므로, <math>n</math>의 인수를 찾은 셈. 만약 <math>b_{u+1}\equiv1\pmod n</math>이고, <math>b_u\equiv-1\pmod n</math>이면, <math>a</math>의 값을 바꿔 다시 시도한다. 만약 <math>b_{u+1}\equiv1\pmod n</math>이고 <math>b_u\not\equiv\pm1\pmod n</math>이면, <math>\gcd\left(b_u-1,n\right)</math>가 <math>n</math>의 한 인수가 된다. <math>n</math>의 한 인수를 찾았으므로 나머지 인수를 쉽게 찾을 수 있고, <math>\phi</math>도 쉽게 찾을 수 있다. | ##<math>r=de-1</math>이라 하자. 그럼, 적당한 홀수 <math>m</math>에 대해 <math>r=2^km</math>로 나타낼 수 있다. 이제 적당한 <math>a</math>에 대해, <math>b_0\equiv a^m\pmod n</math>이라 하자. 이제 <math>b_0</math>을 연속 제곱하여 <math>b_{u+1}\equiv{b_u}^2\pmod n</math>를 1이 나올 때까지 구한다. <math>k</math>번 연속 제곱하면 반드시 1이 나오게 되어 있으므로 1이 나오지 않을 염려는 할 필요 없다 (이유는 직접 생각해보자). 만약 1이 나오지 않았다면 <math>a</math>와 <math>n</math>이 서로소가 아니라는 뜻이므로, <math>n</math>의 인수를 찾은 셈. 만약 <math>b_{u+1}\equiv1\pmod n</math>이고, <math>b_u\equiv-1\pmod n</math>이면, <math>a</math>의 값을 바꿔 다시 시도한다. 만약 <math>b_{u+1}\equiv1\pmod n</math>이고 <math>b_u\not\equiv\pm1\pmod n</math>이면, <math>\gcd\left(b_u-1,n\right)</math>가 <math>n</math>의 한 인수가 된다. <math>n</math>의 한 인수를 찾았으므로 나머지 인수를 쉽게 찾을 수 있고, <math>\phi</math>도 쉽게 찾을 수 있다. | ||
##<math>de=1+k\phi</math>에서, <math>k</math>를 찾을 수 있다면 <math>\phi</math>를 찾을 수 있다. 우선 양변을 <math>n</math>으로 나누면, <math>\frac{de}{n}=\frac{1}{n}+k\frac{\phi}{n}</math>인데, <math>n</math>이 200자리 숫자고 소인수가 2개밖에 없으므로, <math>\phi\approx n</math>이다. 즉, <math>\frac{de}{n}\approx k</math>. 이제 <math>k</math>를 찾았으므로 <math>\phi</math>를 계산할 수 있고, <math>\phi</math>를 알고 있으므로 <math>n</math>의 두 소인수를 찾을 수 있다. | ##<math>de=1+k\phi</math>에서, <math>k</math>를 찾을 수 있다면 <math>\phi</math>를 찾을 수 있다. 우선 양변을 <math>n</math>으로 나누면, <math>\frac{de}{n}=\frac{1}{n}+k\frac{\phi}{n}</math>인데, <math>n</math>이 200자리 숫자고 소인수가 2개밖에 없으므로, <math>\phi\approx n</math>이다. 즉, <math>\frac{de}{n}\approx k</math>. 이제 <math>k</math>를 찾았으므로 <math>\phi</math>를 계산할 수 있고, <math>\phi</math>를 알고 있으므로 <math>n</math>의 두 소인수를 찾을 수 있다. |