Earticle

대표적인 소수판별법으로 밀러-라빈 방법이 적용되고 있다. 밀러-라빈 판별법은 카마이클 수 또는 반소수가 합성수임에도 불구하고 소수로 잘못 판별하는 단점이 있어 , 인 을 개 선택하여 소수 여부를 판별한다. 밀러-라빈 방법은 에 대해 또는 로 소수를 판별한다. 본 논문은 로 한정시켜 를 판별할 수 있는 알고리즘을 제안한다. 제안된 방법은 로 1차로 합성수 여부를 판별한다. 2차에서는 과 로 판별하였으며, 3차에서는 이면 에서 존재 여부로, 이면 을 순서대로 적용하였다. 제안된 알고리즘을 에 적용한 결과 은 26개로 , 은 만 수행되었으며, 는 초기에 판별할 수 있었다.

Miller-Rabin method is the most prevalently used primality test. However, this method mistakenly reports a Carmichael number or semi-prime number as prime (strong lier) although they are composite numbers. To eradicate this problem, it selects number of , whose value satisfies the following : , . The Miller-Rabin method determines that a given number is prime, given that after the computation of , the outcome satisfies or . This paper proposes a step-by-step primality testing algorithm that restricts , hence achieving 98.8% probability. The proposed method, as a first step, rejects composite numbers that do not satisfy the equation, . Next, it determines prime by computing and . In the third step, it tests in the range of for . In the case of , it retests sequentially. When applied to , the proposed algorithm determined 96.55% of prime in the initial stage. The remaining 3% was performed for and 0.55% for .

IoT 기반의 초연결사회가 되어감에 따라 암호, 인증, 전자서명 등을 위해 RSA와 같은 공개키암호시스템이 빈번하게 사용되고 있다. 공개키암호시스템은 악의적인 공격으로부터 보안성을 확보하기 위해 크기가 매우 큰 (안전)소수를 사용하는데 기기의 성능이 크게 발전하였음에도 불구하고 크기가 큰 (안전)소수생성은 수행시간이 오래 걸리거나 메모리를 많이 요구하는 작업이다. 본 논문에서는 수행시간과 사용공간의 효율을 높이기 위해 오일러체(Euler sieve)를 사용하는 ET-MR 소수검사법과 ET-MR-MR 안전소수검사법을 제안한다. 제안한 검사법을 확률적으로 분석한 수행시간 예측 모델을 제안하고 기존 방법들과 수행시간, 메모리 사용량을 비교하였다. 실험결과, 이론적 예측시간과 실제 수행시간의 차이는 거의 없었으며(4%미만) 각 알고리즘이 가장 빠를 때의 수행시간을 비교하면 ET-MR이 TD-MR보다 34.5%, DT-MR보다 8.5% 더 빨랐으며, ET-MR-MR이 TD-MR-MR보다 65.3% 더 빨랐고, DT-MR-MR과는 비슷하였다. 공간의 경우 k=12,381일 때 ET-MR이 DT-MR보다 약 2.7배 더 사용했지만 TD-MR보다 98.5% 더 적게 사용하였고 k=65,536일 때 ET-MR-MR이 TD-MR-MR 보다 98.4%, DT-MR-MR보다 92.8% 더 적게 사용하였다.

As the IoT-based hyper-connected society grows, public-key cryptosystem such as RSA is frequently used for encryption, authentication, and digital signature. Public-key cryptosystem use very large (safe) prime numbers to ensure security against malicious attacks. Even though the performance of the device has greatly improved, the generation of a large (safe)prime is time-consuming or memory-intensive. In this paper, we propose ET-MR and ET-MR-MR using Euler sieve so it runs faster while using less memory. We present a running time prediction model by probabilistic analysis and compare time and memory of our method with conventional methods. Experimental results show that the difference between the expected running time and the measured running time is less than 4%. In addition, the fastest running time of ET-MR is 36% faster than that of TD-MR, 8.5% faster than that of DT-MR and the fastest running time of ET-MR-MR is 65.3% faster than that of TD-MR-MR and similar to that of DT-MR-MR. When k=12,381, the memory usage of ET-MR is 2.7 times more than that of DT-MR but 98.5% less than that of TD-MR and when k=65,536, the memory usage of ET-MR-MR is 98.48% less than that of TD-MR-MR and 92.8% less than that of DT-MR-MR.

본 논문에서는 현재 사용되고 있는 소수성 검정 알고리즘의 효율성을 비교하여 효과적인 알고리즘 사용에 관한 방향을 제시하려 한다. 현재 가장 일반적으로 사용하고 있는 Miller-Rabin 소수성검정법(Miller-Rabin primality test)에 대하여, Miller-Rabin 소수성 검정법 이외에 다른 확률적 소수성 검정법으로 제안된 Frobenius-Grantham 소수성 검정법(Frobenius-Grantham primality test) 이 있다. 그러나 합성수 판별에 대한 확률적 우세함에도 불구하고, Miller-Rabin 소수성 검정법을 대체하고 있지 못하는 이유는 시간복잡도(time complexity)가 Randomized polynomial time이기 때문에 같은 확률에 대한 평균 실행 속도가 Miller-Rabin 소수성 검정법보다 크게 효율적이지 못하기 때문이다. 또한, 2002년 Manindra Agrawal이 제시한 AKS 알고리즘(AKS algorithm)은 최초의 다항식 시간내 결정적 소수성 검정법(Polynomial time deterministic primality test)이지만, 시간 복잡도에서 다항식의 차수가 높기 때문에 현재 사용되고 있는 확률적 소수성 검정법(Probabilistic primality test)을 대체하지 못할 것으로 사료된다. 본 논문에서는 최근 발표된 소수성 검정법인 Frobenius-Grantham 소수성 검정법, AKS 알고리즘과 기존의 Miller-Rabin 소수성 검정법의 장단점을 비교·분석해 보고자 한다.

큰 소수를 빠르게 생성하기 위한 다양한 소수 검사 방법이 개발되었으며, 가장 많이 쓰이는 소수 검사 방법은 trial division과 Fermat (또는 Miller-Rabin) 검사를 조합한 방법과 gcd 연산과 Fermat (또는 Miller-Rabin) 검사를 조합한 방법이다. 이 중 trial division과 조합한 방법에 대해서는 확률적 분석을 이용하여 수행시간을 예측하고 수행시간을 최적화 하는 방법이 개발되었다. 하지만, gcd 연산과 조합한 방법에 대해서는 아무런 연구결과도 제시되어 있지 않다. 본 논문에서는 gcd 연산을 이용한 조합 소수 검사 방법에 대해 확률적 분석을 이용하여 수행시간을 예측하고 수행시간을 최적화 하는 방법을 제안한다.

이 논문에서는 먼저 소수성 시험 알고리즘의 기본 개념이 되는 Fermat 의 정리를 살펴본다. 그리고, 가장 널리 사용되고 구현이 용이한 소수성 시험 알고리즘인 Rabin-Miller 및 Rivest 알고리즘을 살펴보고, 이들 알고리즘의 수행 시간을 분석한다. 또한, Rivest 가 제시한 연구 결과를 바탕으로 소수성시험 방법의 수행성능 향상 방안을 고려함으로써, Rivest 알고리즘을 효율적으로 구현하여 암호 시스템 등의 응용에 적용할 수 있도록 개선 방안을 제시한다.