[논문]단계적 소수 판별법

이상운

doi:10.7236/jiibc.2013.13.3.103

단계적 소수 판별법
A Step-by-Step Primality Test 원문보기

한국인터넷방송통신학회 논문지 = The journal of the Institute of Internet Broadcasting and Communication, v.13 no.3, 2013년, pp.103 - 109

이상운 (강릉원주대학교 과학기술대학 멀티미디어공학과)

초록
AI-Helper

대표적인 소수판별법으로 밀러-라빈 방법이 적용되고 있다. 밀러-라빈 판별법은 카마이클 수 또는 반소수가 합성수임에도 불구하고 소수로 잘못 판별하는 단점이 있어 m=[2,n-1], (m,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)로 소수를 판별한다. 본 논문은 m=2로 한정시켜 98.9%를 판별할 수 있는 알고리즘을 제안한다. 제안된 방법은 $n=6k{\pm}1$, $n_1{\neq}5$로 1차로 합성수 여부를 판별한다. 2차에서는 $2^{2^{s-1}d}{\equiv}{\beta}_{s-1}$(mod n)과 $2^d{\equiv}{\beta}_0$(mod n)로 판별하였으며, 3차에서는 ${\beta}_0$ >1이면 $1{\leq}r{\leq}s-2$에서 ${\beta}_r{\equiv}-1$ 존재 여부로, ${\beta}_0=1$이면 m=3,5,7,11,13,17을 순서대로 적용하였다. 제안된 알고리즘을 n=[101,1000]에 적용한 결과 ${\beta}_0$ >1은 26개로 3.0%, ${\beta}_0$ = 1은 0.55%만 수행되었으며, 96.55%는 초기에 판별할 수 있었다.

Abstract ▼ AI-Helper

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 k number of m, whose value satisfies the following : m=[2,n-1], (m,n)=1. The Miller-Rabin method determines that a given number is prime, given that after the computation of $n-1=2^sd$, $0{\leq}r{\leq}s-1$, the outcome satisfies $m^d{\equiv}1$(mod n) or $m^{2^rd}{\equiv}-1$(mod n). This paper proposes a step-by-step primality testing algorithm that restricts m=2, hence achieving 98.8% probability. The proposed method, as a first step, rejects composite numbers that do not satisfy the equation, $n=6k{\pm}1$, $n_1{\neq}5$. Next, it determines prime by computing $2^{2^{s-1}d}{\equiv}{\beta}_{s-1}$(mod n) and $2^d{\equiv}{\beta}_0$(mod n). In the third step, it tests ${\beta}_r{\equiv}-1$ in the range of $1{\leq}r{\leq}s-2$ for ${\beta}_0$ > 1. In the case of ${\beta}_0$ = 1, it retests m=3,5,7,11,13,17 sequentially. When applied to n=[101,1000], the proposed algorithm determined 96.55% of prime in the initial stage. The remaining 3% was performed for ${\beta}_0$ >1 and 0.55% for ${\beta}_0$ = 1.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

왜냐하면 어떠한 수에 대해 밀러-라빈 알고리즘이 판별 오류를 발생시키는지 알려져 있지 않기 때문에 카마 이클 수에 대해 판별을 수행하였다. 또한, 밀러-라빈 방법에 비해 얼마나 빨리 판별을 할 수 있는지 여부에 초점을 두었다. 임의의 수 n을 선택하였을 때 제안된 알고리즘은 n-1 = 2^sd, α = 2, r = 0, r= s -1에 대한 2^₂r_d(mod n) 계산만으로 96.
본 논문에서는 α = 2 로 한정시킨 변형된 밀러-라빈 방법을 제안한다.
본 논문은 α = 2로 한정시킨 변형된 밀러-라빈 소수 판별법을 제안하였다.

제안 방법

다음으로, α = 2로 한정시켜 2d ≡ β0 (mod n)과 22s-1d ≡ βs -1 (mod n)의 2개에 대한 모듈러 지수연산을 수행하여 대부분의 합성수를 제거한다.
과 비교하지는 못하였다. 왜냐하면 어떠한 수에 대해 밀러-라빈 알고리즘이 판별 오류를 발생시키는지 알려져 있지 않기 때문에 카마 이클 수에 대해 판별을 수행하였다. 또한, 밀러-라빈 방법에 비해 얼마나 빨리 판별을 할 수 있는지 여부에 초점을 두었다.
제안된 방법은 사전에 n≠ 6k± 1,(n1 = 1,3,7,9)로 많은 합성수를 제거한다.

대상 데이터

1차 검증 단계에서 n = 6k± 1,n1 ≠ 5만을 대상으로 한다.
제안 알고리즘의 적합성을 검증하기 위해n = [101, 1000]을 대상으로 비교하여 보자. n = [101, 1000]의 900개 수 중에서 소수는 홀수이므로 대상은 450개이다. 홀수 450개 중에서 사전처리 단계로 n = 6k± 1,(n1 = 1,3,7 or9) 를 만족하는 수는 239개로, 211개는 제외된다.
제안 알고리즘의 적합성을 검증하기 위해n = [101, 1000]을 대상으로 비교하여 보자. n = [101, 1000]의 900개 수 중에서 소수는 홀수이므로 대상은 450개이다.

성능/효과

(2) 밀러-라빈 방법은 α을 k개 선택하는데 반해, 제안된 방법은 βs - 1 = β0 = 1인 경우를 제외하면 α= 2로 k = 1이다.
(3) 밀러-라빈 방법은 n-1 = 2s d, 0≤r≤s-1에 대해 s회 수행하는데 반해, 제안된 알고리즘은βr =-1을 찾으면 알고리즘을 종료한다.
(5) 제안된 방법은 s≥2인 βs - 1 = 1, β0 >1에 대해서는 1≤r≤s-2 범위에서 βr =-1이 발생하면 소수로 판정한다.
15개의 카마이클 수에 제안된 알고리즘을 적용한 결과 α = 2에서 14개는 합성수로 판별하였으며, n = 15841에 대해서만 α = 2에서 판별하지 못하고α = 3에서 판별할 수 있었다.
n = [101, 1000]의 900개 수에 제안된 알고리즘을 적용한 결과 Step 1의 n = 6k± 1,(n1 ≠ 5)를 만족하는 239개에 대해서만 알고리즘이 수행되었으며, Step 2의α = 2,r = 0 and r = s -1에서 판별되지 못한 31개 중 26개는 α = 2, 1≤r≤s -2에서, 나머지 5개는β0 = 1, (s > 2)로 α = 3에서 4개, α = 5에서 1개가 판별되었다.
결국, 제안된 알고리즘을 적용할 경우 α = 2, 1 ≤ r≤s -2를 수행하는 비율은 27/900 × 100 = 3.0%이며, α =3은 4/900 × 100 = 0.44%, α = 5는 1/900 ×100 = 0.11%로 α = 3 이상을 수행하는 비율은 0.55% 로 미미함을 알 수 있다.
결론적으로 소수판별법의 성능은 3개 이상의 소인수 들로 합성된 카마이클 수 (carmichael number)를 어떻게 합성수로 판별하는가에 달려 있다.
임의의 수 n을 선택하였을 때 제안된 알고리즘은 n-1 = 2sd, α = 2, r = 0, r= s -1에 대한 22rd(mod n) 계산만으로 96.55%를 판별하였으며, α = 2, 1≤r≤s -2를 수행할 비율은 3.0%, α = 3,5,7,11,13,17에 대해 불만족 수행할 비율은 0.55%에 불과함을 보였다.
제안된 알고리즘을 n = [101, 1000]의 900개 수에 적용한 결과 26개는 α = 2, 1≤r≤s -2에서 27개 (3.0%)를, β0 = 1,(s > 2)의 5개 (0.55%)중 4개는α = 3에서 나머지 1개는 α = 5에서 판별할 수 있었다.

질의응답

핵심어	질문	논문에서 추출한 답변
	소박한 방법은 무엇을 대상으로 하며 그 이유는 무엇인가?	가장 간단한 소박한 방법은 n≡0 (mod α), (2≤α≤ # ,홀수)의 나눗셈 시행법 (trial division)으로 합성수를 결정한다. 이 방법은 α을 정확히 소수들만으로 구하기 어려워 편의상 홀수만을 대상으로 하고 있다. 확률적 방법은 가장 일반적으로 사용되고 있으며, 페르마 (Fermat), Lucas, SolovayStrassen, 밀러-라빈 (Miller-Rabin) 방법 등이 있다.
	소수 판별법에는 어떤 방법들이 있는가?	소수 판별법에는 소박한 방법 (naïve PT), 확률적 방법 (probabilistic PT)과 결정론적 방법 (deterministic PT)이 적용되고 있다. 가장 간단한 소박한 방법은 n≡0 (mod α), (2≤α≤ # ,홀수)의 나눗셈 시행법 (trial division)으로 합성수를 결정한다.
	소박한 방법이란?	소수 판별법에는 소박한 방법 (naïve PT), 확률적 방법 (probabilistic PT)과 결정론적 방법 (deterministic PT)이 적용되고 있다. 가장 간단한 소박한 방법은 n≡0 (mod α), (2≤α≤ # ,홀수)의 나눗셈 시행법 (trial division)으로 합성수를 결정한다. 이 방법은 α을 정확히 소수들만으로 구하기 어려워 편의상 홀수만을 대상으로 하고 있다.

참고문헌 (9)

D. Zagier, "Newman's Short Proof of the Prime Number Theorem," American. Mathematical. Monthly, Vol. 104, No. 8, pp. 705-708, 1997.

상세보기
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, "Introduction to Algorithms," 2nd Ed., MIT Press and McGraw-Hill. pp. 887-896, 2001.
R. D. Carmichael, "On composite numbers which satisfy the Fermat congruence $\alpha^{P-1}{\equiv}1 $ mod P ," American Mathematical Monthly, Vol. 19, No. 2, pp. 22-27, 1912.

상세보기
M. E. O'Neill, "The Genuine Sieve of Eratosthenes," Journal of Functional Programming, Cambridge University Press, 2008.
P. Ribenboim, "The New Book of Prime Number Records (3rd ed.)," New York: Springer-Verlag, 1995.
M. O. Rabin, "Probabilistic algorithm for testing primality," Journal of Number Theory, Vol. 12, No. 1, pp. 128-138, 1980.

상세보기
C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, "The Pseudoprimes to 25.109", Mathematics of Computation, Vol.35, No. 151, pp. 1003-1026, 1980.
G. Jaeschke, "On strong pseudoprimes to several bases," Mathematics of Computation, Vol. 61, No. 204, pp. 915-926, 1993.

상세보기
S. U. Lee and M. B. Choi, "The Integer Factorization Method Based on Congruence of Squares," Journal of Korean Institute of Information Technology, Vol. 12, No. 5, pp. 185-189, Oct. 2012.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

단계적 소수 판별법
A Step-by-Step Primality Test 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

제안 방법

대상 데이터

성능/효과

질의응답

참고문헌 (9)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

단계적 소수 판별법 A Step-by-Step Primality Test 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

대상 데이터

성능/효과

질의응답

참고문헌 (9)

이 논문을 인용한 문헌

저자의 다른 논문 :

이상운 (190)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

단계적 소수 판별법
A Step-by-Step Primality Test 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper