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

La transformada teórica de números inversos 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 inversos debe ser primo necesariamente. Pero si es primo, simplifica las cosas. Se puede realizar el NTT Inverso 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.intt( ) :

Puede realizar la Transformación Teórica de Números Inversos (NTT) de la secuencia. Se especializa en el anillo de cociente de la transformada discreta de Fourier (DFT) con Z/pZ para 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 INTT to perform on.

Returns : 
Number Theoretic Transform

Ejemplo 1 :

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

Producción :

Inverse NTT :  [600, 357, 183, 413]

Ejemplo #2:

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

Producción :

Inverse NTT :  [355, 710, 557, 69]