Earticle

초록

영어

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 .

한국어

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

목차

요약
 Abstract
 Ⅰ. 서론
 Ⅱ. 소수 판별법
 Ⅲ. 단계적 소수 판별 알고리즘
 Ⅳ. 실험 및 결과 분석
 Ⅴ. 결론
 Reference

키워드

저자

• 이상운 [ Sang-Un Lee | 정회원, 강릉원주대학교 과학기술대학 멀티미디어공학과 ] Corresponding Author

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국인터넷방송통신학회 논문지 [The Journal of the Institute of Internet, Broadcasting and Communication]

• 간기

  격월간

• pISSN

  2289-0238

• eISSN

  2289-0246

• 수록기간

  2001~2025

• 십진분류

  KDC 326 DDC 380