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 자리 수에 대해서는 실패하였 다.