격자 기반 양자 내성 암호에서는 차수 n = 256인 다항식의 곱셈을 여러 번 수행한다. 계수끼리 모두 곱하는 소박한 방법으로는 약 n²회, 수론 변환(NTT)을 사용하는 방법으로는 약 n log₂ n회의 곱셈이 필요하다고 하면, NTT를 사용함으로써 곱셈 횟수가 대략 몇 분의 1이 되는지에 가장 가까운 것은?

정답: B. 약 32분의 1

소박한 방법으로는 n² = 256² = 65,536회, NTT를 사용하는 방법으로는 n log₂ n = 256 × 8 = 2,048회이므로, 65,536 ÷ 2,048 = 32로 약 32분의 1이 됩니다. 수론 변환은 고속 푸리에 변환과 같은 개념을 소수를 법으로 하는 정수의 세계에서 수행하는 변환으로, 변환한 뒤에는 계수별 곱셈만으로 끝납니다. ML-KEM은 계수를 q = 3329를 법으로 하여 다루며 NTT로 계산하는 것을 전제로 설계되어 있으므로, NTT 회로는 양자 내성 암호 가속기의 중심적인 부품이 됩니다. 또한 ML-KEM이나 ML-DSA는 행렬이나 난수를 만드는 데 SHA-3 계열의 함수(SHAKE)를 많이 사용하므로, 그 가속기도 효과가 있습니다.