Para llevar a cabo el algoritmo FFT en un campo finito (la Transformada Teórica de Números o Number Theoretic Transform), debe haber raíces -ésimas de la unidad de tal manera que sea una potencia de 2.
Idealmente, buscamos una gran potencia de 2 para poder multiplicar polinomios grandes. Existen varios campos finitos de uso común (casi todos los cuales tienen un nombre pegadizo asociado a ellos). Este artículo enumera algunos de los más comunes.
Como definición rápida, la característica de un campo es el número primo con el que tomamos el módulo, por lo que en el campo finito , es la característica. (Existen algunos matices con esta definición si consideramos extensiones de campos finitos, pero no queremos profundizar en eso ahora. Para nuestros propósitos, es un número primo y la característica del campo finito).
Como vimos en el Teorema Fundamental de los Grupos Cíclicos Finitos, un subgrupo existe si el orden del subgrupo divide al orden del grupo.
Por lo tanto, si el campo es amigable con FFT, entonces existe algún tal que y es una gran potencia de 2. En otras palabras, es divisible por una gran potencia de 2.
Esta lista no es exhaustiva; solo incluimos los campos relativamente conocidos al momento de la publicación.
Lista de campos amigables con FFT
Campo Goldilocks
El campo Goldilocks tiene una característica y una raíz -ésima de la unidad.
El siguiente código de Python comprueba que existe un subgrupo multiplicativo de orden en este campo.
q = 2**64 - 2**32 + 1
k = 2**32
assert (q - 1) % k == 0
Dado que la característica es menor a 64 bits, los elementos se pueden almacenar en una sola palabra en la mayor parte del hardware moderno (que suele ser de 64 bits).
Sin embargo, multiplicar dos números de 64 bits requiere temporalmente 128 bits, lo que hace necesario un registro adicional para la multiplicación.
Esto motiva el uso de un campo más pequeño que utilice solo 32 bits.
Campo Baby Bear
El campo Baby Bear utiliza una característica . Tiene una raíz -ésima de la unidad.
q = 2**31 - 2**27 + 1
k = 2**27
assert (q - 1) % k == 0
El nombre “Baby Bear” hace referencia al cuento de hadas de Goldilocks (Ricitos de Oro), donde la historia enfatiza el tamaño pequeño del Bebé Oso en comparación con la protagonista de la historia (Goldilocks).
Dado que el campo cabe en 32 bits, una computadora de 64 bits puede multiplicar dos elementos juntos en una sola palabra.
Campo Teddy Bear
El campo Teddy Bear utiliza una característica y tiene una raíz -ésima de la unidad.
q = 2**32 - 2**30 + 1
k = 2**30
assert (q - 1) % k == 0
En comparación con el campo Baby Bear, también cabe dentro de 32 bits, pero tiene un subgrupo multiplicativo que es ocho veces mayor.
El campo Teddy Bear fue introducido por Ingonyama en este artículo científico.
Campo Koala Bear
El campo Koala Bear es otro campo cuya característica cabe en 32 bits y tiene una raíz -ésima de la unidad.
q = 2**31 - 2**24 + 1
k = 2**24
assert (q - 1) % k == 0
Campo BN-128
El campo BN-128 se utiliza por su soporte para emparejamientos de curvas elípticas, pero también tiene un subgrupo multiplicativo relativamente grande que es de orden .
# curve_order = 21888242871839275222246405745257275088548364400416034343698204186575808495617
from py_ecc.bn128 import curve_order
k = 2**28
assert (curve_order - 1) % k == 0
El Campo STARK
La Cairo VM utilizada por Starknet tiene una característica y tiene una raíz -ésima de la unidad muy grande.
q = 2**251 + 17*2**192 + 1
k = 2**192
assert (q - 1) % k == 0
El BLS12-381
El BLS12-381 es otra curva elíptica amigable para emparejamientos cuyo orden de curva tiene una raíz -ésima de la unidad.
# curve_order = 52435875175126190479447740508185965837690552500527637822603658699938581184513
from py_ecc.bls12_381 import curve_order
k = 2**32
assert (curve_order - 1) % k == 0
Soporte en Bibliotecas
La biblioteca Plonky3 tiene bibliotecas para Goldilocks, Baby Bear y Koala Bear.