Python | Transformación teórica de números

La transformada teórica de números es una generalización del teorema de la transformada rápida de Fourier. Se obtiene reemplazando e^(-2piik/N) por una n-ésima raíz unitaria primitiva. Entonces, esto significa que, en lugar de los números complejos C, use la transformación sobre el anillo cociente Z/pZ . La teoría se basa y utiliza los conceptos de campos finitos y teoría de números.

El módulo de transformación teórica de números debe ser primo necesariamente. Pero si es primo, simplifica las cosas. Se puede realizar el NTT con un módulo compuesto. Para módulo:

• enésima raíz de la unidad ^existencia
• inverso multiplicativo de n

Una transformada teórica de números es básicamente una transformada de Fourier . Además, suponga que se da una transformada de Fourier discreta normal y se puede hacer en forma de array multiplicando los datos con una array de Fourier. Supongamos N = 4. Entonces, la array puede ser –

[ 1   1    1    1  ]
[ 1   w   w^2  w^3 ]
[ 1  w^2  w^4  w^6 ]
[ 1  w^3  w^6  w^9 ]

sympy.discrete.transforms.ntt( ) :

Puede hacer Transformación Teórica de Números (NTT) de la secuencia.
Se especializa en el anillo de cociente de la transformada discreta de Fourier (DFT) con Z/pZ para los números primos en lugar de números complejos.

Automáticamente, la secuencia se completa con cero a la derecha porque la FFT radix-2 requiere el número de punto de muestra como una potencia de 2.

Parameters : 
-> seq       : [iterable] sequence on which DFT is to be applied.
-> prime no. : [Integer] prime modulus for NTT to perform on.

Returns : 
Number Theoretic Transform

Ejemplo 1 :

# import sympy 
from sympy import ntt
  
# sequence 
seq = [15, 21, 13, 44]
  
prime_no = 3 * 2**8 + 1
  
# ntt
transform = ntt(seq, prime_no)
print ("NTT : ", transform)

Producción :

NTT :  [93, 114, 732, 659]

Ejemplo 2:

# import sympy 
from sympy import ntt
  
# sequence 
seq = [153, 321, 133, 44, ]
  
# Prime modulus of the form (m * 2**k + 1)
prime_no = 3 * 2**8 + 1
  
# ntt
transform = ntt(seq, prime_no)
print ("NTT : ", transform)

Producción :

NTT :  [651, 276, 690, 533]