- 암호해독을 위한 소인수분해
- ㆍ 저자명
- 이상운,최명복,Lee. Sang-Un,Choi. Myeong-Bok
- ㆍ 간행물명
- 한국인터넷방송통신학회 논문지
- ㆍ 권/호정보
- 2013년|13권 6호|pp.221-228 (8 pages)
- ㆍ 발행정보
- 한국인터넷방송통신학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
큰 반소수 n=pq의 소인수 p,q를 나눗셈 시행법으로 직접 찾는 것은 현실적으로 거의 불가능하다. 따라서 대부분의 소인수분해 알고리즘은$a^2{equiv}b^2$ (mod n)의 제곱합동을 찾아 p=GCD(a-b, n), q=GCD(a+b, n)의 소인수를 찾는 간접 방법을 적용하고 있다. n = pq에 대해 p와 q를 선택한 영역은 $l(p)=l(q)=l(sqrt{n})=0.5l(n)$의 [$10{cdots}01$, $99{cdots}9$] 범위에서 $sqrt{n}$을 기준으로 $10{cdots}00$ < p < $sqrt{n}$과 $sqrt{n}$ < q < $99{cdots}9$에 존재한다는 사실만이 밝혀졌다. 본 논문은 n으로 부터 획득한 정보를 이용하여 p의 범위를 보다 축소시키는 방법을 제안한다. 제안 방법은 $n=n_{LR}+n_{RL}$, $l(n_{LR})=l(n_{RL})=l(sqrt{n})$으로 분할하여 $p_{min}=n_{LR}$, $q_{min}=n_{RL}$로 설정하는 방법을 적용하였다. 본 논문에서 제안한 n의 정보로 p의 범위를 축소하는 방법은 $sqrt{n}$의 정보로 p의 범위 축소 방법에 비해 최소 17.79%에서 최대 90.17%의 범위 축소 효과를 얻었다.
It is impossible directly to find a prime number p,q of a large semiprime n = pq using Trial Division method. So the most of the factorization algorithms use the indirection method which finds a prime number of p = GCD(a-b, n), q=GCD(a+b, n); get with a congruence of squares of $a^2{equiv}b^2$ (mod n). It is just known the fact which the area that selects p and q about n=pq is between $10{cdots}00$ < p < $sqrt{n}$ and $sqrt{n}$ < q < $99{cdots}9$ based on $sqrt{n}$ in the range, [$10{cdots}01$, $99{cdots}9$] of $l(p)=l(q)=l(sqrt{n})=0.5l(n)$. This paper proposes the method that reduces the range of p using information obtained from n. The proposed method uses the method that sets to $p_{min}=n_{LR}$, $q_{min}=n_{RL}$; divide into $n=n_{LR}+n_{RL}$, $l(n_{LR})=l(n_{RL})=l(sqrt{n})$. The proposed method is more effective from minimum 17.79% to maxmimum 90.17% than the method that reduces using $sqrt{n}$ information.