본 논문은 RSA 알고리즘에서 키 생성 등에 필요한 소수를 효율적으로 생성하는 방법에 대해 논의한다. 본 연구는 현재의 PC 및 스마트폰 환경이 다수의 코어를 갖는 환경인 것을 이용한다. 이를 바탕으로 현재까지 Miller-Rabin test등 확률적인 소수 테스트를 기반으로 하는 방법들 중 가장 효율적이라고 알려진 Bit-array 방법에 대한 병렬화를 시도한다. 제안 방법에서는 Bit-array 알고리즘 수행 도중에 작은 소수를 이용하여 나누어 보는 기본 테스트 과정을 통과한, 즉 Miller-Rabin test 의 수행을 통해 소수인지 아닌지 검증해야할 후보 소수들을 다수의 코어들을 통해 한꺼번에 테스트 한다. 구현을 통해 제안 방법의 성능 향상을 검증하였으며, 일반적인 Desktop 환경에서 1024bit 소수 생성 알고리즘 구현 시 2개의 코어를 사용 시 단일 코어 사용의 경우에 비해 약 110%, 4개의 코어를 사용 시 약 265% 의 성능 향상이 있었다. 본 연구의 결과는 권한 위임을 위해 공개키를 임시키로 사용하는 대리 인증서 환경[14]에서 권한 위임의 효율성을 향상시킬 때 공헌할 것으로 기대한다.
In this paper, we discuss how to efficiently generate a prime number using Multi-core architecture. We modify the bit-array algorithm so that it can work in parallel manner. The proposed algorithm searches for the candidates of prime numbers in parallel. Then, the Miller-Rabin primality tests are performed on these candidates using all available cores. Since more than one candidate can be tested, a prime number can be found in a less time than single-core case if the proposed algorithm works on multi-core environment. Experimental result shows that about 110% and 265% performance improvements are achieved when two and four cores are used, respectively.
