- 소수 판별법
- ㆍ 저자명
- 이상운,최명복,Lee. Sang-Un,Choi. Myeong-Bok
- ㆍ 간행물명
- 韓國컴퓨터情報學會論文誌
- ㆍ 권/호정보
- 2011년|16권 8호|pp.103-108 (6 pages)
- ㆍ 발행정보
- 한국컴퓨터정보학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
대표적인 소수판별법으로 밀러-라빈방법이 적용되고 있다. 밀러-라빈판별법은 m=[2, n-1]에서 m을 k개 선택하여 n-1=$2^sd$, $0;{leq};r;{leq};s-1$ 에 대해 $m^d;{equiv};1(mod;n)$ 또는 $m^{2^rd};{equiv};-1(mod n)$로 소수를 판별하여 $k{ imes}r$회를 수행한다. 본 논문은 c=$p^{frac{n-1}{2}}(mod;n)$을 계산하여 c=-1이면 소수로 판별하여 k회 수행하였다. 제안된 판별법은 밀러-라빈 판별법의 $k{ imes}r$회를 k회로 감소시켰다.
Generally, Miller-Rabin method has been the most popular primality test. This method arbitrary selects m at k-times from m=[2, n-1] range and (m,n)=1. Miller-Rabin method performs $k{ imes}r$ times and reports prime as $m^d;{equiv};1(mod;n)$ or $m^{2^rd};{equiv};-1(mod n)$ such that n-1=$2^sd$, $0;{leq};r;{leq};s-1$. This paper suggests more simple primality test than Miller-Rabin method. This test method computes c=$p^{frac{n-1}{2}}(mod;n)$ for k times and reports prime as c=-1. The proposed primality test method reduces $k{ imes}r$ times of Miller-Rabin method to k times.