로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.스팸 방지 검사입니다. 이것을 입력하지 마세요!'''토넬리-섕크스 알고리즘'''(Tonelli–Shanks algorithm)은 [[모듈러산술]]에서 홀수 소수를 법으로 하는 이차합동식 <math>x^2 \equiv a \pmod p</math>의 해, 즉 [[모듈러 제곱근]]을 구하는 방법이다. 주어진 소수 <math>p</math>에 대해 <math>p-1</math>이 8의 배수일 때 이 알고리즘을 이용하면 모듈러 제곱근을 손쉽게 구할 수 있다. == 아이디어 == 먼저 홀수 소수는 <math>p=2^mq+1</math>의 꼴로 나타낼 수 있다. 여기서 <math>q</math>는 홀수이고, 2의 지수 <math>m</math>은 유일하게 정해진다. <math>1 \leq b \leq p</math>인 어떤 자연수가 법 <math>p</math>에 대한 이차비잉여이면 <math>b^{p-1} \equiv 1, b^{\frac{p-1}{2}} \equiv -1 \pmod p</math>이다. <math>c=b^q \mod p</math>이라 하면 <math>c^{2^m} \equiv 1, c^{2^{m-1}} \equiv -1 \pmod p</math>이므로 <math>\operatorname{ord}_p c=2^m</math>이다. 한편 <math>1 \leq a \leq p</math>인 임의의 자연수에 대해 <math>(a^q)^{2^m} \equiv 1 \pmod p</math>이므로 <math>\operatorname{ord}_p a^q \mid 2^m</math>이며, <math>a^q \equiv c^r \pmod p, 0 \leq r < 2^m</math>인 <math>r</math>이 반드시 하나 존재한다. 만약 운이 좋은 경우로 <math>r=0, a^q \equiv 1 \pmod p</math>이라면 <math>x^2 \equiv a \pmod p</math>의 해는 <math>x \equiv \pm a^{\frac{q+1}{2}} \pmod p</math>으로 바로 나온다. 물론 실제로는 상당한 확률로 <math>r \neq 0</math>인데, <math>a^q \mod p</math>에서 출발하는 <math>t</math>를 변형하여 이 값이 1에 도달하도록 알고리즘을 세울 것이다. 먼저 위에서 구한 <math>c=b^q \mod p</math>으로부터 <math>O=\{x: x \equiv c^r \pmod p, 0 \leq r< 2^m \} \subset \mathbb{Z}/n\mathbb{Z}</math>를 정의한다. 즉 <math>O=\{1, c, c^2, \cdots c^{2^m-1} \}</math>와 같이 써지고, 이제 이 집합을 법 <math>p</math>에 대한 [[위수 (정수론)|위수]] 별로 쪼갠다. * 정의: <math>A_k=\{x: x \in O, \operatorname{ord}_n x=2^k \}, 0 \leq k \leq m</math> * <math>A_m=\{c, c^3, c^5, \cdots c^{2^m-1} \}</math> * <math>A_{m-1}=\{c^2, c^6, c^{10}, \cdots c^{2^m-2} \}</math> * <math>A_{m-2}=\{c^4, c^{12}, c^{20}, \cdots c^{2^m-4} \}</math> * 이렇게 나아가서 <math>A_2=\{c^{2^{m-2}}, c^{3\cdot 2^{m-2}} \}, A_1=\{c^{2^{m-1}} \}, A_0=\{1\}</math>까지 도달한다. * <math>O=A_0 \cup A_1 \cup A_2 \cdots \cup A_m, A_k \cap A_{k'} =\emptyset \text { for } k \neq k'</math> 가령 <math>t \in O</math>인 원소에 대해 <math>t \in A_k</math>이면 <math>t^2 \in A_{k-1}, t^4 \in A_{k-2}, \cdots t^{2^k} \in A_0</math>임을 알 수 있다. 또, <math>t \equiv c^r \pmod p</math>에 대해 <math>2^{m-k} \mid r, 2^{m-k+1} \nmid r</math>이다. 그렇다면 만약 <math>r'=r+2^{m-k}, t'=c^{r'}=tc^{2^{m-k}} \mod p</math>을 새로 정의하면 <math>2^{m-k+1} \mid r'</math>이므로 <math>\operatorname{ord}_n t'=2^{k'} \mid 2^{k-1}, t' \in A_{k'}, k'<k</math>라 할 수 있고, 이것이 알고리즘의 단서가 된다. * 먼저 <math>t=a^q \mod p</math>에서 출발하여 이 값이 <math>A_k</math> 중 어느 집합의 원소인지 알아본다. 즉 <math>t^{2^k} \equiv 1 \pmod p</math>인 최소 <math>k</math>를 찾으면 된다. * 그 다음 <math>t'=tc^{2^{m-k}}</math>을 셈하고 이 새로운 값이 어느 집합의 원소인지를 다시 찾는다. 이러한 변형을 반복하면 <math>A_0</math>의 원소인 1에 수렴한다. == 알고리즘 == 구체화된 알고리즘은 아래와 같이 진행한다. * <math>p-1=2^m q</math>를 만족하는 홀수 <math>q</math>와 2의 지수 <math>m</math>을 구한다. * <math>1<b<p, \left(\frac{b}{n}\right)=-1</math>인 자연수를 아무거나 잡고 <math>c=b^q \mod p</math>를 셈한다. * 변수 네 개를 지정한다: <math>M \leftarrow m, y \leftarrow c, t \leftarrow a^q \mod p, x \leftarrow a^{\frac{q+1}{2}}</math> * (※) <math>t=1</math>이면 알고리즘은 여기서 끝나고, <math>\pm x</math>를 반환한다. * <math>t \neq 1</math>이면 제곱을 반복해서 <math>t^{2^k} \equiv 1 \pmod p</math>인 최소 <math>k</math>를 찾는다. * 보조 변수 <math>s \leftarrow y^{2^{M-k-1}} \mod p</math>를 셈하고 앞서 세운 변수의 값들을 갱신한다. ** <math>M \leftarrow k, y \leftarrow s^2, t \leftarrow s^2t, x \leftarrow sx</math> 다음 (※) 지점으로 돌아간다. === 참고 사항 === 만약 <math>p-1</math>이 8의 배수가 아니면 두 경우로 나누어서 풀이과정을 단순화할 수 있다. * <math>p \equiv 3 \pmod 4 \Rightarrow x \equiv \pm a^{\frac{n+1}{4}} \pmod p</math> * <math>p \equiv 5 \pmod 8 \Rightarrow x \equiv \pm aj(2aj^2-1) \pmod p, j \equiv (2a)^{\frac{n-5}{8}} \pmod p</math> == 적용 예 == <math>x^2 \equiv 89 \pmod{97}</math>은 아래와 같이 푼다. 첫 단계로 <math>97=2^m q+1, q=3, m=5</math>를 찾는다. 그 다음 법 97에 대한 이차비잉여를 하나 찾는다. 97을 5로 나눈 나머지가 2라는 점에서 5는 이차비잉여임을 알 수 있다. 즉 <math>\left(\frac{5}{97}\right)=-1</math> 해가 나올때까지 알고리즘은 아래와 같이 진행된다. p=97, a=89, q=3, m=5, b=5 c=b**q %n ##c=28 M=m, y=c, t=a**q %n, x=a**((q+1)/2) %n ##M=5, y=28, t=70, x=64 t!=1: t**2 %p==50, t**4 %p==75, t**8 %p==96, t**16 %n ==1 -> k=4 r=M-k-1 ##r=0 s=y**(2**r) %p ##s=28 M=k, y=s**2 %p, t=(s**2)*t %p, x=s*x %p ##M=4, y=8, t=75, x=46 t!=1: t**2 %p==96, t**4 %n==1 -> k=2 r=M-k-1 ##r=1 s=y**(2**r) %p ##s=64 M=k, y=s**2 %n, t=(s**2)*t %p, x=s*x %p ##M=2, y=22, t=1, x=34 t==1: return x 이렇게 해서 <math>x \equiv \pm 34 \pmod{97}</math>을 얻는다. 이 과정은 아래와 같이 전개된다: * [[페르마의 소정리]]에 의해 <math>b^{96} \equiv c^{32} \equiv 1 \pmod{97}</math>이다. * <math>a=89 \equiv b^{22}, t_1=70 \equiv a^3 \equiv c^{22}, x_1=64 \equiv b^{44} \pmod{97}</math>에서 출발한다. 이때 <math>t_1</math>에 대응하는 <math>c</math>의 지수가 4의 배수가 아닌 2의 배수이므로, <math>t_1 \in A_4, k_1=4</math>이다. * <math>t_2=t_1c^2 \mod{97}</math>는 우변의 <math>c</math>의 지수가 4의 배수가 되도록 맞추는 식이다. 이를 위해 <math>y_1=c, s_1=y_1^{2^0}=c=b^3</math>을 대입하고 <math>t_2=t_1s_1^2 \mod{97}, x_2=s_1x_1 \mod{97}</math>를 셈한다. * <math>t_2=75 \equiv c^{24}, x_2=46 \equiv b^{47} \pmod{97}</math>이다. 이번에는 <math>c</math>의 지수가 8의 배수이므로 <math>t_2 \in A_2, k_2=2</math>가 나왔다. * 그렇다면 이번에는 <math>t_3=t_2c^8 \mod{97}</math>을 계산해서 지수를 16의 배수로 맞춘다. 이를 위해 <math>y_2=s_1^2=c^2, s_2=y_2^{2^1}=c^4=b^{12}</math>을 대입하고 <math>t_3=t_2s_2^2 \mod{97}, x_3=s_2x_2 \mod{97}</math>를 셈한다. * <math>t_3=1 \equiv c^{32}, x_3=34 \equiv b^{59} \pmod{97}</math>이다. 이 시점에서 1과 합동인 <math>c^{32}</math>에 도달하였기에 알고리즘이 끝난다. 아울러 마지막에 나온 <math>x_3 \equiv b^{59}</math>가 구하는 해이며, 검산을 하면 <math>x_3^2 \equiv b^{118} \equiv b^{22} \equiv a \pmod{97}</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 (원본 보기) (준보호됨)틀:각주 (원본 보기) (준보호됨)틀:둘러보기 상자 (원본 보기) (보호됨)틀:둘러보기 상자/핵심 (원본 보기) (보호됨)틀:수론 알고리즘 (편집) 틀:틀바 (원본 보기) (준보호됨)