Este artículo es el tercero de una serie. Presentamos los campos finitos en el contexto de los circuitos para pruebas de conocimiento cero (zero-knowledge proofs). Los capítulos anteriores son P vs NP and its Application to Zero Knowledge Proofs y Arithmetic Circuits.

En el capítulo anterior sobre circuitos aritméticos, señalamos la limitación de que no podemos codificar el número $2/3$ porque no puede representarse con precisión en binario. También señalamos que no teníamos una forma explícita de manejar el desbordamiento (overflow).

Ambos problemas se pueden manejar sin problemas con una variante de la aritmética, que es popular en la criptografía en general, llamada campos finitos (finite fields).

Campos finitos

Dado un número primo p, podemos hacer un campo finito con p elementos tomando el conjunto de enteros $\set{0, 1, 2, …, p-1}$ y definiendo que la suma y la multiplicación se realicen módulo $p$. Comenzaremos limitándonos a campos donde el número de elementos es primo.

Por ejemplo, si el número primo $p$ es $7$, entonces los elementos en el campo finito son $\set{0, 1, 2, 3, 4, 5, 6}$. Cualquier número fuera de este rango ($≥ p$ o $< 0$) siempre se asigna a un número “equivalente” en este rango usando el módulo. La palabra técnica para “equivalente” es congruente.

El módulo calcula el resto al dividir el número por el número primo. Por ejemplo, si nuestro módulo es 7, el número 12 es congruente a 5, es decir, $12 \pmod 7 = 5$, y el número 14 es congruente a 0. De manera similar, cuando sumamos dos números, por ejemplo 3 + 5, la suma resultante de 8 es congruente a 1 (8 mod 7 = 1). La siguiente animación ilustra esto:

En Python, el cálculo mostrado arriba se puede computar como:

Copy
p = 7
result = (3 + 5) % p
print(result) # prints 1

En este capítulo, siempre que realicemos cálculos, expresaremos nuestro resultado como un número en el rango de $0…(p-1)$, que es el conjunto de elementos en nuestro campo finito p. Por ejemplo, 2 * 5 = 10, que “simplificamos” a 3 (módulo 7).

Nota cómo 3 + 5 “desbordó” (overflowed) el límite de 6. En los campos finitos, el overflow no es algo malo, definimos el comportamiento de desbordamiento como parte del cálculo. En un campo finito módulo 7, 5 + 3 se define como 1.

Los desbordamientos por debajo (underflows) también se manejan de manera similar. Por ejemplo, $3 - 5 = - 2$, pero en módulo 7 obtenemos $5$ porque $7 - 2 = 5$.

Cómo funciona la aritmética modular

En un lenguaje de programación típico, escribimos la suma en un campo finito como (6 + 1) % 7 == 0, pero en notación matemática, normalmente decimos

O de manera más general,

donde $a$ y $b$ son números en el campo finito, $c$ es el resto que mapea cualquier número $≥ p$ y $< 0$ de vuelta al conjunto $\set{0, 1, …, p - 1}$.

La notación $\pmod p$ significa que toda la aritmética se hace módulo $p$. Por ejemplo,

Es equivalente (en Python o C) a (a + b) % p == (c + d) % p.

La multiplicación funciona de manera similar multiplicando los números juntos, y luego tomando el módulo:

La operación de multiplicación anterior se puede visualizar de dos formas:

O alternativamente:

Nos referimos a un número en un campo finito como un “elemento”.

$p$ y el orden del campo

El número con el que calculamos el módulo lo llamaremos $p$. En todos nuestros ejemplos es un número primo. En el ámbito más amplio de las matemáticas, $p$ podría no ser necesariamente primo, pero solo nos ocuparemos de los casos donde $p$ es primo.

Debido a esta restricción, el orden del campo siempre es igual a $p$. El orden es la cantidad de elementos en el campo. El término general para el número con el que calculamos el módulo es la característica del campo.

Por ejemplo, si tenemos $p = 5$, los elementos son $\set{0, 1, 2, 3, 4}$. Hay 5 elementos, por lo que el orden de ese campo es 5.

La identidad aditiva de $p$

Cualquier elemento más $p$ es el mismo elemento. Por ejemplo, $(3 + 7) \pmod 7 = 3$. Considera los ejemplos en la siguiente animación:

Inverso Aditivo

Considera que $5 + (-5) = 0$.

En matemáticas, el inverso aditivo de $a$ es un número $b$ tal que $a + b = 0$. Generalmente, expresamos el inverso aditivo de un número colocando un signo negativo delante. $-a$ es, por definición, el número que sumado con $a$ da 0.

Reglas generales de los inversos aditivos

• El cero es su propio inverso aditivo.
• Cada número tiene exactamente un inverso aditivo.

Estas reglas de inverso aditivo también se aplican a los campos finitos. Aunque no tenemos elementos con signos negativos como $-5$, algunos elementos pueden “comportarse” como números negativos entre sí usando el operador de módulo.

En la aritmética regular, $-5$ es el número que, al sumarse con $5$, da como resultado $0$. Si nuestro campo finito es $p = 7$, entonces el $2$ puede considerarse como $-5$ porque $(5 + 2) \pmod 7 = 0$. Del mismo modo, el $5$ puede considerarse como $-2$ porque son el inverso aditivo el uno del otro. Para ser precisos, $-2$ es congruente a $5$ o $-2 \equiv 5 \pmod 7$.

Para calcular el inverso aditivo de un elemento, simplemente se calcula $p - a$, donde $a$ es el elemento del que intentamos encontrar el inverso aditivo. Por ejemplo, para encontrar el inverso aditivo de 14 módulo 23, calculamos $23 - 14 = 9$. Podemos ver que $14 + 9 \pmod {23} = 0$. $p$ es congruente a cero, por lo que esto equivale a calcular $-5$ como $0 - 5$.

Al igual que con los números reales:

• cada elemento en un campo finito tiene exactamente un inverso aditivo
• el cero es su propio inverso aditivo.

El patrón general para los inversos aditivos en un campo finito es que los elementos de la primera mitad del campo finito son los inversos aditivos de los elementos de la segunda mitad, como se muestra en la siguiente figura. El cero es la excepción, ya que es su propio inverso aditivo. Los números conectados por la línea verde son el inverso aditivo del otro en el campo $p = 7$:

Ejercicio: Digamos que elegimos un $p \geq 3$. ¿Cuáles, si los hay, valores distintos de cero son su propio inverso aditivo?

Inverso multiplicativo

Considera que $5 × (1/5) = 1$.

El inverso multiplicativo para $a$ es un número $b$ tal que $ab = 1$. Todo elemento excepto el cero tiene un inverso multiplicativo. Con “números regulares”, un inverso multiplicativo es $1 / \text{num}$. Por ejemplo, el inverso multiplicativo de $5$ es $1/5$, y el inverso multiplicativo de $19$ es $1/19$.

Aunque no tenemos números fraccionarios en los campos finitos, aún podemos encontrar pares de números que “se comportan como” fracciones al sumarse o multiplicarse juntos.

Por ejemplo, el inverso multiplicativo de $4$ en el campo finito $p = 7$ es $2$, porque $4 * 2 = 8$, y $8 \pmod 7 = 1$. Por lo tanto, $2$ “se comporta” como $1/4$ en el campo finito, o para ser precisos, $1/4$ es congruente a $2 \pmod 7$.

Reglas generales de los inversos multiplicativos en aritmética de campos finitos:

• El 0 no tiene un inverso multiplicativo
• El 1 es su propio inverso multiplicativo
• Cada número (excepto el 0) tiene exactamente un inverso multiplicativo (que podría ser sí mismo)
• el elemento de valor $(p - 1)$ es su propio inverso multiplicativo. Por ejemplo, en un campo finito de $p = 103$, el $1$ y el $102$ son sus propios inversos multiplicativos. En un campo finito de $p = 23$, el $1$ y el $22$ son sus propios inversos multiplicativos (la razón por la que esto es así se explica en la siguiente sección). Otro ejemplo: en el campo finito módulo 5, 1 es su propio inverso, y 4 es su propio inverso. $4 \times 4 = 16$, y $16 \pmod 5 = 1$.

Por qué el elemento de valor $p - 1$ es su propio inverso multiplicativo

Cuando multiplicamos $-1$ por sí mismo, obtenemos $1$. Por lo tanto, $-1$ es su propio inverso multiplicativo para los números reales. El elemento de valor $(p - 1)$ es congruente a $-1$. Por lo tanto, esperamos que $(p - 1)$ sea su propio inverso multiplicativo, y efectivamente ese es el caso.

Como otra forma de ver por qué $p - 1$ es su propio inverso multiplicativo, considera que $(p - 1)(p - 1) = p² - 2p + 1$. Dado que $p$ es congruente a $0$, entonces $p² - 2p + 1$ se simplifica a $0^2 - 2*0 + 1 = 1$.

Soluciones para circuitos aritméticos sobre campos finitos

Si consideramos el siguiente circuito aritmético sobre números regulares, esperamos que x = -1 sea la única asignación satisfactoria.

Copy
x * x === 1
x + 1 === 0

En un campo finito, la asignación satisfactoria es el elemento congruente a $-1$, o $p - 1$.

Calcular el inverso multiplicativo con el Pequeño Teorema de Fermat

El Pequeño Teorema de Fermat establece que

En otras palabras, si elevas un elemento distinto de cero a la potencia $p$, obtienes ese elemento de vuelta. Algunos ejemplos:

• $3⁵ \pmod 5 = 3$
• $4⁷ \pmod 7 = 4$
• $14⁵³ \pmod {53} = 14$

Ahora considera si dividimos ambos lados de $aᵖ = a \pmod p$ por $a$ (recuerda, $a ≠ 0$):

Podemos escribir el resultado como

Esto significa que $aᵖ⁻² \pmod p$ es el inverso multiplicativo de $a$, ya que $a$ por $aᵖ⁻²$ es 1.

Algunos ejemplos:

• El inverso multiplicativo de $3$ en el campo finito $p = 7$ es $5$. $3⁷⁻² = 5 \pmod 7$
• El inverso multiplicativo de 8 en el campo finito $p = 11$ es $7$. $8¹¹⁻² = 7 \pmod {11}$

La ventaja de este enfoque es que podemos usar el precompilado expmod en Ethereum para calcular el inverso modular en un contrato inteligente.

En la práctica, esta no es una forma ideal de calcular inversos multiplicativos porque elevar un número a una potencia grande es costoso desde el punto de vista computacional. Las bibliotecas que calculan el inverso multiplicativo utilizan algoritmos más eficientes internamente. Sin embargo, cuando una de esas bibliotecas no está disponible, y se desea una solución rápida y simple, y calcular un exponente grande no es excesivamente costoso, se puede utilizar el Pequeño Teorema de Fermat.

Calcular el inverso multiplicativo con Python

Usando Python 3.8 o posterior, podemos hacer pow(a, -1, p) para calcular el inverso multiplicativo de a en el campo finito p. El primer argumento de pow es la base, el segundo es el exponente, y el tercero es el módulo.

Ejemplo:

Copy
p = 17
print(pow(5, -1, p))
# 7
assert (5 * 7) % p == 1

Ejercicio: Encuentra el inverso multiplicativo de 3 módulo 5. Solo hay 5 posibilidades, así que pruébalas todas y observa cuáles funcionan.

Ejercicio: ¿Cuál es el inverso multiplicativo de 50 en el campo finito $p = 51$? No necesitas Python para calcular esto, revisa los principios descritos en “Reglas generales de los inversos multiplicativos”.

Ejercicio: Usa Python para calcular el inverso multiplicativo de 288 en el campo finito de p = 311. Puedes comprobar tu trabajo validando que (288 * answer) % 311 == 1.

La suma de inversos multiplicativos es consistente con la suma “regular” de fracciones

En un campo finito de p = 7, los números 2 y 4 son inversos multiplicativos el uno del otro porque $(2 \times 4) \pmod 7 = 1$. Esto significa que en el campo finito $p = 7$, $4$ es congruente a $1/2$ y $2$ es congruente a $1/4$.

Decimos que $4$ es congruente a $1/2$ en el campo finito de $p = 7$ porque $2 \times \mathsf{mul\_inv}(2) = 1$. El inverso multiplicativo de $2$ es $4$ en este campo finito, por lo que podemos tratar a $4$ como $1/2$.

Con números reales, si sumamos $1/2 + 1/2$, esperamos obtener $1$. Lo mismo ocurre en un campo finito. Dado que $4$ “se comporta como” $1/2$, esperamos que $4 + 4 \pmod 7 = 1$, y en efecto lo hace.

Podemos codificar el número $5/6$ en un campo finito pensándolo como la operación $5 * (1/6)$, o $5 \times \mathsf{mul\_inv}(6)$.

Considera que $1/2 + 1/3 = 5/6$. Si nuestro campo finito es $p = 7$, entonces $1/2$ es el inverso multiplicativo de $2$, $1/3$ es el inverso multiplicativo de 3, y $5/6$ es $5$ por el inverso multiplicativo de 6:

Copy
p = 7
one_half = pow(2, -1, p)
one_third = pow(3, -1, p)
five_over_six = (pow(6, -1, p) * 5) % p

assert (one_half + one_third) % p == five_over_six
# True

La forma general de calcular una “fracción” en un campo finito es el numerador por el inverso multiplicativo del denominador, módulo p:

Copy
def compute_field_element_from_fraction(num, den, p):
	inv_den = pow(den, -1, p)
	return (num * inv_den) % p

No es posible hacer esto cuando el denominador es un múltiplo de p. Por ejemplo, $1/7$ no puede ser representado en el campo finito $p = 7$ porque pow(7, -1, 7) no tiene solución. El módulo toma el resto después de la división, y el resto de $7/7$ es cero, o más generalmente, $7/d$ es cero cuando $d$ es un múltiplo de $7$. El inverso multiplicativo significa que podemos multiplicar un número y su inverso para obtener $1$, pero si uno de los números es cero, no hay nada por lo que podamos multiplicar cero para obtener 1.

Ejercicio: ejecuta pow(7, -1, 7) en Python. Deberías ver que se lanza una excepción, ValueError: base is not invertible for the given modulus. $7$ mod $7$ es igual a cero. No hay nada por lo que podamos multiplicar cero para obtener $1$.

La “división” en campos finitos no sufre pérdida de precisión

Si dividimos 1 / 3 en la mayoría de los lenguajes de programación, sufriremos una pérdida de precisión porque $0.\overline{3}$ no es representable en binario.

Sin embargo, 1 / 3 en un campo finito es simplemente el inverso multiplicativo de 3.

Esto significa que el circuito aritmético

Copy
x + y + z === 1;
x === y;
y === z;

tiene una solución exacta cuando se hace en un campo finito. Esto no sería posible de hacer de manera confiable si usáramos números de punto fijo o punto flotante como los tipos de datos para nuestros circuitos aritméticos (considera que sumar 0.33333 + 0.33333 + 0.33333 resultará en 0.99999 en lugar de 1).

La siguiente implementación en Python ilustra el circuito:

Copy
p = 11

# x, y, z have value 1/3
x = pow(3, -1, 11)
y = pow(3, -1, 11)
z = pow(3, -1, 11)

assert x == y;
assert y == z;
assert (x + y + z) % p == 1

Los elementos de campos finitos no tienen una noción tradicional de “par” o “impar”

Decimos que un número es “par” si puede dividirse entre dos sin dejar resto.

En un campo finito, cualquier elemento puede dividirse entre 2 sin dejar resto.

Es decir, “dividir entre dos” en realidad es multiplicar por el inverso multiplicativo de 2, y eso siempre resultará en otro elemento del campo sin “resto”.

Sin embargo, si tenemos una representación binaria del elemento del campo, entonces podemos comprobar si el elemento es par o impar si se convirtiera (cast) a un número entero. Si el bit menos significativo es 1, entonces el número es impar (si se interpreta como un número entero, no como un elemento de campo finito).

Biblioteca de campos finitos en Python

Debido a que puede ser un poco tedioso tener que escribir pow y % p constantemente en Python, el lector puede desear usar la biblioteca galois en su lugar (los campos finitos a veces se denominan campos de Galois). Se puede instalar con python3 -m pip install galois.

A continuación, traducimos el código de suma de fracciones de la sección anterior $(1/2 + 1/3 = 5/6)$ para que use la biblioteca galois en su lugar. La biblioteca sobrescribe los operadores matemáticos para funcionar en un campo finito:

Copy
import galois
GF7 = galois.GF(7) # GF7 is a class that wraps 7

one_half = GF7(1) / GF7(2)
one_third = GF7(1) / GF7(3)
five_over_six = GF7(5) / GF7(6)

assert one_half + one_third == five_over_six  

La operación 1 / GF(a) calcula el inverso multiplicativo de a.

La biblioteca galois puede calcular el inverso aditivo agregando un signo negativo al frente:

Copy
negative_two = -GF7(2)
assert negative_two + GF7(2) == 0

La multiplicación de fracciones también es consistente

Usemos un campo finito p = 11 para este ejemplo.

Con números regulares sabemos que $1/3 * 1/2 = 1/6$.

Hagamos esta misma operación en un campo finito:

Copy

import galois
GF = galois.GF(11)

one_third = GF(1) / GF(3)
one_half = GF(1) / GF(2)
one_sixth = GF(1) / GF(6)

assert one_third * one_half == one_sixth

Ejercicio: usa la biblioteca galois para comprobar que $3/4 * 1/2 = 3/8$ en el campo finito $p = 17$.

a × b ≠ 0 para todo a, b distinto de cero

Ningún par de elementos puede multiplicarse para obtener cero en un campo finito a menos que uno de los elementos sea cero en sí mismo. Esto también es cierto para los números regulares.

Para entender esto, considera el campo finito $p = 7$. Para multiplicar dos números juntos y obtener $0$ como resultado, entonces uno de los términos $a$ debe ser un múltiplo de 7, de modo que $a \pmod 7$ sea cero. Sin embargo, ninguno de $\set{0, 1, 2, 3, 5, 6}$ es un múltiplo de 7, por lo que esto no puede suceder.

Haremos referencia a este hecho frecuentemente cuando diseñemos circuitos aritméticos. Por ejemplo, si sabemos que

Copy
x₁ * x₂ * ... * xₙ ≠ 0 

Entonces podemos estar seguros de que todas las variables x₁, x₂, xₙ son distintas de cero — incluso si no conocemos sus valores.

Así es como podemos usar este truco para un circuito aritmético realista. Supongamos que tenemos señales x₁, x₂, x₃. Deseamos restringir que al menos una de estas señales tenga el valor 8 sin especificar cuál lo tiene. Primero calculamos el inverso aditivo de 8 a_inv(8) para nuestro campo. Luego hacemos:

(x₁ + a_inv(8))(x₂ + a_inv(8))(x₃ + a_inv(8)) === 0

Esto se podría escribir como

(x₁ - 8)(x₂ - 8)(x₃ - 8) === 0

con la comprensión de que -8 es el inverso aditivo de 8 para nuestro campo finito.

Mientras una de las señales tenga el valor 8, entonces ese término será cero y toda la expresión se multiplicará dando cero. Este truco se basa en dos hechos:

• Si todos los términos son distintos de cero, no hay forma de que la expresión se evalúe a cero
• El inverso aditivo de 8 es único, y 8 es el inverso aditivo único para el inverso aditivo de 8. En otras palabras, no hay ningún valor excepto el 8 que resulte en que 8 + inv(8) sea cero.

Por lo tanto, el circuito aritmético (x₁ + a_inv(8))(x₂ + a_inv(8))(x₃ + a_inv(8)) === 0 establece que al menos uno de x₁, x₂, xₙ tiene el valor 8.

Las operaciones en campos finitos son asociativas, conmutativas y distributivas

Al igual que con las matemáticas regulares, en la aritmética modular se mantienen las propiedades asociativa, conmutativa y distributiva, es decir:

asociativa

$(a + b) + c = a + (b + c) \pmod p$

conmutativa de la suma

$(a + b) = (b + a) \pmod p$

conmutativa de la multiplicación

$ab = ba \pmod p$

distributiva

$a(b + c) = ab + ac \pmod p$

Raíces cuadradas modulares

En “matemáticas regulares”, los números cuadrados perfectos tienen raíces cuadradas enteras. Por ejemplo, 25 tiene una raíz cuadrada de 5, 49 tiene una raíz cuadrada de 7, y así sucesivamente.

Los elementos en un campo finito no necesitan ser cuadrados perfectos para tener una raíz cuadrada

Considera que $5 × 5 \pmod {11} = 3$. Esto significa que la raíz cuadrada de 3 es 5, módulo 11. Debido a cómo los campos finitos se reinician (wrap around), los elementos de un campo finito no tienen que ser cuadrados perfectos para tener una raíz cuadrada.

Al igual que las raíces cuadradas regulares, que tienen dos soluciones: una positiva y una negativa, las raíces cuadradas modulares en un campo finito también tienen dos soluciones. La excepción es el elemento 0, que solo tiene a 0 como su raíz cuadrada.

En el campo finito módulo 11, los siguientes elementos tienen raíces cuadradas:

Ejercicio: Verifica que las raíces cuadradas declaradas en la tabla sean correctas en el campo finito módulo 11.

Observa que la segunda raíz cuadrada siempre es el inverso aditivo de la primera raíz cuadrada, al igual que en los números reales.

Por ejemplo:

• En las matemáticas regulares, las raíces cuadradas de $9$ son $3$ y $-3$, donde ambas son el inverso aditivo de la otra.
• En un campo finito de $p = 11$, las raíces cuadradas de 9 son 3 y 8. El 8 es el inverso aditivo de 3 porque $8 + 3 \pmod {11}$ es $0$, de la misma forma que $3$ es el inverso aditivo de $-3$.

Los elementos 2, 6, 7, 8 y 10 no tienen raíces cuadradas modulares en el campo finito $p = 11$. Esto se puede descubrir elevando al cuadrado cada elemento del 0 al 10 inclusive, y observando que 2, 6, 7, 8 y 10 nunca se producen.

Copy
numbers_with_roots = set()
p = 11
for i in range(0, p):
    numbers_with_roots.add(i * i % p)

print("numbers_with_roots:", numbers_with_roots)
# numbers_with_roots: {0, 1, 3, 4, 5, 9}

Ten en cuenta que el 3 no es un cuadrado perfecto, pero sí tiene una raíz cuadrada en este campo finito.

Calcular la raíz cuadrada modular

La raíz cuadrada modular se puede calcular en Python con la biblioteca libnum. A continuación, calculamos la raíz cuadrada de 5 módulo 11. El tercer argumento para las funciones has_sqrtmod_prime_power y sqrtmod_prime_power se puede establecer en 1 para nuestros propósitos.

Copy
# install libnum with `python -m pip install libnum`

from libnum import has_sqrtmod_prime_power, sqrtmod_prime_power
has_sqrtmod_prime_power(5, 11, 1) # True
list(sqrtmod_prime_power(5, 11, 1)) # [4, 7]
# square roots generally have two solutions. 4 and 7 are the square roots of 5 (mod 11)

Cuando p puede escribirse como 4k + 3 donde k es un número entero, entonces la raíz cuadrada modular se puede calcular de la siguiente manera:

Copy
def mod_sqrt(x, p):
	assert (p - 3) % 4 == 0, "prime not 4k + 3"
	exponent = (p + 1) // 4
	return pow(x, exponent, p) # x ^ e % p

La función anterior devuelve una de las raíces cuadradas de x módulo p. La otra raíz cuadrada puede calcularse obteniendo el inverso aditivo del valor devuelto. Si el número primo no tiene la forma 4k + 3, entonces se debe usar el Algoritmo de Tonelli-Shanks para calcular la raíz cuadrada modular (que es el que implementa la biblioteca libnum mostrada arriba).

La implicación de esto es que el circuito aritmético x * x === y puede tener dos soluciones. Por ejemplo, en un campo finito p = 11, podría parecer que el circuito aritmético x * x === 4 solo admite el valor 2 porque -2 no es un elemento del campo finito. Sin embargo, ¡esa suposición está muy equivocada! La asignación x = 9, que es congruente a -2, también satisface el circuito.

Ejercicio: Usa el fragmento de código anterior para calcular la raíz cuadrada modular de 5 en el campo finito de p = 19. El código solo te dará una de las respuestas. ¿Cómo puedes calcular la otra?

Sistemas de ecuaciones lineales en campos finitos

Como se señaló en el capítulo anterior, un circuito aritmético es esencialmente un sistema de ecuaciones. Los sistemas de ecuaciones lineales en un campo finito comparten muchas propiedades con un sistema de ecuaciones lineales sobre números regulares. Sin embargo, hay algunas diferencias que inicialmente pueden resultar inesperadas. Dado que los circuitos aritméticos se calculan sobre campos finitos, debemos entender dónde pueden presentarse estas sorprendentes desviaciones.

Un sistema de ecuaciones lineales es una colección de ecuaciones de líneas rectas con un conjunto de incógnitas (variables) que intentamos resolver juntas. Para encontrar la solución única a un sistema de ecuaciones lineales, debemos encontrar un valor numérico para cada variable que satisfaga todas las ecuaciones del sistema simultáneamente.

Los sistemas de ecuaciones lineales con números reales tienen:

1. Ninguna solución: lo que significa que las dos ecuaciones representan líneas que son paralelas en dos dimensiones, o que nunca se cruzan en tres dimensiones o más.

2. Una solución: lo que significa que las líneas se intersectan en un punto.

3. Infinitas soluciones: si las dos ecuaciones representan la misma línea, entonces hay una cantidad infinita de puntos de intersección, y el sistema de ecuaciones lineales tiene un número infinito de soluciones.

Los sistemas de ecuaciones de campos finitos también tienen:

1. ninguna solución o

2. una solución o

3. $p$ soluciones, es decir, tantas soluciones como el orden del campo.

Sin embargo, el hecho de que un sistema de ecuaciones lineales sobre los números reales tenga cero, una o infinitas soluciones no implica que el mismo sistema de ecuaciones lineales sobre un campo finito vaya a tener también cero, una o p soluciones.

La razón por la que enfatizamos esto es porque usamos circuitos aritméticos y una asignación a las señales para codificar nuestra solución a un problema en NP. Sin embargo, dado que los circuitos aritméticos están codificados con campos finitos, podemos terminar codificando el problema de una manera que no capture el comportamiento de las ecuaciones que estamos tratando de modelar.

Los siguientes tres ejemplos muestran cómo puede cambiar el comportamiento de un sistema de ecuaciones cuando se realiza sobre un campo finito.

Ejemplo 1: Un sistema de ecuaciones con una solución sobre números regulares puede tener p soluciones en un campo finito

Por ejemplo, graficamos:

Tiene una solución: $(1, 0)$ para los números reales, pero sobre el campo finito $p = 11$, tiene 11 soluciones: $\set{(0, 6), (1, 0), (2, 5), (3, 10), (4, 4), (5, 9), (6, 3), (7, 8), (8, 2), (9, 7), (10, 1)}$.

¡No asumas que un sistema de ecuaciones (circuito aritmético) que tiene una sola solución en números reales tiene una sola solución en un campo finito!

A continuación graficamos las soluciones para los sistemas de ecuaciones sobre los campos finitos para ilustrar que ambas ecuaciones “se intersectan en todas partes”, es decir, tienen el mismo conjunto de puntos que satisfacen ambas ecuaciones:

Esto podría parecer extremadamente contraintuitivo — veamos cómo sucede. Si resolvemos las ecuaciones originales:

para $y$ obtenemos:

$1/2$ es el inverso multiplicativo de $2$. En un campo finito de $p = 11$, $6$ es el inverso multiplicativo de $2$, es decir, $2 * 6 \pmod {11} = 1$. Por lo tanto, $x + 2y = 1$ y $6x + y = 6$ son en realidad la misma ecuación en el campo finito $p = 11$. Es decir, la ecuación $y = 1/2 - 1/2x$ al codificarse en un campo finito es $y = \mathsf{mul\_inv}(2) - \mathsf{mul\_inv}(2)x$, que es $y = 6 - 6x$, lo que es igual a la otra ecuación en el sistema.

Ejemplo 2: Un sistema de ecuaciones con una solución sobre números regulares puede no tener ninguna solución en un campo finito

También de forma contraintuitiva, un sistema de ecuaciones con una sola solución sobre números reales puede no tener solución en un campo finito:

Claramente, este sistema de ecuaciones tiene un punto de intersección, pero sobre un campo finito no tiene solución.

A continuación mostramos el gráfico de las dos ecuaciones en un campo finito:

Ejercicio: Escribe un código para probar por fuerza bruta cada combinación de (x, y) en el rango x = 0..10, y = 0..10 para verificar que el sistema anterior no tiene solución sobre el campo finito de p = 11.

¿Por qué este sistema de ecuaciones no tiene solución en el campo finito $p = 11$?

Si resolvemos

para números reales, obtenemos las soluciones

Las fracciones anteriores no tienen un elemento congruente en el campo finito p = 11.

Recuerda que dividir entre un número es equivalente a multiplicar por su inverso multiplicativo. Además, recuerda que el orden del campo (en este caso 11) no tendrá un inverso multiplicativo, porque el orden del campo es congruente a 0.

El inverso multiplicativo de a es el valor b tal que a * b = 1. Sin embargo, si a = 0 (o cualquier valor congruente a él) entonces no hay solución para b. Por lo tanto, las expresiones que escribimos para las soluciones en los números reales no pueden traducirse a elementos de nuestro campo finito.

Por ende, las soluciones (x, y) anteriores no son parte del campo finito. De ahí que, en un campo finito p = 11, x + 2y = 1 y 7x + 3y = 2 sean líneas paralelas.

Para ver esto desde otro ángulo, podríamos resolver las ecuaciones para y obteniendo:

Vimos en la sección anterior que 6 es el inverso multiplicativo de 2, así que la primera ecuación tiene una “pendiente” de -1/2 que es -6 o equivalentemente 5 en el campo finito. En la segunda ecuación, calculamos la pendiente multiplicando -7 por el inverso multiplicativo de 3: (-7 * pow(3, -1, 11)) % 11 = 5. Ahora mostramos que sus pendientes son iguales en un campo finito.

La pendiente es el coeficiente de x en la forma y = c + bx. Para las dos ecuaciones anteriores, la primera pendiente es -1/2 y la segunda pendiente es -7/3. Si convertimos ambas fracciones a un elemento en el campo finito de p = 11, obtenemos el mismo valor de 5:

Copy
import galois
GF11 = galois.GF(11)

negative_1 = -GF11(1)
negative_7 = -GF11(7)

slope1 = GF11(negative_1) / GF11(2)
slope2 = GF11(negative_7) / GF11(3)

assert slope1 == slope2 # 5 == 5

La implicación de este hecho para el circuito aritmético:

Copy
x + 2 * y === 1
7 * x + 3 * y === 2

es que el circuito aritmético no tiene una asignación satisfactoria (witness) en un campo finito p = 11.

Ejemplo 3: Un sistema de ecuaciones con cero soluciones sobre números regulares puede tener p soluciones en un campo finito

Las siguientes dos fórmulas trazan líneas que son paralelas y, por lo tanto, no tienen solución sobre los reales:

Sin embargo, sobre el campo finito p = 11, tiene 11 soluciones: $\set{(0, 7), (1, 1), (2, 6), (3, 0), (4, 5), (5, 10), (6, 4), (7, 9), (8, 3), (9, 8), (10, 2)}$. Esas soluciones se grafican a continuación:

Ejercicio: Convierte las dos ecuaciones a su representación en campo finito y observa que son iguales.

Supongamos que codificamos este sistema de ecuaciones como un circuito aritmético:

Copy
x + 2 * y === 3
4 * x + 8 * y === 1

Para el campo finito que estamos utilizando, nuestras restricciones son redundantes a pesar de que “se ven diferentes”. Es decir, dos restricciones de apariencia diferente en realidad restringen a que $x$ e $y$ tengan los mismos valores.

Polinomios en campos finitos

En el capítulo sobre Circuitos Aritméticos, usamos el polinomio x(x - 1) === 0 para forzar a que x solo pueda ser 0 o 1. Esto se podría escribir como una ecuación polinómica. Para hacerlo, expandimos completamente nuestra expresión hasta que se represente como potencias separadas de x, cada una multiplicada por un coeficiente. En este caso: x² - x === 0.

La suposición de que el polinomio x² - x === 0 solo tiene las soluciones 0 o 1 en un campo finito (al igual que con los números reales) es correcta en este caso. Sin embargo, en general, no se debe asumir que las raíces de un polinomio sobre números reales tienen las mismas raíces en un campo finito. Mostraremos algunos contraejemplos más adelante.

No obstante, los polinomios en campos finitos comparten muchas propiedades con los polinomios sobre números reales:

• Un polinomio de grado $d$ tiene como máximo $d$ raíces. Las raíces de un polinomio $p(x)$ son los valores $r$ tales que $p(r) = 0$.
• Si sumamos dos polinomios $p_1$ y $p_2$, el grado de $p_1 + p_2$ será como máximo $\max(\deg(p_1), \deg(p_2))$. Es posible que el grado de $p_1 + p_2$ sea menor que $\max(\deg(p_1), \deg(p_2))$. Por ejemplo, $p_1=x³ + 5x + 7$, y $p_2 = -x³$.
• Sumar polinomios en un campo finito sigue las leyes asociativa, conmutativa y distributiva.
• Si multiplicamos dos polinomios $p_1$ y $p_2$, las raíces del producto serán la unión de las raíces de $p_1$ y $p_2$.

Grafiquemos $y = x² \pmod {17}$ como ejemplo.

El dominio de $x$ son los elementos del campo finito, y la salida (rango) también debe ser un miembro del campo finito. Es decir, nota cómo todos los valores de $x$ e $y$ se encuentran en el intervalo de $[0,16]$. Un polinomio sobre un campo finito solo puede tener valores de $x$ e $y$ menores a $p$.

El equivalente de $y = -x²$ en el campo finito $p = 17$ es $y = 16x² \pmod {17}$, ya que 16 es el inverso aditivo de 1 en ese campo finito. El polinomio $y = 16x² \pmod {17}$ está graficado a continuación:

Los polinomios que no tienen raíces en los números reales pueden tener raíces en un campo finito

Al igual que en nuestros ejemplos anteriores con sistemas de ecuaciones lineales, no se debe asumir que un polinomio con ciertas raíces en los números reales tiene las mismas raíces en un campo finito.

A continuación, graficamos $y = x² + 1$ en el campo finito $p = 17$. En los números reales, $y = x² + 1$ no tiene raíces reales. Pero en un campo finito, tiene dos raíces en $4$ y $13$, marcadas en puntos rojos a continuación:

Expliquemos ahora por qué $y = x² + 1$ no tiene raíces en los números reales pero sí tiene raíces en el campo finito $p = 17$. En el campo finito $p = 17$, el 17 es congruente a cero. Así que si introducimos un valor en $x$ de modo que $x² + 1$ se convierta en $17$, entonces el polinomio generará cero, no $17$. Podemos resolver $x² + 1 = 17$ para $x² = 17 - 1 = 16$. En un campo finito de $p = 17$, $x² = 16$ tiene las soluciones $4$ y $13$. Por lo tanto, $y = x² + 1$ tiene raíces $4$ y $13$ en el campo finito $p = 17$.

Los polinomios con raíces reales pueden no tener raíces en un campo finito

Considera el polinomio $y = x² − 5$. Podemos ver que tiene raíces en $\sqrt{5}$ y $-\sqrt{5}$. Sin embargo, si lo graficamos sobre un campo finito módulo 17, podemos ver que nunca cruza el eje x:

No hay raíces porque $\sqrt{5}$ no puede ser representado en un campo finito módulo 17. Sin embargo, en el campo finito $p = 11$, entonces habría dos raíces porque 5 tiene raíces cuadradas modulares en el campo finito de $p = 11$.

Limitaciones en circuitos aritméticos para Pruebas ZK

Si deseamos escribir un circuito aritmético para demostrar “Conozco la raíz del polinomio $y = x² − 5$” usando un circuito aritmético sobre un campo finito, entonces podríamos encontrarnos con el problema de no poder codificar $\sqrt{5}$. Es decir, sobre los números reales, $y = x² − 5$ tiene una raíz de $\sqrt{5}$, pero esto no se puede expresar en algunos campos finitos. Dependiendo de $p$, el circuito aritmético x² === 5 puede no tener ningún testigo (witness) satisfactorio.

Polinomios en campos finitos con Python

Al experimentar con circuitos aritméticos, a veces es útil escribir código en Python para simularlos. Cuando nuestro circuito aritmético tiene forma polinómica, podemos usar la biblioteca galois de antes para probar su comportamiento. Los siguientes ejemplos de código ilustran cómo usar esta biblioteca para trabajar con polinomios.

Sumar polinomios en un campo finito

En el código a continuación, definimos dos polinomios: p1 = x² + 2x + 102 y p2 = x² + x + 1 y luego los sumamos simbólicamente para producir 2x² + 3x. Observa que los términos de los coeficientes constantes se suman dando cero en el campo finito p = 103.

Copy
import galois
GF103 = galois.GF(103) # p = 103

# we define a polynomial x^2 + 2x + 102 mod 103
p1 = galois.Poly([1,2,102], GF103)

print(p1)
# x^2 + 2x + 102

# we define a polynomial x^2 + x + 1 mod 103
p2 = galois.Poly([1,1,1], GF103)

print(p1 + p2)
# 2x^2 + 3x

La biblioteca galois es lo suficientemente inteligente como para interpretar los enteros negativos como inversos aditivos, como lo demuestra el siguiente código:

Copy
import galois
GF103 = galois.GF(103) # p = 103

# We can input "-1" as a coefficient, and that will
# automatically be calculated as `p - 1`
# -1 becomes 102 in a field p = 103
p3 = galois.Poly([-1, 1], GF103)
p4 = galois.Poly([-1, 2], GF103)

print(p3)
# 102x + 1
print(p4)
# 102x + 2

Multiplicar polinomios en un campo finito

Podemos multiplicar polinomios entre sí:

Copy
print(p3 * p4)
# x^2 + 100x + 2

Observa que p3 y p4 son polinomios de grado 1 y su producto es un polinomio de grado 2.

Encontrar las raíces de polinomios en un campo finito

Encontrar raíces de polinomios sobre campos finitos es un tema aparte (consulta la página de Wikipedia sobre algoritmos para factorizar polinomios sobre campos finitos). La biblioteca galois puede calcular las raíces con la función roots. Esto puede ser útil para verificar que las restricciones aritméticas en forma polinómica realmente crean las restricciones previstas.

Copy
print((p3 * p4).roots())
# [1, 2]

Cosas a tener en cuenta de la biblioteca galois

La biblioteca aplica silenciosamente la función floor (entero más cercano hacia abajo) a los números de punto flotante pasados como coeficientes:

Copy
# The galois library will silently convert
# floats into a integer
galois.Poly([2.5], GF103)
# Poly(2, GF(103))

La biblioteca lanzará un error (revertirá) si se le pasa un número mayor o igual a p:

Copy
# The follow code fails because we cannot
# have coefficients the order of the field or higher
galois.Poly([103], GF103)
# ValueError: GF(103) arrays must have elements in `0 <= x < 103`, not [103].

Aprende más con RareSkills

Consulta nuestro Libro de ZK para obtener más información sobre las Pruebas de Conocimiento Cero (Zero Knowledge Proofs).

Problemas de práctica

En los problemas a continuación, usa un campo finito p de 21888242871839275222246405745257275088548364400416034343698204186575808495617. Ten en cuenta que la biblioteca galois tarda un poco en inicializar un objeto GF, galois.GF(p), de este tamaño.

1. Un desarrollador crea un circuito aritmético x * y * z === 0 y x + y + z === 0 con la intención de restringir todas las señales para que sean cero. Encuentra un contraejemplo a esto en el que se cumplan las restricciones, pero no todas las variables x, y, y z sean 0.
2. Un desarrollador crea un circuito con el polinomio x² + 2x + 3 === 11 y prueba que el 2 es una solución. ¿Cuál es la otra solución? Pista: escribe el circuito como x² + 2x - 8 === 0 y luego factoriza el polinomio a mano para encontrar las raíces. Finalmente, calcula el elemento congruente de las raíces en el campo finito para encontrar la otra solución.

Publicado originalmente el 29 de abril de 2024