Earticle

초록

영어

It is almost impossible to directly find the prime factor, p,q of a large semiprime, n=pq . So Most of the integer factorization algorithms uses a indirect method that find the prime factor of the p= GCD(a-b,n),q = GCD(a+b,n) after getting the congruence of squares of the a2 ≡ b2(mod n) . Many methods of getting the congruence of squares have proposed, but it is not easy to get with RSA number of greater than a 100-digit number. This paper proposes a fast algorithm to get the congruence of squares. The proposed algorithm succeeded in getting the congruence of squares to a 19-digit number.

한국어

큰 반소수 n=pq의 소인수 p,q를 직접 찾는 것은 현실적으로 거의 불가능하여 대부분의 소인수분해 알고리 즘은 a2≡b2(mod n)의 제곱합동을 찾아 p=GCD(a-b, n), q=GCD(a+b, n)의 소인수를 찾는 간접 방법을 적용하고 있다. 제곱합동 a,b을 찾는 다양한 방법이 제안되었지만 100자리 이상인 RSA 수에 대해서는 적용이 쉽지 않다. 본 논문에서는 xa = ⌈  ⌉ or ⌈ ⌉+ z, z = 1, 2, ⋯ 로 설정하고 (xa)2 ≡ (yb)2 (mod n) 을 찾는 간단한 방법을 제안한 다. 제안된 알고리즘은 19 자리 수 까지는 제곱합동을 빠르게 찾는데 성공하였으나 39 자리 수에 대해서는 실패하였 다.

목차

요약
 Abstract
 Ⅰ. 서론
 Ⅱ. 반소수의 소인수 분해법
 Ⅲ. 제곱합동 소인수분해 알고리즘
 Ⅳ. 알고리즘 적용성 평가
 Ⅴ. 결론 및 향후 연구과제
 참고문헌

키워드

저자

• 이상운 [ Sang-Un Lee | 정회원, 강릉원주대학교, 멀티미디어공학과 ]
• 최명복 [ Myeong-Bok Choi | 종신회원, 강릉원주대학교 멀티미디어공학과 ] Corresponding Author

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국인터넷방송통신학회 논문지 [The Journal of the Institute of Internet, Broadcasting and Communication]

• 간기

  격월간

• pISSN

  2289-0238

• eISSN

  2289-0246

• 수록기간

  2001~2025

• 십진분류

  KDC 326 DDC 380