[논문]페르마 인수분해 방법의 확장과 검증에 대한 고찰

정서현; 정수환

doi:10.13089/jkiisc.2010.20.3.3

페르마 인수분해 방법의 확장과 검증에 대한 고찰
A Consideration on Verification and Extension of Fermat's Factorization 원문보기

情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology, v.20 no.3, 2010년, pp.3 - 8

정서현 (숭실대학교 전자공학과) , 정수환 (숭실대학교 정보통신전자공학부)

초록
AI-Helper

인수분해에 관한 여러 가지 전수공격이 알려져 있다. 페르마의 인수분해 방법은 여러 가지 공격 중에 두 인수가 비슷한 크기인 경우에 가장 잘 동작한다고 알려져 있다. 본 논문에서는 페르마의 방법이 위와 같은 상황에서 잘 동작하는지 보이고, 그 해가 유일함을 증명한다. 이러한 증명을 이용하여 임의의 심작점에서 페르마의 정리를 시작 할 수 있다. 또한 본 증명은 "인수분해하다"는 명제와 "제곱수를 찾다"라는 명제가 동일함을 의미한다.

Abstract ▼ AI-Helper

There are some efficient brute force algorithm for factorization. Fermat's factorization is one of the way of brute force attack. Fermat's method works best when there is factor near the square-root. This paper shows that why Fermat's method is effective and verify that there are only one answer. Because there are only one answer, we can start Fermat's factorization anywhere. Also, we convert from factorization to finding square number.

주제어

AI 본문요약
AI-Helper

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

문제 정의

페르마의 인수분해 방법은 ”인수는 특정 제곱 식으로 주어진다「라는 명제에서 시작하는데 본 논문에서는 이를 역을 증명함으로써 페르마 정리에 사용된 인수분해 과정과 제곱수 찾기라는 문제가 동치 임을 보였다. 또한 본 논문에서는 제곱수와 또 다른 제곱수와의 관계를 기하학적으로 기술하여 정확하면서도 빠르게 제곱수의 조건을 판별하는 방법을 제시하였다. 이와 같은 논리적 기반은 페르마의 인수분해 방법이 임의의 시작점 설정이 가능함을 제시한다.
본 논문에서 많은 인수분해 방법 중에서 페르마의 인수분해 방법에 대하여 고찰하였다. 페르마의 인수분해 방법은 두 인수가 비슷한 경우에 인수분해가 빠르다고 알려져 있다.

가설 설정

되는 최소 1개의 식이 존재한다. 먼저 최소의 경우부터 시작하여 하나의 정당한 식을 찾았다고 가정하고 〔그림 5)와 같이 s와 z를 적당하게 조절하여 또 다른 해를 찾는다고 가정해 보자. 찾은 해는 가장 작은 해가 된다.

성능/효과

빠른 이유에 관한 해석이 없다. 따라서 두수가 비슷한 경우 인수를 찾는다는 가정에서부터 알고리즘의 설계를 시작하여, 비슷한 결론의 수식이 생성됨을 보이고, 결론적으로 페르마 알고리즘이 두수가 비슷할 때 효과적임을 보이도록 한다.
따라서 본 논문에서는 페르마 인수분해에서 변수가 가지는 의미를 상이한 방법으로 해석하고, 역으로 사용이 타당함을 보임으로써 , 인수분해문제가 제곱근을 찾는 문제로 귀결될 수 있음을 보인다.
반드시 k=-s라는 정의를 성립 할 수 없으며, 본 논문에서는 p와 q가 소수일 때 식 3이 유일한 해를 가짐을 보임으로써, p와 g가 소수일 때 반드시 A;=-s임을 증명하였다.
페르마의 인수분해 방법은 두 인수가 비슷한 경우에 인수분해가 빠르다고 알려져 있다. 페르마의 인수분해 방법은 ”인수는 특정 제곱 식으로 주어진다「라는 명제에서 시작하는데 본 논문에서는 이를 역을 증명함으로써 페르마 정리에 사용된 인수분해 과정과 제곱수 찾기라는 문제가 동치 임을 보였다. 또한 본 논문에서는 제곱수와 또 다른 제곱수와의 관계를 기하학적으로 기술하여 정확하면서도 빠르게 제곱수의 조건을 판별하는 방법을 제시하였다.
이와 같은 논리적 기반은 페르마의 인수분해 방법이 임의의 시작점 설정이 가능함을 제시한다. 한 발 더 나아가 임의의 시작점 보다 작거나 큰 부분에 해가 존재하지 않는다는 것을 증명한다면 보다 효율적인 인수분해가 가능하게 된다는 결론을 얻게 된다.

참고문헌 (9)

G. Wilson, "Factorization of the covariance generating function of a pure moving average process," SIAM J. Numer. Anal. pp. 1-7, Mar. 1969.

상세보기
R. Solovay and V. Strassen, "A fast Monte-Carlo test for primality," SIAM Journal on Computing, vol. 6. no. 1 pp. 84-85, 1977.

상세보기
O. Rabin, "Probabilistic algorithm for testing primality," Journal of Number Theory, vol. 12, no. 1, pp. 128-138, Feb. 1980.

상세보기
C. Mcintosh, "Finding prime numbers : Miller rabin and beyond," Furman University Electronic, vol. 12, pp. 1-4, 2007.
E. Bach, "Toward a theory of Pollard's rho method," Information and Computation, vol. 90, no. 2, pp. 139-155, Feb. 1991.

상세보기
김종국, "Fermat의 定理에 關한 硏究," 박사학위논문, 성균관대학교, 1989년 8월.
이민섭, 현대암호학, 2판, 敎友社, pp. 272-292, 2007년 3월.
J. McKee, "Speeding Fermat's factoring method," Mathematics of Computation, pp. 1729-1737, Mar. 1999.

상세보기
D.M. Burton, Elementary number theory, McGRAW HILL, pp. 82-88, Sep. 1998.

저자의 다른 논문 :

LOADING...

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증