쇤하게-슈트라센 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

쇤하게-슈트라센 알고리즘은 큰 정수의 곱셈을 효율적으로 수행하기 위한 알고리즘으로, 분할 정복 방식과 고속 푸리에 변환(FFT)을 활용한다. 이 알고리즘은 이산 푸리에 변환, 합성곱, 수론 변환(NTT) 등의 개념을 사용하며, 암호학, 과학 연산, 디지털 신호 처리 등 다양한 분야에 응용된다. 쇤하게-슈트라센 알고리즘은 분할 횟수 최적화, 툼-쿡 곱셈과 같은 다른 곱셈 알고리즘 활용, 제곱근 2 트릭, 그란룬드의 트릭, 시프트 연산 최적화 등의 기법을 통해 성능을 향상시킨다.

2. 역사적 배경

쇤하게-슈트라센 알고리즘은 곱셈 알고리즘 발전 과정에서 중요한 이정표를 세웠다.

2. 1. 쇤하게-슈트라센 알고리즘의 등장

여기에서는 쇤하게와 포메란스의 ''Prime Numbers: A Computational Perspective''에 기반한 구현에 대해 주로 설명한다. 쇤하게의 원래 구현에서는 Discrete Weighted Transform (DWT)를 사용하여 보다 효율적으로 컨볼루션을 수행하고 있다. 크누스의 ''The Art of Computer Programming''에서도 본 알고리즘이 소개되어 있다.^[28] 여기에서는 블록의 구성 방법에 대해 설명하고, 알고리즘 전체의 절차를 순서대로 설명하고 있다.

3. 이론적 배경

쇤하게-슈트라센 알고리즘은 이산 푸리에 변환(DFT)과 합성곱(Convolution)의 원리를 이용하여 큰 정수의 곱셈을 효율적으로 수행한다. 이 알고리즘은 두 수의 곱셈을 다항식의 곱셈으로 변환하고, 합성곱 정리를 활용하여 DFT 영역에서 점별 곱셈을 수행한 후, 역 DFT를 통해 최종 결과를 얻는다.

원래 버전에서는 수론 변환(NTT) 대신 고속 푸리에 변환(FFT)이 사용된다.^[7] FFT를 합성곱 정리와 함께 사용하면 다음과 같은 식이 성립한다.^[7]

: $\hat{f}(a * b) = \hat{f}\left(\sum_{i=0}^k a_ib_{k-i} \right) = \hat{f}(a) \bullet \hat{f}(b).$

즉, $C_k = a_k \bullet b_k$ 이다. 여기서 $C_k$ 는 푸리에 공간에서의 해당 계수이다. 이는 $\text{fft}(a * b) = \text{fft}(a) \bullet \text{fft}(b)$ 로도 쓸 수 있다.

쇤하게-슈트라센 알고리즘은 분할 정복 방식을 사용하여 문제를 하위 문제로 나눈다.

3. 1. 이산 푸리에 변환 (Discrete Fourier Transform, DFT)

이산 푸리에 변환(DFT, Discrete Fourier Transform)은 이산적인 신호(데이터)를 주파수 영역으로 변환하는 연산이다. DFT는 시간 영역의 데이터를 주파수 성분으로 분해하여 분석하는 데 사용된다. 고속 푸리에 변환(FFT, Fast Fourier Transform) 알고리즘을 사용하면 DFT를 효율적으로 계산할 수 있다.

쇤하게-슈트라센 알고리즘은 다른 고속 푸리에 변환을 사용하는 곱셈과 마찬가지로, 겹침곱 정리의 ''순환 겹침곱을 효율적으로 계산할 수 있는 성질''을 이용한다. 구체적으로, 두 벡터의 순환 겹침곱은 각각을 한 번 이산 푸리에 변환하고, 그 결과의 곱을 역 이산 푸리에 변환함으로써 얻을 수 있다.

수식으로 표현하면 (여기서 점곱은 벡터의 내적(스칼라 곱)이 아니라, 두 벡터를 성분별로 곱하여 새로운 벡터를 만드는 연산이다) 다음과 같다.

: CyclicConvolution(''X, Y'') = IDFT(DFT(''X'') ⋅ DFT(''Y''))

입력을 변환한 DFT(X)와 DFT(Y)의 곱을 계산하기 위해서도 고속 푸리에 변환을 사용하여 이산 푸리에 변환과 역 이산 푸리에 변환을 수행하고, 곱셈 알고리즘을 재귀적으로 호출함으로써 순환 겹침곱을 효율적으로 계산할 수 있다.

이 알고리즘은 역방향의 순환 겹침곱을 사용하면 가중치가 부여된 변환인 DWT에 대응하는 겹침곱 정리도 적용할 수 있어 더욱 유용한 알고리즘이 된다. 벡터 X와 Y의 길이가 ''n''이고, a가 위수 2''n''의 원시근이라고 가정한다 (즉, ''a''^2''n'' = 1). 이때, A를 가중치 벡터로 다음과 같이 정의한다.

: ''A'' = (''a''^''j''), 0 ≤ ''j'' < ''n''

: ''A''⁻¹ = (''a''^−''j''), 0 ≤ ''j'' < ''n''

따라서, 다음과 같이 표현할 수 있다.

: NegacyclicConvolution(''X'', ''Y'') = ''A''⁻¹ ⋅ IDFT(DFT(''A'' ⋅ ''X'') ⋅ DFT(''A'' ⋅ ''Y''))

이산 푸리에 변환 전에 A가 곱해지고, 역 이산 푸리에 변환 후에 ''A''⁻¹이 곱해진다는 점을 제외하면 거의 같은 형태이다.

3. 2. 합성곱 (Convolution)

Convolution|컨볼루션^영어(합성곱)은 두 신호(데이터)를 결합하여 새로운 신호를 생성하는 연산이다. 합성곱은 신호 처리, 이미지 처리 등 다양한 분야에서 활용된다. 특히, 쇤하게-슈트라센 알고리즘에서는 순환 합성곱(Circular Convolution)과 역순환 합성곱(Negacyclic Convolution)이 중요한 역할을 한다.

두 수의 곱셈은 두 다항식의 곱으로 생각할 수 있으며, 이 과정에서 합성곱이 사용된다.^[7]

:

XY = \left(\sum_{i=0}^N {x_iB^i}\right)\left(\sum_{j=0}^N {y_iB^j}\right)

여기서

B^k

에 대해,

c_k =\sum_{(i,j):i+j=k} {a_ib_j} = \sum_{i=0}^k {a_ib_{k-i}}

이 성립한다.

쇤하게-슈트라센 알고리즘은 겹침곱 정리를 활용하여 순환 겹침곱을 효율적으로 계산한다. 겹침곱 정리는 다음과 같다.

두 벡터의 순환 겹침곱은 각각을 이산 푸리에 변환하고, 그 결과의 곱을 역 이산 푸리에 변환하여 얻을 수 있다.

수식으로는 다음과 같이 표현된다.

CyclicConvolution(''X, Y'') = IDFT(DFT(''X'') ⋅ DFT(''Y''))

여기서 점곱(⋅)은 벡터의 성분별 곱을 의미한다.
순환 합성곱 (Cyclic Convolution)입력 수열이 n개의 요소로 구성된 경우, 선형 합성곱의 결과에서 오른쪽 끝 n개 요소를 왼쪽 끝 n-1개 요소에 더하여 순환 합성곱을 얻는다. 순환 합성곱의 결과는 입력의 곱과

B^n - 1

을 법으로 하는 합동 결과와 같다.
역순환 합성곱 (Negacyclic Convolution)선형 합성곱의 결과에서 오른쪽 끝 n개 요소에서 왼쪽 끝 n-1개 요소를 빼서 역순환 합성곱을 얻는다. 역순환 합성곱의 결과는

B^n + 1

을 법으로 하여 입력의 곱과 합동이다. 음수가 나올 수 있지만, 올림/내림을 통해 처리할 수 있다.

쇤하게-슈트라센 알고리즘은 역순환 합성곱을 사용하며, 가중치가 부여된 변환(DWT)에 대응하는 겹침곱 정리를 적용하여 효율성을 높인다.^[28] 벡터 X와 Y의 길이가 n이고, a가 위수 2n의 원시근일 때, 가중치 벡터 A와 A^-1을 다음과 같이 정의한다.

$A = (a^j)$ , 0 ≤ j < n
$A^{-1} = (a^{-j})$ , 0 ≤ j < n

그러면 역순환 합성곱은 다음과 같이 계산된다.

NegacyclicConvolution(X, Y) = $A^{-1}$ ⋅ IDFT(DFT(A ⋅ X) ⋅ DFT(A ⋅ Y))

즉, 이산 푸리에 변환 전에 A를 곱하고, 역 이산 푸리에 변환 후에

A^{-1}

을 곱하는 것을 제외하면 순환 합성곱과 유사하다.

3. 3. 합성곱 정리 (Convolution Theorem)

두 신호의 합성곱은 각 신호의 DFT를 곱한 후, 역 DFT를 취하여 얻을 수 있다는 합성곱 정리를 활용한다.^[7] 쇤하게-슈트라센 알고리즘은 이 정리를 이용하여 곱셈 연산을 효율적으로 수행한다.

밑이 B인 모든 숫자는 다음과 같은 다항식으로 표현할 수 있다.

:

X = \sum_{i=0}^N {x_iB^i}

두 숫자의 곱셈은 두 다항식의 곱으로 생각할 수 있다.

:

XY = \left(\sum_{i=0}^N {x_iB^i}\right)\left(\sum_{j=0}^N {y_iB^j}\right)

B^k

에 대해:

c_k =\sum_{(i,j):i+j=k} {a_ib_j} = \sum_{i=0}^k {a_ib_{k-i}}

이므로, 컨볼루션(convolution, 합성곱)이 존재한다.

고속 푸리에 변환(FFT)을 컨볼루션 규칙과 함께 사용하면,^[7]

:

\hat{f}(a * b) =  \hat{f}\left(\sum_{i=0}^k a_ib_{k-i} \right) =  \hat{f}(a) \bullet \hat{f}(b).

즉,

C_k = a_k \bullet b_k

이다. 여기서

C_k

는 푸리에 공간에서의 해당 계수이다. 이는

\text{fft}(a * b) = \text{fft}(a) \bullet \text{fft}(b)

로도 쓸 수 있다.

푸리에 변환은 선형성을 가지며, 이러한 다항식은 계수당 하나의 고유한 항만으로 구성되어 있기 때문에 동일한 계수를 갖는다.

:

\hat{f}(x^n) = \left(\frac{i}{2\pi}\right)^n \delta^{(n)}

:

\hat{f}(a\, X(\xi) + b\, Y(\xi)) = a\, \hat{X}(\xi) + b\, \hat{Y}(\xi)

컨볼루션 규칙:

\hat{f}(X * Y) = \ \hat{f}(X) \bullet \hat{f}(Y)

FFT를 통해 컨볼루션 문제를 곱셈 문제로 축소했다. 각

C_k

의 다항식 보간법의 FFT를 찾음으로써 원하는 계수를 결정할 수 있다.

쇤하게-슈트라센 알고리즘은 다른 고속 푸리에 변환을 사용하는 곱셈과 마찬가지로, 겹침곱 정리의 ''순환 겹침곱을 효율적으로 계산할 수 있는 성질''을 이용한다. 구체적으로, 두 벡터의 순환 겹침곱은 각각을 이산 푸리에 변환하고, 그 결과의 곱을 역 이산 푸리에 변환함으로써 얻을 수 있다.

수식으로 표현하면 (여기서의 점곱은 벡터의 내적(스칼라 곱)이 아니라, 두 벡터를 성분별로 곱하여 새로운 벡터를 만드는 연산이다)

: CyclicConvolution(''X, Y'') = IDFT(DFT(''X'') · DFT(''Y''))

입력을 변환한 DFT(X)와 DFT(Y)의 곱을 계산하기 위해서도 고속 푸리에 변환을 사용하여 이산 푸리에 변환과 역 이산 푸리에 변환을 수행하고, 곱셈 알고리즘을 재귀적으로 호출함으로써 순환 겹침곱을 효율적으로 계산할 수 있다.

역방향 순환 겹침곱을 사용하면 가중치가 부여된 변환인 DWT에 대응하는 겹침곱 정리도 적용할 수 있어, 더욱 유용한 알고리즘이 된다. 벡터 X와 Y의 길이가 ''n'' 이고, a가 위수 2''n''의 원시근이라고 가정한다 (즉, ''a''^2''n'' = 1). 이때, A를 가중치 벡터로 다음과 같이 정의한다.

: ''A'' = (''a''^''j''), 0 ≤ ''j'' < ''n''

: ''A''⁻¹ = (''a''^−''j''), 0 ''≤ ''j''<'' n''

따라서,

: NegacyclicConvolution(''X'', ''Y'') = ''A''⁻¹ · IDFT(DFT(''A'' · ''X'') · DFT(''A'' · ''Y''))

라고 할 수 있다. 이산 푸리에 변환 전에 A가 곱해지고, 역 이산 푸리에 변환 후에 ''A''⁻¹이 곱해진다는 점을 제외하면 거의 같은 형태이다.

3. 4. 수론 변환 (Number Theoretic Transform, NTT)

쇤하게-슈트라센 알고리즘은 수론 변환(Number Theoretic Transform, NTT)을 사용하여 큰 정수의 곱셈을 효율적으로 수행한다. NTT는 유한체(Finite Field)에서 수행되는 이산 푸리에 변환(DFT)의 일종으로, 복소수 연산 대신 정수 연산을 사용하므로 반올림 오차 없이 정확한 계산을 보장한다.^[7]

이 알고리즘의 핵심 아이디어는 다음과 같다.

1. 다항식 표현: 밑이 B인 두 숫자 a, b는 다음과 같은 다항식으로 표현할 수 있다.^[7]

:

a = \sum_{i=0}^N {a_iB^i}

:

b = \sum_{i=0}^N {b_iB^i}

2. 컨볼루션 (합성곱): 두 숫자의 곱셈은 두 다항식의 곱으로 생각할 수 있으며, 이는 컨볼루션을 통해 계산할 수 있다.^[7]

:

a \cdot b = \left(\sum_{i=0}^N {a_iB^i}\right)\left(\sum_{j=0}^N {b_iB^j}\right)

컨볼루션은 다음과 같이 정의된다.

:

c_k =\sum_{(i,j):i+j=k} {a_ib_j} = \sum_{i=0}^k {a_ib_{k-i}}

3. FFT/NTT를 이용한 컨볼루션 계산: 컨볼루션 정리에 따라, 두 다항식의 컨볼루션은 각 다항식을 FFT(또는 NTT) 변환한 후, 변환된 다항식의 점별 곱을 역변환하여 구할 수 있다.^[7]

:

\hat{f}(a * b) =  \hat{f}\left(\sum_{i=0}^k a_ib_{k-i} \right) =  \hat{f}(a) \bullet \hat{f}(b).

4. 유한체와 원시근: 쇤하게-슈트라센 알고리즘은 복소수 대신 유한체

\mathrm{GF}( 2^n + 1 )

을 사용한다. 유한체에서 원시근

\theta

를 사용하여 NTT를 수행한다. 여기서

\theta^N = -1

(n^차 근)이다.^[8]

5. 가중치 적용: 가중치

\theta^i

를 사용하여 컨볼루션 결과를 조정한다.^[8]

6. 역변환: NTT 역변환을 통해 최종 곱셈 결과를 얻는다.

7. 모듈러 연산: 쇤하게-슈트라센 알고리즘은

2^n + 1

형태의 수로 나눈 나머지 연산을 사용한다. 이를 통해 비트 시프트와 덧셈 연산만으로 효율적인 계산이 가능하다.

8. 분할 정복: 이 알고리즘은 분할 정복 방식을 사용하여 문제를 더 작은 하위 문제로 나누어 해결한다.

9. 정규화: FFT 데이터를 특정 범위로 정규화하기 위해

2^{-m}

을 곱한다. 여기서

\frac{1}{n} \equiv 2^{-m} \bmod N(n)

이며, 여기서 m은 모듈러 곱셈 역원을 사용하여 구한다.^[14]

4. 알고리즘 개요

쇤하게-슈트라센 알고리즘은 분할 정복 방식을 사용하여 큰 정수의 곱셈을 작은 정수의 곱셈으로 분할하여 처리한다. 이 알고리즘은 다음과 같은 특징을 갖는다.

컨볼루션(합성곱) 활용: 두 숫자의 곱셈을 다항식 곱셈으로 변환하고, 컨볼루션 연산을 통해 효율적으로 계산한다.
고속 푸리에 변환(FFT) 및 수론 변환(NTT) 적용: 컨볼루션 계산을 위해 FFT 또는 NTT를 사용하여 시간 복잡도를 줄인다.^[7]
모듈러 연산: 중간 계산 과정에서 발생하는 큰 숫자를 다루기 위해 $2^n + 1$ 형태의 모듈러 연산을 사용한다.

이 알고리즘은 카라추바 알고리즘이나 툼-쿡 곱셈과 유사하게 분할, 평가 (FFT), 아다마르 곱, 보간 (역 FFT), 결합 순서로 진행된다.

4. 1. 알고리즘 단계

이 섹션에서는 두 개의 자연수

a, b

의 곱

ab

를

2^n+1

형태의 수로 나눈 나머지 연산을 계산하는 알고리즘의 단순화된 버전을 설명한다. 여기서

n=2^kM

은 어떤 고정된 숫자이다.

정수

a, b

는

D=2^k

개의

M

비트 블록으로 나누어지며, 실제 구현에서는 매개변수

M, k

사이의 적절한 균형을 맞추는 것이 중요하다. 이 알고리즘은

n

이

ab < 2^n+1

이 되도록 선택된다면 두 양의 정수를 곱하는 방법을 제공한다.

n=DM

을 신호

a

와

b

의 비트 수라고 하고,

D=2^k

는 2의 거듭제곱이다. 신호

a

와

b

를 각각

M

비트씩

D

개의 블록으로 나누어 결과 블록을 배열

A,B

로 저장한다.

이제 푸리에 변환을 위한 법을 선택한다.

M'

을

DM'\ge 2M+k

가 되도록 한다.

n'=DM'

을 놓고 배열

A,B

의 요소를 (임의 정밀도) 정수 모듈로

2^{n'}+1

로 간주한다.

2^{n'} + 1 \ge 2^{2M+k} + 1 = D2^{2M}+1

이므로 법은

a

와

b

를 곱할 때 발생할 수 있는 모든 캐리를 수용할 만큼 충분히 크다. 따라서 곱

ab

(모듈로

2^n+1

)는

A,B

의 컨볼루션을 평가하여 계산할 수 있다. 또한,

g=2^{2M'}

에 대해

g^{D/2}\equiv -1\pmod{2^{n'}+1}

이므로

g

는 모듈로

2^{n'}+1

인 원시

D

번째 단위근이다.

배열

A,B

의 이산 푸리에 변환을 단위근

g

를 푸리에 기저로 사용하여 링

\mathbb Z/(2^{n'}+1)\mathbb Z

에서 취하여 변환된 배열

\widehat A,\widehat B

를 구한다.

D=2^k

가 2의 거듭제곱이므로 고속 푸리에 변환을 사용하여 로그 시간 안에 이를 수행할 수 있다.

\widehat C_i=\widehat A_i\widehat B_i

(포인트별 곱)를 놓고, 단위근

g

를 다시 사용하여 배열

\widehat C

의 역변환

C

를 계산한다. 배열

C

는 이제 배열

A,B

의 컨볼루션이다. 마지막으로, 곱

ab\pmod{2^n+1}

는 다음을 평가하여 제공된다.

:

ab\equiv \sum_j C_j2^{Mj}\mod{2^n+1}.

밑이 B인 모든 숫자는 다음과 같은 다항식으로 표현할 수 있다.

:

X = \sum_{i=0}^N {x_iB^i}

두 숫자의 곱셈은 두 다항식의 곱으로 생각할 수 있다.

:

XY = \left(\sum_{i=0}^N {x_iB^i}\right)\left(\sum_{j=0}^N {y_iB^j}\right)

B^k

에 대해:

c_k =\sum_{(i,j):i+j=k} {a_ib_j} = \sum_{i=0}^k {a_ib_{k-i}}

이므로, 컨볼루션(convolution, 합성곱)이 존재한다.

원래 버전에서 NTT (수론 변환) 대신 사용되는 FFT (고속 푸리에 변환)을 컨볼루션 규칙과 함께 사용하면,^[7]

:

\hat{f}(a * b) =  \hat{f}\left(\sum_{i=0}^k a_ib_{k-i} \right) =  \hat{f}(a) \bullet \hat{f}(b).

즉,

C_k = a_k \bullet b_k

이다. 여기서

C_k

는 푸리에 공간에서의 해당 계수이다. 이는

\text{fft}(a * b) = \text{fft}(a) \bullet \text{fft}(b)

로도 쓸 수 있다.

푸리에 변환에 따른 선형성 때문에, 그리고 이러한 다항식이 계수당 하나의 고유한 항만으로 구성되어 있기 때문에 동일한 계수를 갖는다.

:

\hat{f}(x^n) = \left(\frac{i}{2\pi}\right)^n \delta^{(n)}

그리고

:

\hat{f}(a\, X(\xi) + b\, Y(\xi)) = a\, \hat{X}(\xi) + b\, \hat{Y}(\xi)

컨볼루션 규칙:

\hat{f}(X * Y) = \ \hat{f}(X) \bullet \hat{f}(Y)

FFT를 통해 컨볼루션 문제를 곱셈 문제로 축소했다.

각

C_k

의 다항식 보간법의 FFT를 찾음으로써 원하는 계수를 결정할 수 있다.

이 알고리즘은 분할 정복 방식을 사용하여 문제를 하위 문제로 나눈다. 다음 알고리즘은 표준 모듈식 쇤하게-슈트라센 곱셈 알고리즘(몇 가지 최적화 포함)이다.^[14]

쇤하게의 원래 구현에서는 Discrete Weighted Transform (DWT)를 사용하여 보다 효율적으로 컨볼루션을 수행하고 있다. 크누스의 ''The Art of Computer Programming''에서도 본 알고리즘이 소개되어 있다.^[28]

이 알고리즘은 카라추바 알고리즘이나 톰-3와 마찬가지로 분할·평가(고속 푸리에 변환)·아다마르 곱·보간(역 고속 푸리에 변환)·결합 순으로 진행된다.

입력인 ''x'' 와 ''y'' 그리고 정수 ''N''이 주어지면, 다음 알고리즘은 ''xy'' mod 을 계산한다. ''N''이 충분히 큰 경우, 단순히 ''xy'' 이다.

# 각 입력을 2^''k'' 개의 부분으로 분할하여 X와 Y로 한다.(예: 12345678 → (12, 34, 56, 78))

# 재귀적인 곱셈을 위해 작은 ''N''을 준비한다. 이를 위해 2''N''/2^''k'' + ''k'' 이상이고 2^''k'' 로 나누어 떨어지는 최소의 정수를 ''n''으로 한다.

# 역 방향 순환 컨볼루션에 의해, mod 에서의 ''X''와 ''Y''의 곱을 계산한다.

## 시프트 연산을 사용하여 X와 Y에 가중치 벡터 A를 곱한다.

## 수론 변환 고속 푸리에 변환을 사용하여 X와 Y의 이산 푸리에 변환을 계산한다. 여기서 모든 곱셈은 시프트 연산으로 수행된다.

## 재귀적으로 이 알고리즘을 적용하여, 변환 후 X와 Y의 요소를 곱한다(내적).

## 3.의 결과의 역 이산 푸리에 변환을 계산하여 벡터 C를 얻는다. 여기서도 모든 곱셈은 시프트 연산으로 수행된다. 이는 보간에 해당한다.

## 시프트 연산을 사용하여 벡터 C에 가중치 벡터의 역행렬 A⁻¹ 을 곱한다.

## 부호를 조정한다: 몇몇 요소는 음수가 된다. C의 j번째 최대 가능한 요소를 계산하여 을 초과하면 그것을 뺀다.

# 마지막으로, mod 에서 올림을 실행한다.

4. 2. 최적화 기법

어떤 임계점 이하에서는 툼-쿡 곱셈과 같은 다른 곱셈 알고리즘을 사용하는 것이 더 효율적이다.^[17]

\sqrt{2}

를 유한체

\mathrm{GF}(2^{n+2} +1)

에서

2^{n+2}

차 단위근으로 사용하여(이는

\theta^{2^{n+2}} \equiv 1 \pmod{2^{n+2} + 1}

방정식의 해이다) NTT (수론적 변환) 접근 방식에서 값을 가중하는 아이디어가 있다. 이는 정수 곱셈 시간을 10% 절약하는 것으로 나타났다.^[18]

m = N + h

를 사용하여,

uv \bmod{2^N +1}

및

(u \bmod{2^h})(v \bmod{2^h})

를 계산할 수 있다. CRT(중국인의 나머지 정리)와 결합하여 곱셈 uv의 정확한 값을 찾는다.^[19]

5. 구현 세부 사항

쇤하게-슈트라센 알고리즘은 특정 임계점 이하에서는 투음-쿡 곱셈과 같은 다른 곱셈 알고리즘을 사용하는 것이 더 효율적이다.^[17]

알고리즘의 개요는 다음과 같다.^[14]

1. 두 입력 숫자 a와 b를 각각 s 비트의 n개 계수로 분할한다. 최소 K + 1 비트를 사용하여 저장하고, 값 $2^K$ 의 인코딩을 허용한다.

2. (2.24)에 따라 계수 벡터에 θ의 거듭제곱으로 가중치를 부여하여 순환 이동을 수행한다.

3. 계수 $a_i$ 와 $b_j$ 를 섞는다.

4. $a_i$ 와 $b_j$ 를 평가한다. ω의 거듭제곱과의 곱셈은 순환 이동이다.

5. $Z/(2^K + 1)Z$ 에서 n개의 점별 곱셈 $c_k := a_k b_k$ 를 수행한다. SMUL이 재귀적으로 사용되는 경우, K를 매개변수로 제공한다. 그렇지 않으면 T3MUL과 같은 다른 곱셈 함수를 사용하고 그 후 $2^K + 1$ 을 모듈로 축소한다.

6. 곱 계수 $c_k$ 를 섞는다.

7. 곱 계수 $c_k$ 를 평가한다.

8. (2.25)에 따라 $c_k$ 에 반대 가중치를 적용한다. $\theta^{2n} \equiv 1$ 이므로 $\theta^{-k} \equiv \theta^{n-k}$ 가 성립한다.

9. $1/n \equiv 2^{-m}$ 으로 $c_k$ 를 정규화한다(다시 순환 이동).

10. $c_k$ 를 더하고 올림수를 전파한다. 음수 계수를 적절히 처리해야 한다.

11. $2^N + 1$ 을 모듈로 축소를 수행한다.

T3MUL = 툼-쿡 곱셈
SMUL = 쇤하게-슈트라센 곱셈
Evaluate = FFT/IFFT

\sqrt{2}

를 유한체

\mathrm{GF}(2^{n+2} +1)

에서

2^{n+2}

차 단위근으로 사용하여 (이는

\theta^{2^{n+2}} \equiv 1  \pmod {2^{n+2} + 1}

방정식의 해이다) 수론적 변환(NTT) 접근 방식에서 값을 가중하는 아이디어는 정수 곱셈 시간을 10% 절약하는 것으로 나타났다.^[18]

m = N + h

를 사용하여,

uv \bmod {2^N +1}

및

(u \bmod {2^h})(v \bmod 2^h)

를 계산할 수 있다. 중국인의 나머지 정리(CRT)와 결합하여 곱셈

uv

의 정확한 값을 찾는다.^[19]

이 변형은 이산 가중 변환을 활용하여 음사이클 컨볼루션을 보다 효율적으로 수행한다는 점에서 쇤하게의 원래 방법과 약간 다르다. 자세한 정보는 커누스의 ''The Art of Computer Programming''에서도 찾아볼 수 있다.^[16]

5. 1. 모듈러 연산 (Modular Arithmetic)

쇤하게-슈트라센 알고리즘은 효율적인 모듈러 연산을 필요로 한다. 특히,

2^n + 1

형태의 수로 나눈 나머지 연산을 효율적으로 계산해야 한다.
페르마 수와 메르센 수페르마 수와 메르센 수는 모듈러 연산에 적합한 수이다. 이들은 일반화된 페르마-메르센 수(Generalized Fermat-Mersenne Number, GSM)의 특수한 경우이다. GSM의 공식은 다음과 같다.^[11]

:

G_{q,p,n} = \sum_{i=1}^p q^{(p-i)n} = \frac{q^{pn}-1}{q^n-1}

:

M_{p,n} =  G_{2,p,n}

위 식에서

M_{2,2^k}

는 페르마 수이고,

M_{p,1}

는 메르센 수이다.
일반화된 페르마-메르센 수 (GSM)GSM은 중국인의 나머지 정리(CRT)에 사용될 수 있는 일련의 방정식을 생성하는 데 사용될 수 있다.^[12]

:

g^{\frac{(M_{p,n}-1)}{2}} \equiv -1  \pmod {M_{p,n}}

, 여기서 g는

x^2 \equiv g \pmod {M_{p,n}}

인 x가 존재하는 숫자이며,

N = 2^n

이라고 가정한다.

또한, 다음이 성립한다.

:

g^{2^{(p-1)n}-1} \equiv a^{2^n -1}  \pmod {M_{p,n}}

여기서 a는

\{1,2,4,...2^{n-1},2^n\}

의 원소를 순환 방식으로 생성하는 원소이다.

만약

N=2^t

, 여기서

1 \le t \le n

이면,

g_t = a^{(2^n-1)2^{n-t}}

이다.
모듈러 연산의 활용

2^n \equiv -1

in

\operatorname{GF}(2^n + 1)

and

\sqrt{2} \equiv -1

in

\operatorname{GF}(2^{n+2} + 1)

임을 주목하라. 이러한 후보에 대해, 유한체에서

\theta^N \equiv -1

이므로 우리가 원하는 방식으로 작동한다.

이러한 성질들은 쇤하게-슈트라센 알고리즘에서 수론적 변환(NTT)을 효율적으로 수행하는 데 사용된다.

5. 2. K 선택

Schönhage–Strassen algorithm|쇤하게-슈트라센 알고리즘^영어에서 주어진 비트 크기 N에 대해 효율적인 연산을 위해 적절한 K (N 비트를 나눌 그룹 수)를 찾는 공식은 다음과 같다.^[13]

:

E = \frac{\frac{2N}{K}+k}{n}

여기서 N은 최외각 수준의 비트 크기(

2^N + 1

에서 사용되는 것)이다. K는

\frac{N}{K}

개의 비트 그룹을 제공하며,

K = 2^k

이다.

n은 N과 k를 통해,

2N/K +k \le n = K2^x

를 만족하는 가장 작은 x를 찾아 구할 수 있다.

효율이 50% 이상이라고 가정하면,

\frac{n}{2} \le \frac{2N}{K}, K \le n

이고 k는 나머지 공식에 비해 매우 작으므로,

:

K \le 2\sqrt{N}

이는 매우 효과적인 연산에서 K는

2\sqrt{N}

로 상한이 정해지거나 점근적으로

\sqrt{N}

로 상한이 정해짐을 의미한다.^[13]

5. 3. 시프트 연산 최적화

알고리즘 과정에서 2의 거듭제곱과의 곱셈/나눗셈은 시프트 연산과 덧셈으로 대체될 수 있다. 이는 다음 성질을 이용한다.

: (2^''n'')^k ≡ (−1)^k mod (2^''n'' + 1)

이 성질을 이용하여, 수를 mod (2^N + 1)에서 쉽게 줄일 수 있다. 최하위 비트(오른쪽 끝)부터 시작하여 n 비트씩 묶어 처리한다. 첫 n 비트는 그대로 두고, 다음 n 비트는 빼고, 그 다음 n 비트는 더하는 식으로 모든 비트를 처리한다. 결과가 0에서 2ⁿ 범위에 없으면, 2^N + 1의 배수를 더하거나 빼서 정규화한다.

예를 들어, n = 3이고 법이 2³ + 1 = 9인 경우, 656은 다음과 같이 줄일 수 있다.

: 656 = 1 010 010 000₂ ≡ 000₂ − 010₂ + 010₂ − 1₂ = 0 − 2 + 2 − 1 = −1 ≡ 8 (mod 2³ + 1).

또한, 큰 시프트 연산도 효율적으로 수행할 수 있다. 0에서 2ⁿ 범위의 수 A에 2^k를 곱하는 경우, k를 n으로 나누어 k = qn + r (r < n) 형태를 얻는다. 그러면 다음이 성립한다.

: A(2^k) = A(2^{qn + r}) = A[(2ⁿ)^q(2^r)] ≡ (−1)^q × shl(A, r) (mod 2ⁿ + 1).

여기서 shl(A, r)은 A를 r 비트 왼쪽으로 시프트한 것이다. A는 2ⁿ 이하이고 r < n이므로, r 비트 왼쪽 시프트된 A는 최대 2n - 1 비트를 가지며, 한 번의 시프트 연산과 뺄셈(정규화)만으로 처리할 수 있다.

마지막으로, 2^k로 나눌 때는 2n이 원시근임을 이용하여 다음을 얻는다.

: 2²ⁿ ≡ 1 (mod 2ⁿ + 1)

따라서,

: A/2^k = A(2^−k) ≡ A(2^{2n − k}) = shl(A, (2n − k)) (mod 2ⁿ + 1)

6. 응용 분야

쇤하게-슈트라센 알고리즘은 다음과 같은 다양한 분야에서 활용된다.

암호학(Cryptography): RSA, 타원 곡선 암호 등 현대 암호 시스템은 큰 정수의 곱셈 연산을 기반으로 한다. 쇤하게-슈트라센 알고리즘은 암호 연산 속도를 향상시켜 보안 시스템의 효율성을 높이는 데 기여한다.^[1]
과학 연산(Scientific Computing): 천문학, 물리학, 기상학 등 과학 분야는 매우 큰 수의 계산이 필요하다. 쇤하게-슈트라센 알고리즘은 과학 연산의 정확성과 속도를 향상시키는 데 중요한 역할을 한다.
디지털 신호 처리(Digital Signal Processing): 쇤하게-슈트라센 알고리즘은 디지털 신호 처리 분야에서 효율성을 높이는 데 기여한다.^[1]
기타:
큰 소수 탐색: 메르센 소수와 같이 특정한 형태의 소수를 탐색하는 데 유용하다.
컴퓨터 대수 시스템: 컴퓨터 대수 시스템에서 큰 정수 연산을 빠르게 처리하는 데 사용된다.
금융 모델링: 암호화 알고리즘이나 복잡한 금융 계산 등 매우 큰 숫자를 다루는 분야에서 활용될 수 있다.

6. 1. 암호학 (Cryptography)

RSA^영어, 타원 곡선 암호 등 현대 암호 시스템은 큰 정수의 곱셈 연산을 기반으로 한다. 쇤하게-슈트라센 알고리즘은 암호 연산 속도를 향상시켜 보안 시스템의 효율성을 높이는 데 기여한다.^[1]

6. 2. 과학 연산 (Scientific Computing)

Scientific Computing|과학 연산^영어에서 천문학, 물리학, 기상학 등 과학 분야는 매우 큰 수의 계산이 필요하다. 쇤하게-슈트라센 알고리즘은 과학 연산의 정확성과 속도를 향상시키는 데 중요한 역할을 한다.

6. 3. 디지털 신호 처리 (Digital Signal Processing)

쇤하게-슈트라센 알고리즘은 디지털 신호 처리 분야에서 효율성을 높이는 데 기여한다.^[1] 이 섹션에서는

a

와

b

두 자연수의 곱

ab

를

2^n+1

형태의 수로 나눈 나머지 연산을 계산하는 알고리즘의 단순화된 버전을 제시한다. 여기서

n=2^kM

은 고정된 숫자이다.

n=DM

을 신호

a

와

b

의 비트 수라고 하고,

D=2^k

는 2의 거듭제곱이다. 신호

a

와

b

는 각각

M

비트씩

D

개의 블록으로 나누어 배열

A,B

에 저장된다.

DM'\ge 2M+k

가 되도록

M'

을 설정하고,

n'=DM'

을 놓는다. 배열

A,B

의 요소는 정수 모듈로

2^{n'}+1

로 간주된다.

2^{n'} + 1 \ge 2^{2M+k} + 1 = D2^{2M}+1

이므로, 이 법은

a

와

b

를 곱할 때 발생하는 모든 캐리를 수용할 수 있다. 따라서 곱

ab

(모듈로

2^n+1

)는

A,B

의 컨볼루션을 통해 계산 가능하다.

g=2^{2M'}

에 대해

g^{D/2}\equiv -1\pmod{2^{n'}+1}

이므로,

g

는 모듈로

2^{n'}+1

인 원시

D

번째 단위근이다.

배열

A,B

의 이산 푸리에 변환은 단위근

g

를 푸리에 기저로 사용하여 링

\mathbb Z/(2^{n'}+1)\mathbb Z

에서 수행되어 변환된 배열

\widehat A,\widehat B

를 얻는다.

D=2^k

가 2의 거듭제곱이므로, 고속 푸리에 변환을 사용하여 로그 시간 안에 이를 수행할 수 있다.

\widehat C_i=\widehat A_i\widehat B_i

(포인트별 곱)을 계산하고, 단위근

g

를 사용하여 배열

\widehat C

의 역변환

C

를 계산한다. 배열

C

는 배열

A,B

의 컨볼루션이다. 곱

ab\pmod{2^n+1}

는 다음을 통해 얻어진다.

:

ab\equiv \sum_j C_j2^{Mj}\mod{2^n+1}.

6. 4. 기타

쇤하게-슈트라센 알고리즘은 매우 큰 정수의 곱셈을 효율적으로 수행하는 알고리즘으로, 다음과 같은 다양한 분야에서 활용된다.

큰 소수 탐색: 메르센 소수와 같이 특정한 형태의 소수를 탐색하는 데 유용하다.
컴퓨터 대수 시스템: 컴퓨터 대수 시스템에서 큰 정수 연산을 빠르게 처리하는 데 사용된다.
금융 모델링: 암호화 알고리즘이나 복잡한 금융 계산 등 매우 큰 숫자를 다루는 분야에서 활용될 수 있다.

참조

_[1] 논문 Schnelle Multiplikation großer Zahlen
_[2] 논문 Fast Quantum Modular Exponentiation
_[2] 웹사이트 MUL_FFT_THRESHOLD https://gmplib.org/m[...] 2021-07-20
_[2] 웹사이트 MUL_FFT_THRESHOLD http://gmplib.org/de[...] 2011-11-03
_[2] 웹사이트 MUL_FFT_THRESHOLD https://gmplib.org/d[...] 2021-07-20
_[3] 컨퍼런스 Faster Integer Multiplication http://www.cse.psu.e[...]
_[3] 논문 Faster Integer Multiplication http://dx.doi.org/10[...]
_[3] 서적 Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation https://hal.inria.fr[...] ACM 2019-07-08
_[4] 논문 Integer multiplication in time $O(n \log n)$ https://hal.archives[...]
_[6] 웹사이트 ECMNET https://members.lori[...] 2023-04-09
_[7] 웹사이트 Efficient Multiplication of Somewhat Small Integers using Number-Theoretic Transforms https://eprint.iacr.[...] 2022
_[8] 웹사이트 Fast Multiplication of Large Integers: Implementation and Analysis of the DKSS Algorithm https://www.research[...]
_[9] 서적 Algorithm Design https://archive.org/[...] Pearson 2005
_[10] 웹사이트 A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm https://inria.hal.sc[...]
_[11] 웹사이트 Generalized Fermat-Mersenne Number Theoretic Transform https://www.research[...]
_[12] 웹사이트 Generalized Fermat-Mersenne Number Theoretic Transform https://www.research[...]
_[13] 웹사이트 A GMP-based Implementation of Schönhage-Strassen's Large Integer Multiplication Algorithm https://inria.hal.sc[...] 2007
_[14] 웹사이트 Fast Multiplication of Large Integers: Implementation and Analysis of the DKSS Algorithm https://www.research[...]
_[15] 서적 Prime Numbers – A Computational Perspective Springer
_[16] 서적 The Art of Computer Programming Addison-Wesley
_[17] 웹사이트 A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm https://inria.hal.sc[...]
_[18] 웹사이트 A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm https://inria.hal.sc[...] 2007
_[19] 웹사이트 A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm https://inria.hal.sc[...] 2007
_[20] 논문 Schnelle Multiplikation großer Zahlen
_[21] 컨퍼런스 Faster integer multiplication
_[22] 논문 Fast quantum modular exponentiation
_[23] 웹사이트 Overview of Magma V2.9 Features, arithmetic section
_[24] 기타 Can Schönhage multiplication speed up the RSA encryption or decryption?
_[25] 웹사이트 MUL_FFT_THRESHOLD http://gmplib.org/de[...] 2011-11-03
_[26] 웹사이트 An improved BigInteger class which uses efficient algorithms, including Schönhage–Strassen https://github.com/t[...] Oracle 2014-01-10
_[28] 서적 The Art of Computer Programming
_[29] 기타

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com