earticle

영어

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 a2 ≡ b2(mod n). It is just known the fact which the area that selects p and q about n = pq is between 10 ⋯ 00 < p <  and < q < 99 ⋯ 9 based on  in the range, [10 ⋯ 01, 99 ⋯ 9 of l(q) = l() = 0.5(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 pmin = nLR, qmin = nRL ; divide into nLR + nRL, l(nLR) = l(nRL) = L( ). The proposed method is more effective from minimum 17.79% to maxmimum 90.17% than the method that reduces using  information.

한국어

큰 반소수 n = pq의 소인수 p,q를 나눗셈 시행법으로 직접 찾는 것은 현실적으로 거의 불가능하다. 따라서 대 부분의 소인수분해 알고리즘은 a2 ≡b2(mod n)의 제곱합동을 찾아 p = GCD(a-b,n), q=GCD(a+b,n)의 소인수를 찾는 간접 방법을 적용하고 있다. n = pq에 대해 p와 q를 선택한 영역은 l(p) = l(q) = l( ) = 0.5l(n)의 [10 ⋯ 01, 99 ⋯ 9] 범위에서  을 기준으로 10 ⋯ 00