Earticle

초록

영어

It is very difficult to factorize composite number, to integer factorization, p and q that is almost similar length of digits. Integer factorization algorithms, for the most part, find (a,b) that is congruence of squares (a2=b2(mod n)) with using factoring(factor base, B) and get the result, p=GCD(a-b,n), q=GCD(a+b,n) with taking the greatest common divisor of Euclid based on the formula a2-b2=(a-b)(a+b). The efficiency of these algorithms hangs on finding a(a,b)nd deciding factor base, B. This paper proposes a efficient algorithm. The proposed algorithm extracts B from integer factorization with 3 digits prime numbers of n+1 and decides f, the combination of B. And then it obtains x(this is, a=fxy, ) from integer factorization of n-2 and gets y-fx/a. Our algorithm is much more effective in comparison with the conventional Fermat algorithm that sequentially finds .

한국어

n=pq인 합성수 n을 크기가 비슷한 p와 q로 소인수분해하는 것은 매우 어려운 문제이다. 대부분의 소인수분해 알고리즘은 a2=b2(mod n)인 제곱 합동이 되는 (a,b)를 소수의 곱 (인자 기준, factor base, B)으로 찾아 a2-b2=(a-b)(a+b) 공식에 의거 유클리드의 최대공약수 공식을 적용하여 p=GCD(a-b,n), q=GCD(a+b,n)으로 구한다. 여기서 (a,b)를 얼마나 빨리 찾는가에 알고리즘들의 차이가 있으며, B를 결정하는 어려움이 있다. 본 논문은 좀 더 효율적인 알고리즘을 제안한다. 제안된 알고리즘에서는 n+1을 3자리 소수까지 소인수분해하여 B를 추출하고 B의 조합 f를 결정한다. 다음으로, a=fxy가 되는 값을 범위에서 구하여 n-2의 소인수분해로 x를 얻고, y=fx/a, y1={1,3,7,9}을 구한다. 제안된 알고리즘을 몇 가지 사례에 적용한 결과 를 순차적으로 찾는 기존의 페르마 알고리즘에 비해 수행 속도를 현격히 단축시키는 효과를 얻었다.

목차

요약
 Abstract
 I. 서론
 II. 제곱합동 소인수분해 방법
 III. n+1 소인수분해 알고리즘
 IV. 알고리즘 적용 결과 분석
 V. 결론
 참고문헌

키워드

저자

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

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

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

• 간기

  격월간

• pISSN

  2289-0238

• eISSN

  2289-0246

• 수록기간

  2001~2025

• 십진분류

  KDC 326 DDC 380