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개로 , 은 만 수행되었으며, 는 초기에 판별할 수 있었다.