로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.스팸 방지 검사입니다. 이것을 입력하지 마세요!'''뤼카-레머-리젤 소수판정법'''(Lucas-Lehmer-Riesel primality test)은 <math>N=k\cdot 2^n-1, k<2^n</math> 형태의 자연수의 [[소수 (정수)|소수]] 여부를 알아내는 소수판정법이다. [[뤼카-레머 소수판정법]]의 확장판으로, 해당 판정법을 [[메르센 수]]에서 범위를 넓힌 것이다. 한스 리젤(Hans Riesel)이 기존 뤼카-레머 방식을 개량하였다. == 진술 == 이 소수판정법에서는 일반화된 [[뤼카 수열]] 중 <math>V_n(P, 1)</math>을 이용한다. 이 수열은 <math>V_0=2, V_1=P, V_n=PV_{n-1}-V_{n-2}</math>로 정의되며, 본 문서에서는 초기 조건을 어떻게 결정하는 지에 초점을 둔다. 소수 여부를 알아볼 자연수 <math>N=k\cdot 2^n-1</math>이 주어지고 <math>k</math>는 <math>2^n</math>보다 작은 홀수이다. 상수 <math>P</math>는 [[야코비 기호]]의 조건으로 <math>\left(\frac{P-2}{N} \right)=1, \left(\frac{P+2}{N} \right)=-1</math>을 만족한다. 그 다음 알고리즘에 사용할 수열을 정의한다. :<math>r_m=\begin{cases}V_k &\text{if } m=1 \\ r_{m-1}^2-2 &\text{otherwise} \end{cases}</math> 이때 <math>r_{n-1} \equiv 0 \pmod N</math>이면 <math>N</math>은 소수이고, 그렇지 않으면 합성수이다. == 증명 == 진술과 증명 과정은 다루는 값만 다를 뿐 [[뤼카-레머 소수판정법]]과 아주 흡사하다. 먼저 [[뤼카 수열]]의 항은 <math>V_n(P, 1)=a^n+a^{-n}, a=\frac{P+\sqrt{P^2-4}}{2}</math>와 같이 풀 수 있다. 아울러 <math>r_1=a^k+a^{-k}</math>이고, 진술의 점화관계식을 풀면 <math>r_m=a^{2^{m-1}k}+a^{-2^{m-1}k}</math>이다. 즉 진술의 합동식에 대입하면 <math>a^{2^{n-2}k}+a^{-2^{n-2}k} \equiv 0 \pmod N</math>(☆)이다. === 필요조건 === 아래 모든 연산은 [[환 (수학)|환]] <math>X=\{a+b\sqrt{D}|a,b \in \mathbb{Z}/N\mathbb{Z} \} (D=P^2-4)</math> 내에서 이루어진다. 즉 <math>a+b\sqrt{D} \equiv c+d\sqrt{D} \pmod N</math>은 <math>a \equiv c, b \equiv d \pmod N</math>를 의미한다. <math>N</math>이 소수라 가정하고 (☆) 합동식을 이끌어낸다. 진술에서 쓴 야코비 기호는 [[르장드르 기호]]가 되며, [[오일러의 규준]]에 의해 <math>(P-2)^{\frac{N-1}{2}} \equiv 1, (P+2)^{\frac{N-1}{2}} \equiv -1 \pmod N</math>이다. 위 문단의 식을 불러오면 <math>4a=2P+2\sqrt{P^2-4}=(\sqrt{P+2}+\sqrt{P-2})^2</math>이다. 이 식의 양 변을 <math>\frac{N+1}{2}</math>제곱하면 <math>2^{N+1}a^{\frac{N+1}{2}}=(\sqrt{P+2}+\sqrt{P-2})^{N+1}</math>이고, 각 항은 아래와 같이 정리된다. :<math>a^{\frac{N+1}{2}}=a^{2^{n-1}k}</math> :<math>2^{N+1}=2^{N-1}\cdot 4 \equiv 4 \pmod N</math> ←[[페르마의 소정리]] :<math>(\sqrt{P-2}+\sqrt{P+2})^{N+1}=(\sqrt{P-2}+\sqrt{P+2})^N (\sqrt{P-2}+\sqrt{P+2})</math> :<math>(\sqrt{P-2}+\sqrt{P+2})^N=\sum_{j=0}^{N}\binom{N}{j}(\sqrt{P+2})^{j}(\sqrt{P-2})^{N-j} \equiv (\sqrt{P+2})^N+(\sqrt{P-2})^N \pmod N</math> <ref><math>0<j<N</math>이면 <math>N \mid \binom{N}{j}</math>임을 이용</ref> :<math>(\sqrt{P-2})^N=(P-2)^{\frac{N-1}{2}}\sqrt{P-2} \equiv \sqrt{P-2} \pmod N</math> :<math>(\sqrt{P+2})^N=(P+2)^{\frac{N-1}{2}}\sqrt{P+2} \equiv -\sqrt{P+2} \pmod N</math> :<math>(\sqrt{P-2}+\sqrt{P+2})^N \equiv \sqrt{P-2}-\sqrt{P+2} \pmod N</math> :<math>(\sqrt{P-2}+\sqrt{P+2})^{N+1} \equiv (\sqrt{P-2}+\sqrt{P+2})(\sqrt{P-2}-\sqrt{P+2}) \equiv -4 \pmod N</math> 이상 정리된 항들을 원래 식에 대입하면 <math>4a^{2^{n-1}k} \equiv -4 \pmod N</math>이다. 양 변을 4로 나누고 <math>a^{-2^{n-2}k}</math>을 곱하면 <math>a^{2^{n-2}k} \equiv -a^{-2^{n-2}k} \pmod N</math>이며, 우변을 이항하면 유도하고자 하는 (☆) 합동식이 성립함을 알 수 있다. === 충분조건 === (☆) 합동식이 성립한다고 가정하고, <math>N</math>이 소수임을 이끌어낸다. 만약 홀수 <math>N</math>이 소수가 아니면 <math>q \mid N, q(q+2) \leq N</math>인 홀수 소인수 <math>q</math>가 존재한다.<ref><math>q^2 \leq N</math>이 아닌 이유는 해당 자연수는 제곱수가 될 수 없기 때문이다. 제곱수가 아닌 이유는 아래 '초깃값 구하기' 문단 참고.</ref> (☆) 합동식을 변형하면 <math>a^{2^{n-1}k} \equiv -1 \pmod q</math>이다. <math>q</math>가 원래 수의 약수이므로 합동식의 법을 이렇게 바꿔 쓸 수 있다. 양 변을 제곱하면 <math>a^{2^n k} \equiv 1 \pmod q</math>이다. <math>\lambda</math>를 <math>a^{\lambda} \equiv 1 \pmod q</math>를 만족하는 최소 차수라고 하면 <math>\lambda \mid 2^n k, \lambda \nmid 2^{n-1}k</math>이어야 하므로 <math>\lambda=2^n k'</math>이다. 단, <math>k' \mid k</math> 한편 <math>2a=P+\sqrt{P^2-4}</math>의 양 변을 <math>q</math>제곱하면 <math>(2a)^q \equiv P^q+(P^2-4)^{\frac{q-1}{2}}\sqrt{P^2-4} \pmod q</math>이다. 우변의 경우, 진술에서 쓴 야코비 기호 값은 <math>P-2, P+2 \nmid N</math>을 뜻하고, 이에 따라 <math>P^2-4 \nmid q, \left(\frac{P^2-4}{q} \right)= \pm 1</math>을 알 수 있다. 또한 페르마의 소정리에 의해 <math>2^q \equiv 2, P^q \equiv P \pmod q</math>이고, 위 식을 정리하면 <math>2a^q \equiv P \pm \sqrt{P^2-4} \pmod q</math>이다. 합동식의 우변은 <math>2a^{\pm 1}</math>과 같으므로, <math>a^{q-1} \equiv 1 \pmod q</math> 또는 <math>a^{q+1} \equiv 1 \pmod q</math>이다. 따라서 <math>\lambda \mid q-1</math> 또는 <math>\lambda \mid q+1</math>이므로 <math>\lambda=2^n k' \leq q+1</math>이며, <math>q \geq 2^n k'-1 \geq 2^n-1, q+2 \geq 2^n+1</math>이다. 두 부등식을 곱하면 <math>q(q+2) \geq (2^n)^2-1</math>이다. 또, 처음 가정인 <math>k<2^n</math>을 불러오면 <math>q(q+2)>k \cdot 2^n-1=N</math>이다. 하지만 이는 앞서 가정했던 <math>q(q+2) \leq N</math>과 모순이다. 그러므로 <math>N</math>은 소수이다. 참고로 <math>k<2^n</math>이라는 특수한 조건은 [[프로트의 정리]]에서도 귀류법으로 증명할 때 쓰인다. == 초깃값 구하기 == 이번에는 진술에서 언급한 식인 <math>\left(\frac{P-2}{N} \right)=1, \left(\frac{P+2}{N} \right)=-1</math>을 만족하는 <math>P</math>와 초깃값 <math>r_1=V_k(P, 1)</math>을 구할 차례이다. <math>n=1</math>인 경우 <math>k<2^n</math>으로부터 <math>k=1, N=1</math>만 가능하며 이는 관심의 대상이 아니다. 그러므로 <math>n \geq 2</math>라는 전제를 깔고, 그러면 <math>N \equiv 3 \pmod 4</math>가 된다. 즉 <math>N</math>은 제곱수가 아니다. * <math>3 \nmid k</math>인 경우, <math>N \equiv 0 \text{ or }1 \pmod 3 </math>이다. 3의 배수는 3을 제외하고 모두 합성수이므로, 3으로 나눈 나머지가 1인 경우만을 생각한다. 이 경우 <math>P=4</math>로 두면 된다. ** <math>k=1</math>이면 <math>N=2^n-1</math>로 [[메르센 수]]가 된다. 그리고 이 값을 3으로 나눈 나머지가 1이라면 <math>n</math>은 홀수이므로 <math>n \geq 3</math>이며, <math>N \equiv 7 \pmod 8, N \equiv 7 \pmod{24}</math>가 되어 <math>\left(\frac{2}{N} \right)=1, \left(\frac{6}{N} \right)=-1</math>을 만족한다. 또, <math>r_1=V_1(4, 1)=4</math>이며, 이는 곧 [[뤼카-레머 소수판정법]]이 된다. ** <math>k \geq 5</math>이면 <math>2^n>5, n \geq 3</math>이므로 바로 위와 똑같이 야코비 기호의 조건을 만족한다. 초깃값은 <math>r_1=V_k(4, 1)=(2+\sqrt{3})^k+(2-\sqrt{3})^k</math> * <math>k=3</math>인 경우, <math>n \equiv 1 \pmod 4</math>이면 <math>2^n \equiv 2 \pmod 5</math>이므로 <math>N \equiv 0 \pmod 5</math>이다. 즉 5를 제외하고 모두 합성수이므로, 관심의 대상이 아니다. <math>n \equiv 0 \text{ or }3 \pmod 4</math>이면 마찬가지 방법으로 <math>N \equiv 2 \text{ or }3 \pmod 5</math>이므로 야코비 기호의 값은 <math>\left(\frac{5}{N} \right)=\left(\frac{20}{N} \right)=-1</math>이다. 또, 16은 제곱수이므로 <math>\left(\frac{16}{N} \right)=1</math>인데, 두 식을 토대로 <math>P=18, r_1=V_3(18, 1)=5778</math>로 두면 된다. * 그 밖에 <math>k>3</math>이거나 <math>k=3, n \equiv 2 \pmod 4</math>이면 <math>P</math>와 그에 대응하는 야코비 기호 식은 또다른 값을 가진다. == 기타 == 이 소수판정법은 큰 [[쌍둥이 소수]]를 찾는 데 유용하다. 즉 <math>N=k \cdot 2^n \pm 1, k<2^n</math>의 형태에서, (+) 부호는 [[프로트의 정리]]로, (-)부호는 본 문서의 알고리즘으로 소수 여부를 규명해낸다. 그렇게 해서 두 수 모두 소수가 맞으면 쌍둥이 소수가 된다. {{각주}} {{수론 알고리즘}} [[분류:알고리즘]] 요약: 리브레 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 3.0 라이선스로 배포됩니다(자세한 내용에 대해서는 리브레 위키:저작권 문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요. 글이 직접 작성되었거나 호환되는 라이선스인지 확인해주세요. 리그베다 위키, 나무위키, 오리위키, 구스위키, 디시위키 및 CCL 미적용 사이트 등에서 글을 가져오실 때는 본인이 문서의 유일한 기여자여야 하고, 만약 본인이 문서의 유일한 기여자라는 증거가 없다면 그 문서는 불시에 삭제될 수 있습니다. 취소 편집 도움말 (새 창에서 열림) | () [] [[]] {{}} {{{}}} · <!-- --> · [[분류:]] · [[파일:]] · [[미디어:]] · #넘겨주기 [[]] · {{ㅊ|}} · <onlyinclude></onlyinclude> · <includeonly></includeonly> · <noinclude></noinclude> · <br /> · <ref></ref> · {{각주}} · {|class="wikitable" · |- · rowspan=""| · colspan=""| · |} {{lang|}} · {{llang||}} · {{인용문|}} · {{인용문2|}} · {{유튜브|}} · {{다음팟|}} · {{니코|}} · {{토막글}} {{삭제|}} · {{특정판삭제|}}(이유를 적지 않을 경우 기각될 가능성이 높습니다. 반드시 이유를 적어주세요.) {{#expr:}} · {{#if:}} · {{#ifeq:}} · {{#iferror:}} · {{#ifexist:}} · {{#switch:}} · {{#time:}} · {{#timel:}} · {{#titleparts:}} __NOTOC__ · __FORCETOC__ · __TOC__ · {{PAGENAME}} · {{SITENAME}} · {{localurl:}} · {{fullurl:}} · {{ns:}} –(대시) ‘’(작은따옴표) “”(큰따옴표) ·(가운뎃점) …(말줄임표) ‽(물음느낌표) 〈〉(홑화살괄호) 《》(겹화살괄호) ± − × ÷ ≈ ≠ ∓ ≤ ≥ ∞ ¬ ¹ ² ³ ⁿ ¼ ½ ¾ § € £ ₩ ¥ ¢ † ‡ • ← → ↔ ‰ °C µ(마이크로) Å °(도) ′(분) ″(초) Α α Β β Γ γ Δ δ Ε ε Ζ ζ Η η Θ θ Ι ι Κ κ Λ λ Μ μ(뮤) Ν ν Ξ ξ Ο ο Π π Ρ ρ Σ σ ς Τ τ Υ υ Φ φ Χ χ Ψ ψ Ω ω · Ά ά Έ έ Ή ή Ί ί Ό ό Ύ ύ Ώ ώ · Ϊ ϊ Ϋ ϋ · ΐ ΰ Æ æ Đ(D with stroke) đ Ð(eth) ð ı Ł ł Ø ø Œ œ ß Þ þ · Á á Ć ć É é Í í Ĺ ĺ Ḿ ḿ Ń ń Ó ó Ŕ ŕ Ś ś Ú ú Ý ý Ź ź · À à È è Ì ì Ǹ ǹ Ò ò Ù ù · İ Ż ż ·  â Ĉ ĉ Ê ê Ĝ ĝ Ĥ ĥ Î î Ĵ ĵ Ô ô Ŝ ŝ Û û · Ä ä Ë ë Ï ï Ö ö Ü ü Ÿ ÿ · ǘ ǜ ǚ ǖ · caron/háček: Ǎ ǎ Č č Ď ď Ě ě Ǐ ǐ Ľ ľ Ň ň Ǒ ǒ Ř ř Š š Ť ť Ǔ ǔ Ž ž · breve: Ă ă Ğ ğ Ŏ ŏ Ŭ ŭ · Ā ā Ē ē Ī ī Ō ō Ū ū · à ã Ñ ñ Õ õ · Å å Ů ů · Ą ą Ę ę · Ç ç Ş ş Ţ ţ · Ő ő Ű ű · Ș ș Ț ț 이 문서에서 사용한 틀: 틀:Skin (원본 보기) (준보호됨)틀:각주 (원본 보기) (준보호됨)틀:둘러보기 상자 (원본 보기) (보호됨)틀:둘러보기 상자/핵심 (원본 보기) (보호됨)틀:수론 알고리즘 (편집) 틀:틀바 (원본 보기) (준보호됨)