[논문]n+1 소인수분해 알고리즘

최명복; 이상운

doi:10.7236/jiwit.2011.11.2.107

초록
AI-Helper

$n=pq$인 합성수 을 크기가 비슷한 p와 q로 소인수분해하는 것은 매우 어려운 문제이다. 대부분의 소인수분해 알고리즘은 $a^2{\equiv}b^2$ (mod $n$)인 제곱 합동이 되는 ($a,b$)를 소수의 곱 (인자 기준, factor base, B)으로 찾아 $a^2-b^2=(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$가 되는 값을 $\sqrt{n}$ < $a$ < $\sqrt{2n}$ 범위에서 구하여 $n-2$의 소인수분해로 $x$를 얻고, $y=\frac{a}{fx}$, $y_1$={1,3,7,9}을 구한다. 제안된 알고리즘을 몇 가지 사례에 적용한 결과 $\sqrt{n}$ < $a$를 순차적으로 찾는 기존의 페르마 알고리즘에 비해 수행 속도를 현격히 단축시키는 효과를 얻었다.

Abstract ▼ AI-Helper

It is very difficult to factorize composite number, $n=pq$ 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 ($a^2{\equiv}b^2$ (mod $n$...

It is very difficult to factorize composite number, $n=pq$ 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 ($a^2{\equiv}b^2$ (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 $a^2-b^2=(a-b)(a+b)$. The efficiency of these algorithms hangs on finding ($a,b$) and 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$, $\sqrt{n}$ < $a$ < $\sqrt{2n}$) from integer factorization of $n-2$ and gets $y=\frac{a}{fx}$, $y_1$={1,3,7,9}. Our algorithm is much more effective in comparison with the conventional Fermat algorithm that sequentially finds $\sqrt{n}$ < $a$.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문은 a2 ≡ b2(mod n)의 제곱합동을 보다 빠르게 찾는 방법을 제안한다.
본 논문은 a2 ≡ b2(mod n)의 제곱합동을 빠르게 찾는 알고리즘을 제안하였다.

제안 방법

제안된 알고리즘은 인자기준 B를 n+1을 소인수분해하여 얻는다. 다음으로 B 값에 특정 기준을 적용하여 f 값을 얻고, # 의 범위에서 a = fxy가 되는 x는 n-2를 소인수분해하여 얻었다.
(mod n)의 제곱합동을 빠르게 찾는 알고리즘을 제안하였다. 제안된 알고리즘은 합성수 n은 소인수분해가 되지 않지만 합성수 a는 소인수 분해가 된다는 특징을 이용하였다. 즉, a는 소수들의 곱인 정준분해로 표기되며, 이들 소수들 중에서 B ≤ 19을 인자기준 B로 결정하였다.

이론/모형

데이터 처리 단계에서는 데이터 수집 단계에서 획득한 a,b에 대해 a2 - b2 = (a+b) (a-b)공식에 기반하여 유클리드 (Euclid)의 최대 공약수 (Great Common Divisor, GCD) 법칙을 적용하여 p = GCD(a-b, n), q = GCD(a+b, n)을 결정한다.

성능/효과

제안된 n+1 알고리즘은 표 2와 같이 #에서 순차적으로 a2 ≡ b2 (mod n)이 되는 제곱 합동 a,b를 찾는 페르마 알고리즘에 비해 수행 속도를 현격히 줄이는 효과를 얻었다.

질의응답

핵심어	질문	논문에서 추출한 답변
	RSA 암호를 해독하기 위한 소인수분해 방법에는 무엇이 있는가?	소인수분해 방법에는 나눗셈 시행 (Trial Division), Pollard의 rho 알고리즘, Pollad의 p-1 알고리즘, William의 p+1 알고리즘, Lenstra elliptic curve 인수분해, 페르마 (Fermat)의 인수분해 방법, 오일러 (Euler)의 인수분해 방법, Special Number Field Sieve, 2차 (Quadratic, Q), MPQ (Multiple-polynomial quadratic), NF (Number field), GNF (General number field), Dixon, CFRAC (continued fraction factorization), SQUFOF (Shanks' square forms factorization)과 양자 컴퓨터를 활용한Shor 알고리즘이 있으며, 대부분은 a2≡b2(mod n) 의 제곱합동 (congruence of squares)에 기반하고 있다.[2]
	RSA 암호를 해독하기 위해 필요한 것은 무엇인가?	RSA 암호체계 (cryptograph)는 큰 자리수의 숫자 n을 p와 q로 소인수분해 (integer factorization)가 어렵다는 이론에 기반을 두고 있다.[1] RSA 암호를 해독하기 위해서는 n=pq인 합성수 (composite number) n을 2개소수 p.q로 소인수분해 해야 한다.[2,3] 여기서, p와 q는크기 (자리수)가 비슷한 큰 소수들이 사용되고 있으며 각각을 소수 인자 (prime factor)라 한다.
	RSA 암호체계는 어떠한 이론에 기반을 두고 있는가?	RSA 암호체계 (cryptograph)는 큰 자리수의 숫자 n을 p와 q로 소인수분해 (integer factorization)가 어렵다는 이론에 기반을 두고 있다.[1] RSA 암호를 해독하기 위해서는 n=pq인 합성수 (composite number) n을 2개소수 p.

참고문헌 (10)

Wikipedia, "RSA," http://en.wikipedia.org/wiki/Rsa, 2010.
Wikipedia,"Integer Factorization," http://en.wikipedia.org/wiki/Integer_factorization, 2010.
Wikipedia, "RSA Factoring Challenge," http://en.wikipedia.org/wiki/RSA_Factoring_ Challenge, 2010.
Wikipedia, "Fermat's Factorization Method," http://en.wikipedia.org/wiki/Fermat's_factorization _method, 2010.
Wikipedia, "Dixon's Factorization Method," http://en.wikipedia.org/wiki/Dixon%27s_ factorization_method, 2010.
Wikipedia, "Quadratic Sieve," http://en.wikipedia.org/wiki/Quadratic_sieve, 2010.
Wikipedia, "General Number Field Sieve," http://en.wikipedia.org/wiki/General_number _field_sieve, 2010.
Wikipedia, "Rational Sieve," http://en.wikipedia.org/wiki/Rational_sieve, 2010.
김승주, "공개키 암호 방식," School of Information and Communication Engineering, Sungkyunkwan University, http://dosan.skku.or.kr/-sjkim/Lecture Notes/SKKU/2006/ECE3063/Lec05(crypto).pdf, 2007.
P. L. Jensen, "pGNFS," http://pgnfs.org/index.php?page Results, 2009.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

n+1 소인수분해 알고리즘
The n+1 Integer Factorization Algorithm 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

제안 방법

이론/모형

성능/효과

질의응답

참고문헌 (10)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

n+1 소인수분해 알고리즘 The n+1 Integer Factorization Algorithm 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

이론/모형

성능/효과

질의응답

참고문헌 (10)

이 논문을 인용한 문헌

저자의 다른 논문 :

최명복 (36) 이상운 (190)

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

n+1 소인수분해 알고리즘
The n+1 Integer Factorization Algorithm 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper