나눗셈 테이블을 이용한 소수 및 안전소수 생성법의 확률적 분석
Probabilistic Analysis of Prime and Safe-prime Generation with Division Table
김창기(한양대학교); 조호성(한양대학교); 박희진(한양대학교)
12권 6호, 82~91쪽
초록
공개키 암호시스템에서는 보안성을 높이기 위해 매우 큰 소수나 안전소수를 사용한다. 하지만 큰 소수를 생성하기위해서는 많은 시간이 걸리기 때문에 소수를 빠르게 생성하는 연구가 중요하다. 나눗셈 테이블 순차난수 생성법은나눗셈 테이블의 길이에 따라 소수 생성 시간이 달라지기 때문에 최적의 테이블 길이를 찾는 것이 필요하다. 현재는모든 길이의 테이블에 대해서 실제로 소수를 생성해 본 후 그 중에서 최적의 테이블 길이를 선택하는 매우 비효율적인 방법이 사용되고 있다. 본 논문에서는 나눗셈 테이블 순차난수 생성법의 (안전)소수 생성 시간을 예측하는 확률적 모델을 제안한다. 이 확률 모델은 나눗셈 테이블의 길이가 인자로 주어졌을 때 (안전)소수 생성알고리즘의 수행시간을 예측하는 모델이다. 본 연구의 실험에 따르면 이 예측 모델은 오차가 약 4% 정도로 거의 정확하게 실제 수행시간을 예측한다. 따라서 이 예측 모델을 사용하면 실제로 소수를 생성하지 않고도 수행시간을 예측하고 거의 정확하게 최적의 테이블 길이를 찾을 수 있다.
Abstract
Public-key cryptosystems use big prime numbers and safe prime numbers for strong security. However, generating big (safe) primes takes a very long time and thus a research for fast generating (safe) primes is important. When incremental search on division tables are used, it is necessary to find the optimal size of division table since the running time of (safe) prime generation depends on the size of division table. However, there is no efficient way to find the optimal size of division table without actual prime generation. In this paper, we propose a probabilistic analysis model to expect the running time of (safe) primes when incremental search on division table are used. Our model predicts the expected running time of generating (safe) primes when the size of division table is given as a parameter. Our experimental results show our model expects actual running time accurately with 4% error. Therefore, with our model, one can predicts the expected running time and the optimal table size very accurately without any actual (safe) prime generation.
- 발행기관:
- 한국차세대컴퓨팅학회
- 분류:
- 컴퓨터학