earticle

논문검색

n+1 소인수분해 알고리즘

원문정보

The n+1 Integer Factorization Algorithm

최명복, 이상운

피인용수 : 0(자료제공 : 네이버학술정보)

초록

영어

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. 정회원, 강릉원주대학교 멀티미디어공학과

참고문헌

자료제공 : 네이버학술정보

    함께 이용한 논문

      ※ 기관로그인 시 무료 이용이 가능합니다.

      • 4,000원

      0개의 논문이 장바구니에 담겼습니다.