# 고속 푸리에 변환 (Fast Fourier Transform, FFT)

고속 푸리에 변환(FFT)은 일정한 간격으로 샘플링한 신호(시간 영역)를 주파수 성분(주파수 영역)으로 바꾸는 이산 푸리에 변환(DFT)을, 직접 계산할 때의 O(n²) 대신 O(n log n) 연산으로 계산하는 알고리즘들의 총칭입니다. 1965년 쿨리와 튜키가 널리 알린 분할 정복 방식이 대표적입니다.

## 자세히 알아보기

DFT는 n개의 값 x₀…x_{n−1}을 X_k = Σ x_j·ω^{jk}(ω는 1의 원시 n제곱근)로 바꿉니다. FFT의 핵심은 이 합을 짝수 번째와 홀수 번째 항으로 나누면 길이 n/2짜리 DFT 두 개로 표현된다는 점입니다. 이를 반복하면 log₂n 단계의 '나비(butterfly)' 연산만으로 전체 변환이 끝납니다. n이 2의 거듭제곱일 때 가장 단순하지만, 다른 길이에 대한 혼합 기수·블루스타인 알고리즘도 있습니다.

FFT는 신호 처리뿐 아니라 다항식 곱셈의 핵심 도구입니다. 두 다항식을 FFT로 '값 표현'으로 바꾸면 곱셈이 각 점의 곱으로 끝나고, 역 FFT로 계수를 되찾습니다. 같은 원리를 복소수 대신 유한체 위에서 하면 수론 변환(NTT)이 되는데, 반올림 오차가 없어 암호에 적합합니다.

## 블록체인·암호화폐에서는

- 영지식 증명: zk-SNARK(PLONK, Groth16 등)와 zk-STARK 증명기는 회로를 다항식으로 바꾸고 다항식을 계산·보간하는 데 유한체 FFT(NTT)를 대량으로 씁니다. 롤업 증명 생성 시간의 상당 부분이 FFT와 다중 스칼라 곱셈에서 나오며, GPU 가속의 주요 대상입니다. STARK 계열은 64비트 연산에 맞춘 '골디락스' 소수 p = 2^64 − 2^32 + 1처럼 FFT 친화적인 체를 고릅니다.
- 양자 내성 암호: NIST 표준 ML-KEM(FIPS 203)과 ML-DSA(FIPS 204)는 다항식 곱셈을 NTT로 수행하고, Falcon 서명은 복소수 FFT를 사용합니다. 블록체인의 양자 내성 전환 논의에서 이 알고리즘들이 후보로 검토됩니다.
- 부채널 분석: 전력 측정 신호를 FFT로 주파수 영역에서 분석해 잡음을 걸러내기도 합니다.

## 쉽게 말하면

FFT는 화음을 개별 음으로 분해하는 계산을 '반으로 나누고 또 나누는' 요령으로 엄청나게 빠르게 해 주는 방법입니다.

## 예시

n = 1,048,576(2^20)일 때 직접 DFT는 약 10^12번의 곱셈이 필요하지만, FFT는 대략 n log₂n ≈ 2 × 10^7 수준의 연산으로 끝납니다.

---
출처: https://achivx.kr/glossary/fast-fourier-transform-fft-%EA%B3%A0%EC%86%8D-%ED%91%B8%EB%A6%AC%EC%97%90-%EB%B3%80%ED%99%98-fft/ · ACHIVX 용어 사전 · 수정일 2026-10-20