Recientemente he escuchado que el Número Teórico de la Transformación (NTT), que es una especialización de la Transformación Rápida de Fourier (FFT) sobre el anillo de módulo de un número entero, se puede utilizar para acelerar ciertos cálculos, si los operandos son transformados antes.
Si tengo las matrices y los vectores (con cientos o pocos miles de entradas) y quieren hacer de la matriz-matriz o matriz-vector multiplicación módulo de un número entero: NTT ser útil para acelerar las operaciones. Y si sí, ¿por qué/cómo?
Si tengo polinomios y quiero hacer el polinomio de la multiplicación de un polinomio anillo modulo otro polinomio (por ejemplo,$ x^n + 1$): NTT ser útil para aumentar la velocidad de los cálculos? Y si sí, ¿por qué/cómo?
Sé que la posible ventaja de NTT proviene de la reducción de la complejidad de la clase. Pero me pregunto si vale la pena hacer para la transformación - calculatation - back transformación pasos. Especialmente cuando estoy lidiando con el más pequeño de los números aproximados tamaño de 32 bits en una máquina de registro de una computadora normal.
