로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.스팸 방지 검사입니다. 이것을 입력하지 마세요!'''쇤하게-슈트라센 곱셈법'''(Schönhage–Strassen multiplication algorithm)은 두 정수의 곱을 빠르게 셈하는 알고리즘으로, 1971년 아놀드 쇤하게(Arnold Schönhage)와 폴커 슈트라센(Volker Strassen)이 고안하였다. 이 곱셈법은 [[푸리에 변환]]을 이용한 방법으로 시간 복잡도는 <math>O(n\log n \log\log n)</math> 꼴이다. 이는 1960년대에 고안된 [[카라추바 곱셈법]]이나 [[톰-쿡 곱셈법]]보다 큰 수에서 훨씬 효율적이며, 로그 항을 제외하면 사실상 연산량은 자릿수에 거의 비례한다. 이 방식은 컴퓨터 연산에 큰 혁명을 가져왔다고 할 수 있으며, 2007년 [[퓌러 곱셈법]], 2019년 [[하비-호븐 곱셈법]]이 나오기 전까지 가장 효율적인 큰 수의 곱셈법이었다. 물론 현재 컴퓨터에서 많이 다루는 범위의 큰 수, 또는 소수점 아래 자릿수가 많은 수에 대해서는 여전히 쇤하게-슈트라센 방식이 가장 실용적이다. == 아이디어 == * '''참고''': 이 문단에서는 쇤하게-슈트라센 곱셈법의 '기본 원리'를 중심으로 소개한다. 구체적인 알고리즘 설계나 최적화 방법에는 여러 방식이 있으며, 본 문서와 [https://www.semanticscholar.org/paper/Schnelle-Multiplikation-gro%C3%9Fer-Zahlen-Sch%C3%B6nhage-Strassen/6c9df56377359945f7ef7e06f0b22d52f288c0bc 원문]의 내용에는 다소 차이가 있다. [[Wikipedia:Schönhage–Strassen algorithm]]에서도 다른 방법을 알아볼 수 있다. * 벡터의 성분 표기는 전산의 편의를 위해 첫 성분을 0으로 잡는다. 이 곱셈법은 기본적으로 자릿수 블록을 쪼개고 부분 곱셈을 시행한 뒤 합성하는 방식을 따르며, [[카라추바 곱셈법]]이나 [[톰-쿡 곱셈법]]과 출발점이 같다. 어떤 큰 두 수를 일정 자릿수마다 블록을 쪼개고, 두 수에 대응하는 다항식을 세운다. <math>M=f(B), m_1=\lceil \log_B M \rceil, f(x)=\sum_{k=0}^{m_1-1} a_k x^k, N=g(B), m_2=\lceil \log_B N \rceil, g(x)=\sum_{k=0}^{m_2-1} b_k x^k</math><ref>항의 수는 엄밀히는 <math>m_1=\lceil \log_{B}(M+1) \rceil</math>이다. 하지만 여기서는 <math>\log_B M</math>이 정수로 정확히 떨어지는 경우는 생각하지 않는다. <math>m_2, N</math>의 경우도 마찬가지.</ref> 여기서 <math>B</math>는 기수법에 따라 결정되는 값으로, 가령 이진법에서 블록 하나당 <math>r</math>자리를 담고 있다면 <math>B=2^r</math>이다. 그 다음 우리가 구할 다항식은 <math>h(x)=f(x)g(x)=\sum_{k=0}^{m_1+m_2-2} c_k x^k</math>이며, 구하려는 곱셈 결과는 <math>MN=h(B)</math>이다. 그렇다면 위에서 상정한 계수 <math>a_k, b_k, c_k</math>의 관계는 아래와 같이 [[합성곱]]의 형태로 써진다. * <math>h(x)=\sum_{k=0}^{m_1-1} a_k x^k \sum_{k=0}^{m_2-1} b_k x^k = \sum_{k=0}^{m_1+m_2-2}(\sum_{l=0}^{k}a_l b_{k-l})x^m</math> * <math>c_k=\sum_{l=0}^{k}a_l b_{k-l}, 0 \leq k \leq m_1+m_2-2</math> * 단, <math>m_1-1 < l \leq m_1+m_2-2</math>인 경우 <math>a_l=0</math>으로 간주한다. 마찬가지로 <math>m_2-1 < l \leq m_1+m_2-2</math>인 경우 <math>b_l=0</math>이다. * 벡터 <math>a=(a_0, a_1, \cdots a_{m_1+m_2-2})</math>를 정의하고 마찬가지로 <math>b, c</math>를 정의하면 <math>c= \operatorname{convolution}(a, b)</math>와 같이 표현된다. 그런데 벡터의 합성곱에서 벡터를 [[푸리에 변환]]하면 '''성분 별 곱셈'''으로 바뀐다. 즉 이산 푸리에 변환을 거친 벡터를 <math>\bar{a} =\operatorname{DFT}(a) \Leftrightarrow a =\operatorname{IDFT}(\bar{a})</math>와 같이 표현하면 <math>\bar{c}_k=\bar{a}_k \bar{b}_k, c=\operatorname{IDFT}(\bar{c})</math>이다.<ref>DFT: 이산 푸리에 번환(discrete Fourier transform), IDFT: 이산 푸리에 역변환</ref> 따라서 이 알고리즘은 "블록 쪼개기→푸리에 변환→블록 별 부분 곱셈→푸리에 역변환→블록 합치기" 순으로 진행한다. === 모듈러 산술에서의 푸리에 변환 === 곱하려는 두 수의 블록 개수의 합을 <math>K</math>라 하면 전형적인 이산 푸리에 변환 및 역변환은 다음과 같이 써진다. * <math>f(x)=\sum_{k=0}^{K-1} a_m x^m</math><ref>앞서 <math>f(x)</math>의 항이 <math>m_1</math>개라 가정했지만 여기서는 <math>K</math>개까지 연장한다. 비어 있는 고차항들은 계수를 0으로 취급한다.</ref> * <math>f(\omega^n)=\sum_{k=0}^{K-1} a_k \omega^{kn}, \omega=e^{2\pi i/K}</math> * <math>a_k=\frac{1}{K}\sum_{n=0}^{K-1} f(\omega^n) \omega^{-kn}</math> * <math>g(x)=\sum_{k=0}^{K-1} b_k x^k, h(x)=\sum_{k=0}^{K-1} c_k x^k</math>도 마찬가지 형태로 써진다. 계산 목표는 먼저 <math>f(\omega^n), g(\omega^n)</math>이고 이를 이용하여 <math>h(\omega)=f(\omega^n)g(\omega^n)</math>의 값을 구한다. 그렇게 해서 다항식 <math>h(x)</math>를 도출하고 <math>h(B)</math>의 값을 구하면 원하는 답이 나온다. 하지만 위 공식을 그대로 적용하기에는 무리가 있다. 푸리에 변환에 필요한 곱셈 인자인 <math>\omega</math>는 특수한 값을 제외하고는 기본적으로 실수부와 허수부 모두 무리수이다. 본 문서에서는 두 정수의 곱셈을 다루려는데, 공식 그대로의 변환은 사실상 무리수의 곱셈 및 덧셈을 다루는 것이다. 즉 계산 과정이 오히려 지저분해진다. 그 대신 [[모듈러 산술]]을 기준으로 공식을 다듬으면 정수의 연산 틀을 유지할 수 있다. 이산 푸리에 변환은 기본적으로 <math>\omega \neq 1, \omega^K=1, \sum_{k=0}^{K-1}\omega^{kn}=\begin{cases} K \text{ if } K \mid n \\ 0 \text{ otherwise} \end{cases}</math> 식을 바탕으로 세워진다. 그렇다면 모듈러 산술에서는 <math>t \neq 1, t^K \equiv 1 \pmod u</math>를 만족하는 정수 <math>t, u</math>로 대체한다. 그리고 푸리에 변환은 <math>\mathbb{C}</math> 대신 <math>\mathbb{Z}/u\mathbb{Z}</math> 위에서 이루어진다. 그러면 <math>f(t^n) \equiv \sum_{k=0}^{K-1} a_k t^{kn} \pmod p</math>과 같이 쓸 수 있고, <math>g(t^n), h(t^n)</math>역시 같은 형식으로 써진다. 이제 몇 가지 가정이 필요하다: 계산의 편의를 위해 <math>K=2K'</math>는 짝수로 두고, <math>t^{K'} \equiv -1 \pmod u</math>라고 가정한다. 그 다음 조건식 <math>\sum_{k=0}^{K-1} t^{kn} \equiv \begin{cases} K \text{ if } K \mid n \\ 0 \text{ otherwise} \end{cases} \pmod u</math>를 살펴볼 차례다. <math>t^K \equiv 1, t^n \not \equiv 1 \pmod u \text{ for } 0< n < K</math>를 만족하면 해당 조건식은 성립한다. 즉 법 <math>u</math>의 대한 <math>t</math>의 [[위수 (정수론)|위수]]가 <math>K</math>와 일치하도록 하려고 한다. 이 조건을 맞추는 방법은 여러 가지가 있지만 컴퓨터가 다루기 쉬운 값은 <math>u=2^{K'}+1, t=2</math>이다. <math>t^n=2^n</math>을 곱한다는 것은 비트를 왼쪽으로 <math>n</math>자리 미는 것과 같으며, <math>A=2^{K'}a+b</math>이면 <math>A \equiv -a+b \pmod{2^{K'}+1}</math>로 나머지 연산이 간결하기 때문이다. 또 하나, 앞서 언급한 식인 <math>M=f(B), N=g(B)</math>에 대해 <math>f(x), g(x)</math>의 계수는 모두 <math>0 \leq a_k, b_k < B</math>이다. 또한 <math>h(x)</math>의 계수 공식 <math>c_k=\sum_{l=0}^{k}a_l b_{k-l}</math>에서 각 계수의 가능한 값의 범위를 파악해야 한다. <math>M, N</math>의 블록의 개수를 <math>m_1, m_2</math>라 하면 <math>a_l b_{k-l} \neq 0</math>인 항의 최대 개수는 <math>\min(m_1, m_2)</math>이다. 그런데 <math>m_1+m_2 =K</math>이므로, 결국 0이 아닌 항의 최대 개수는 <math>K'</math>이라 할 수 있다. 그리고 <math>0 \leq a_l, b_{k-l}<B</math>이므로 <math>0 \leq a_l b_{k-l}<B^2</math>이고, 이에 따라 <math>0 \leq c_k < K'B^2</math>임을 알 수 있다. 한편 <math>h(t^n) \equiv \sum_{k=0}^{K-1} c_k t^{kn} \pmod u</math>에서 <math>c'_k=c_k+u</math>라 하면 <math>h(t^n) \equiv \sum_{k=0}^{K-1} c'_k t^{kn} \pmod u</math> 식도 성립한다. 다시 말해 만약 <math>0 \leq c_k, c'_k < K'B^2, c'_k-c_k=u</math>인 두 계수가 존재한다면 같은 <math>h(t^n)</math>에 대해 '''서로 다른''' <math>c_k</math>의 해가 둘 이상 나오는 불상사가 발생한다. 원래 다항식 <math>h(x)=f(x)g(x)</math>의 계수들은 반드시 유일하게 나와야 하는데, 해가 여러 개이면 어떤 것이 우리가 찾고자 하는 해인지 구분할 수 없게 된다(즉 정보가 뭉개진다). 따라서 이를 방지하려면 <math>u \geq K'B^2</math>으로 잡아야 하며, 이것이 계수의 범위를 사전에 체크하는 이유이다. === 블록의 개수와 길이 === 이산 푸리에 변환은 블록의 개수가 2의 거듭제곱일 때 가장 효율적으로 계산할 수 있으며, 이 조건에서 [[고속 푸리에 변환]]을 도입한다. 두 수의 곱인 <math>MN</math>의 최대 비트 수는 <math>\ell=\lceil \log_2 M \rceil+\lceil \log_2 N \rceil</math>이다.<ref><math>\ell=\lceil \log_2 MN \rceil</math>이 아닌 이유는 <math>MN</math>은 알고 있는 값이 아닌 '''알고 싶은 값'''이기 때문이다. 즉 알고리즘 실행 전에는 두 수의 비트를 각각 잰 다음 더하는 것이 옳다.</ref> 블록 하나가 <math>r</math>비트이고 <math>K</math>개 블록이 위 곱셈 결과를 담으려면 <math>\ell \leq Kr</math>이어야 한다. 즉 <math>r=\left \lceil \frac{\ell}{K} \right \rceil</math>로 잡는다. 한편 블록 하나의 단위는 <math>B=2^r</math>이다. 블록은 <math>K=2^{d+1}, K'=2^d</math>으로 2의 거듭제곱 개수라 가정한다. 그러면 위 조건에 따라 <math>u=2^{2^d}+1 \geq K'B^2=2^{2r+d}</math>이어야 하며, 여기서 <math>r, d</math>는 자연수이므로 <math>2r+d \leq 2^d</math>으로 쓸 수 있다. 아울러 위 문단의 <math>r</math>의 조건을 대입하면 <math>2 \left \lceil \frac{\ell}{2^{d+1}} \right \rceil \leq 2^d-d</math>이다. 이에 따라 <math>\ell</math>을 기준으로 <math>d</math>를 결정할 수 있다. {|class="wikitable" ! <math>d</math> !! <math>K</math> !! <math>2^d-d</math> !! <math>\frac{\ell}{2^{d+1}}</math>의 최댓값 !! <math>\ell</math>의 최댓값 |- | 1 || 4 || 1 || 0 || 0 |- | 2 || 8 || 2 || 1 || 8 |- | 3 || 16 || 5 || 2 || 32 |- | 4 || 32 || 12 || 6 || 192 |- | 5 || 64 || 27 || 13 || 832 |- | 6 || 128 || 58 || 29 || 3712 |- | 7 || 256 || 121 || 60 || 15360 |- | 8 || 512 || 248 || 124 || 63488 |- | 9 || 1024 || 503 || 251 || 257024 |- | 10 || 2048 || 1014 || 507 || 1038336 |- |} 수가 커짐에 따라 <math>d \approx \log_4 \ell</math> 꼴이 된다. 예를 들어 곱하려는 두 수가 81비트, 108비트라 하면 곱한 결과는 189비트라 예상하고, 위 표에서 <math>\ell</math>의 허용 범위를 보면 <math>d \geq 4</math>일 때 알고리즘을 적용할 수 있음을 알 수 있다. <math>d=4</math>를 택하면 <math>K=32, K'=16, u=2^{16}+1, r=\left \lceil \frac{189}{32} \right \rceil=6, B=2^6=64</math>이다. === 고속 푸리에 변환 === 바로 앞 문단에서 [[고속 푸리에 변환]](FFT)을 위해 <math>K</math>를 2의 거듭제곱으로 가정하였다. <math>d, K, r, u</math>의 값을 정한 후에는 FFT를 실행할 차례다. 주어진 <math>f(x)</math>로부터 <math>f(t^n) \mod u</math>의 값을 셈하는데, 앞서 언급했듯이 컴퓨터에게는 <math>t=2</math>가 가장 편리하다. * <math>f(x)=\sum_{k=0}^{K-1} a_k x^k \Rightarrow f(2^n)=\sum_{k=0}^{K-1} (a_k \triangleleft nk)</math> 여기서 <math>a_k \triangleleft n = x\cdot 2^{n} \mod u</math>이다. 즉 <math>a_k</math>의 이진법 표기에서 왼쪽으로 <math>n</math>비트 밀고 <math>u</math>로 나눈 나머지를 셈하는 것이다. 고속 푸리에 변환은 이렇게 전개한다. 모든 벡터의 성분의 수는 2의 거듭제곱이며 <math>w=\bar{v}</math>를 도출하는 것이 목표다. 여기서 보조 인자가 하나 필요한데 초깃값은 <math>s=1</math>이다. * 계수들을 나열한 벡터 <math>v=(v_0, v_1, \cdots v_{n-1})</math>을 입력 받고 벡터의 길이를 잰다. 만약 성분이 하나 뿐이라면 <math>w=v</math>를 반환한다. * 성분이 둘 이상이면 벡터를 홀수 번째와 짝수 번째 성분으로 분리한다. ** <math>v^\oplus=(v_0, v_2, \cdots v_{n-2}), v^\ominus=(v_1, v_3, \cdots v_{n-1})</math> * 각각의 부분 벡터에 대해 보조 인자가 <math>2s</math>인 FFT를 시행한다. 즉 부분벡터를 입력값으로 해서 처음으로 올라간다. (재귀함수 호출) ** <math>w^\oplus=\bar{v^\oplus}, w^\ominus=\bar{v^\ominus}</math> * 두 변환 결과를 이용하여 하나로 합친다. 여기서 아까 언급했던 보조 인자 <math>s</math>가 쓰인다. ** <math>\begin{cases} w_j=w^\oplus_j + (w^\ominus_j \triangleleft js) \\ w_{j+n/2}=w^\oplus_j - (w^\ominus_j \triangleleft js) \end{cases} (0 \leq j < n/2)</math> * 합친 결과인 <math>w</math>를 반환한다. 이 방법으로 계수 벡터 <math>a=(a_0, a_1, \cdots a_{K-1}), b=(b_0, b_1, \cdots b_{K-1})</math>에 대해 푸리에 변환을 거친 <math>\bar{a}=(f(1), f(2), \cdots f(2^{K-1})), \bar{b}=(g(1), g(2), \cdots g(2^{K-1}))</math>를 셈한다. 그리고 두 벡터를 각 성분마다 곱하면 <math>\bar{c} (\bar{c}_k=h(2^k)=f(2^k)g(2^k) \mod u)</math>가 나오는데, 이번에는 고속 푸리에 '''역변환'''(IFFT)을 시행한다. 방법은 위와 거의 똑같다. * <math>\bar{c}=(h(1), h(2), \cdots h(2^{K-1}))</math>에서 첫 번째를 제외한 성분들의 순서를 통째로 뒤집는다. ** <math>\bar{c}^\dagger=(h(1), h(2^{K-1}), \cdots h(2))</math> * <math>\bar{c}^\dagger</math>에 대해 위 방법(FFT)을 시행한다. 마찬가지로 보조 인자는 1에서 시작한다. ** <math>Kc=c'=\bar{\bar{c}^\dagger}</math> * 각 성분을 <math>K</math>로 나눈다. 이때 합동식 <math>Kc_k \equiv c'_k \pmod u</math>를 풀어야 하는데, <math>K=2^{d+1}, u=2^{2^d}+1</math>이므로 <math>c_k \equiv -2^{2^d-(d+1)}c'_k \pmod u</math>이다. 즉 <math>c_k = \begin{cases} 0\ (c'_k=0) \\ u-c'_k \triangleleft [2^d-(d+1)] \ (\text{o/w}) \end{cases}</math> == 알고리즘 == 위 아이디어를 토대로 과정을 총정리하면 아래와 같다. * 곱하고자 하는 두 수 <math>M, N</math>의 비트 수를 잰다. * 비트 수의 합에 따른 블록의 수 <math>K</math>와 이에 따른 블록 하나의 비트 수 <math>r</math>, 모듈러 산술에 필요한 <math>u=2^{K/2}+1</math>을 결정한다. * 두 수를 <math>r</math>비트마다 블록을 쪼개고, 가장 뒷자리부터 블록 별 값을 벡터로 적는다. 그 다음 각 벡터의 성분이 총 <math>K</math>개가 되도록 0을 이어붙인다. * 각 벡터에 대해 FFT를 시행한다. * 변환된 벡터의 성분 별로 곱해서 새로운 벡터를 도출한다. * 새로운 벡터에 IFFT를 적용한다. * 푸리에 역변환 후의 벡터의 성분들을 이어붙인다. 이때 맨 뒤 성분에서 시작하여 역순으로, 자리를 <math>r</math>비트씩 옮기면서 더해간다. == 적용 예 == 두 수 <math>M=1734492765338661710171833, N=205295973898620029528272537868263</math>의 곱을 위 문단에 소개된 방법으로 구해보자. 두 수는 이진법으로 각각 81비트, 108비트이며 곱셈 결과는 189비트로 예상한다. 블록은 총 <math>K=32</math>개, 블록 하나당 <math>r=6</math>비트, 블록 하나의 단위는 <math>B=2^6=64</math>, 모듈러스는 <math>u=2^{16}+1=65537</math>로 잡는다. ('블록의 개수와 길이' 문단 참고) 두 수를 6비트마다 쪼개서 벡터로 표현하고, 성분이 32개가 되도록 0을 덧붙이면 아래와 같다. 이때 가장 나중 블록이 벡터의 첫 성분이고 자리 역순으로 써진 것에 유의한다.<ref>이를테면 이진법 표현인 "110111101001011"을 "110 111101 001011"과 같이 쪼갠다면 벡터는 (1011, 111101, 110)과 같이 뒤쪽 블록부터 적는다.</ref> a=(57, 58, 56, 2, 28, 51, 47, 12, 13, 42, 48, 18, 47, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) b=(39, 31, 53, 56, 11, 2, 15, 8, 62, 63, 40, 44, 49, 5, 49, 12, 31, 40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) 그 다음 각 벡터에 대해 FFT를 시행한다. (모든 연산은 법 65537에 대한 모듈러 산술로 진행한다.) FFT(a)=(484, 23672, 37350, 64084, 48059, 4971, 19047, 11919, 31738, 62963, 16115, 15526, 34681, 57928, 23529, 28579, 108, 15027, 10605, 35996, 46652, 25123, 57809, 49642, 33787, 28348, 47724, 5385, 1662, 5659, 50321, 24849) FFT(b)=(610, 46882, 45564, 16308, 9523, 29188, 42423, 31306, 5411, 56950, 6213, 34544, 55361, 52264, 34647, 19840, 88, 44887, 50106, 19606, 5469, 10232, 16920, 45334, 60196, 62951, 55848, 49446, 61009, 20297, 10491, 49926) 변환 결과를 각 성분 별로 곱한다. ab=(33092, 52683, 16121, 28870, 20986, 60167, 25208, 34073, 27378, 16969, 47496, 40873, 2889, 1740, 60057, 46773, 9504, 10145, 134, 35160, 4247, 22422, 54092, 60922, 32531, 27975, 31236, 55416, 11219, 39899, 17076, 61301) 그리고 이 벡터에다 IFFT를 시행한다. c=IFFT(ab)=(2223, 4029, 7003, 8080, 7997, 6851, 6597, 7656, 11376, 13591, 14996, 14839, 18014, 16935, 17719, 14806, 14164, 14261, 15539, 12803, 12416, 12079, 9827, 7856, 6352, 3760, 5712, 3287, 2237, 2035, 200, 0) 이제 맨 끝 성분부터 시작해서 '왼쪽으로 블록 하나만큼 비트를 밀고 이전 성분을 더하기'를 반복하면 원하는 결과가 나온다. 이 예시에서는 블록 하나가 6비트이고 <math>B=64</math>임을 확인한다. * <math>x_1=c_{K-1}, x_k=x_{k-1}\cdot B+c_{K-k}, 1 < k \leq K</math> * <math>MN=x_K</math> Result: 356084381480311170312773728803907543171632357309247236079 이것으로 알고리즘은 끝난다. 이 결과는 <math>MN</math>을 전통적인 곱셈법으로 계산한 것과 일치한다. 실제로 컴퓨터는 저 정도 크기의 수는 바로 곱하는 편이 빠르지만, 만약 곱하고자 하는 두 수가 수만 비트 이상으로 거대하다면 쇤하게-슈트라센 곱셈법의 효력은 막강해진다. == 참고 자료 == * [https://yuvalfilmus.cs.technion.ac.il/Courses/AlgebraicMethods/2017/FFT.pdf FFT and Schönhage–Strassen] {{각주}} {{수론 알고리즘}} [[분류:알고리즘]] 요약: 리브레 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 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 (원본 보기) (준보호됨)틀:각주 (원본 보기) (준보호됨)틀:둘러보기 상자 (원본 보기) (보호됨)틀:둘러보기 상자/핵심 (원본 보기) (보호됨)틀:수론 알고리즘 (편집) 틀:틀바 (원본 보기) (준보호됨)