gcd 연산을 이용한 조합 소수 검사 알고리즘의 분석 및 최적화

Abstract

큰 소수를 빠르게 생성하기 위한 다양한 소수 검사 방법이 개발되었으며, 가장 많이 쓰이는 소수 검사 방법은 trial division과 Fermat (또는 Miller-Rabin) 검사를 조합한 방법과 gcd 연산과 Fermat (또는 Miller-Rabin) 검사를 조합한 방법이다. 이 중 trial division과 조합한 방법에 대해서는 확률적 분석을 이용하여 수행시간을 예측하고 수행시간을 최적화 하는 방법이 개발되었다. 하지만, gcd 연산과 조합한 방법에 대해서는 아무런 연구결과도 제시되어 있지 않다. 본 논문에서는 gcd 연산을 이용한 조합 소수 검사 방법에 대해 확률적 분석을 이용하여 수행시간을 예측하고 수행시간을 최적화 하는 방법을 제안한다.; Many kinds of primality test are developed in order to generate large prime numbers and the most use of primality tests are "Combining trial division­Fermat test(or Miller-Rabin)" and "Combining gcd operation­Fermat test(or Miller-Rabin)". The combining trial division­Fermat test was developed the method of expectation of running time and optimization to use the probabilistic analysis. But, the combining gcd operation­Fermat test wasn't. In this paper, we suggest the method of expectation of running time and optimization to use the probabilistic analysis about the combining gcd operation­Fermat test.