다항식 선택을 위한 효율적인 최적화 기법

Vol. 26, No. 3, pp. 631-644, 6월. 2016
10.13089/JKIISC.2016.26.3.631, Full Text:
Keywords: GNFS, Polynomial Selection, Root optimization
Abstract

현재까지 알려진 가장 효율적인 인수분해 방법은 General Number Field Sieve (GNFS)를 이용하는 방법이다. CADO-NFS는 GNFS를 기반으로 구현된 공개된 소프트웨어로 RSA-704의 인수분해에 사용된 도구이다. CADO-NFS에서 다항식 선택은 크게 다항식을 생성하는 과정과 이를 최적화하는 과정으로 나누어져 있다. 그러나 CADO-NFS에서 다항식의 최적화 과정은 전체 다항식 선택 소요 시간 중 약 90%를 차지할 정도로 큰 부하를 주고 있다. 본 논문에서는 사전 연산 테이블을 이용하여 다항식 최적화 과정의 부하를 줄이는 방안을 제안한다. 제안하는 방법은 기존 CADO-NFS의 다항식과 같은 다항식을 선택하지만, 다항식 선택에 걸리는 시간은 약 40% 감소한다.

Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from December 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
S. Kim, H. Kwon, Y. Lee, N. S. Chang, K. Yoon, C. H. Kim, Y. Park and S. Hong, "Efficient Optimization Method for Polynomial Selection," Journal of The Korea Institute of Information Security and Cryptology, vol. 26, no. 3, pp. 631-644, 2016. DOI: 10.13089/JKIISC.2016.26.3.631.

[ACM Style]
Suhri Kim, Heetaek Kwon, Yongseong Lee, Nam Su Chang, Kisoon Yoon, Chang Han Kim, Young-Ho Park, and Seokhie Hong. 2016. Efficient Optimization Method for Polynomial Selection. Journal of The Korea Institute of Information Security and Cryptology, 26, 3, (2016), 631-644. DOI: 10.13089/JKIISC.2016.26.3.631.