다항식 선택을 위한 효율적인 최적화 기법
Efficient Optimization Method for Polynomial Selection
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
현재까지 알려진 가장 효율적인 인수분해 방법은 General Number Field Sieve (GNFS)를 이용하는 방법이다. CADO-NFS는 GNFS를 기반으로 구현된 공개된 소프트웨어로 RSA-704의 인수분해에 사용된 도구이다. CADO-NFS에서 다항식 선택은 크게 다항식을 생성하는 과정과 이를 최적화하는 과정으로 나누어져 있다. 그러나CADO-NFS에서 다항식의 최적화 과정은 전체 다항식 선택 소요 시간 중 약 90%를 차지할 정도로 큰 부하를 주고있다. 본 논문에서는 사전 연산 테이블을 이용하여 다항식 최적화 과정의 부하를 줄이는 방안을 제안한다. 제안하는 방법은 기존 CADO-NFS의 다항식과 같은 다항식을 선택하지만, 다항식 선택에 걸리는 시간은 약 40% 감소한다.
Abstract
Currently, General Number Field Sieve(GNFS) is known as the most efficient way for factoring large numbers. CADO-NFS is an open software based on GNFS, that was used to factor RSA-704. Polynomial selection in CADO-NFS can be divided into two stages – polynomial selection, and optimization of selected polynomial. However, optimization of selected polynomial in CADO-NFS is an immense procedure which takes 90% of time in total polynomial selection. In this paper, we introduce modification of optimization stage in CADO-NFS. We implemented precomputation table and modified optimization algorithm to reduce redundant calculation for faster optimization. As a result, we select same polynomial as CADO-NFS, with approximately 40% decrease in time.
참고문헌 (11)
- R. Rivest, "A Method for Obtaining Digital Signature and Public-Key Cryptosystems", ACM, 21(2), pp.120~126 (1978)
- T. Kleinjung, "Polynomial selection", CADO workshop on integer factorization (2008), INRIA Nancy
- T. Kleinjung, "On polynomial selection for the general number field sieve", Mathematics of Computation, pp.2037~2047 (2006)
- S. Bai, "Polynomial Selection for the Number Field Sieve", Ph.D., pp.2011
- "Factorisation of RSA-704 with CADO-NFS. Report"[URL]
- T. Kleinjung, "“Factorization of a 768-bit RSA modulus,” CRYPTO ’10", LNCS, 6223, pp.333~350 (2010)
- A. K. Lenstra, "The Development of the Number Field Sieve", Lecture Notes in Mathematics, 1554 (1993)
- Matthew E. Brigg, "An Introduction to the General Number Field Sieve", Master, pp.1998
- "CADO-NFS"[URL]
- B. A. Murphy, "On Quadratic Polynomials for the Number Field Sieve", CATS’98, pp.199~231 (1998)
- B. A. Murphy, "Polynomial Selection for the Number Field Sieve Integer Factorization Algorithm", Ph.D., pp.1999