Reto sobre retículos: ¿sabrías explicar por qué el ejemplo no es correcto?

 Buscando recursos en Internet sobre retículos y sus aplicaciones encontré dos trabajos de final de grado muy interesantes. Sin desmerecer lo más mínimo la calidad de los mismos, en dichos trabajos, para ejemplificar el problema que conté aquí sobre que el vector devuelto por el algoritmo de Babai no tiene por qué ser el más cercano incluyen las siguientes imágenes (en realidad son el mismo ejemplo).

Chen, J. (2023): GGH: un criptosistema basat en reticles. Treball Final del Grau de Matemàtiques, p. 16. Universitat de Barcelona.

Guitart Torra, J. (2024): Didàctica del criptosistema GGH. Treball Final del Grau de Matemàtiques, p. 12. Universitat de Barcelona.

 En ambos trabajos justifican el fallo del algoritmo de Babai por ser una base "mala" (poco ortogonal).

 Pero este ejemplo no es correcto dado que los vectores representados como base del retículo, aunque son linealmente independientes, no son en realidad una base del retículo representado. Es decir, no es que sea una base "mala" y por eso no funcione bien el algoritmo de Babai, sino que no es ni tan siquiera base. ¿Sabrías explicar por qué? 

Problema del vector más cercano (CVP) en un retículo

Definición del problema: 

Sea $\varLambda$ un retículo completo sobre $\mathbb{R}^n$ y sea $\vec{w} \in \mathbb{R}^n$.

Queremos encontrar un vector $\vec{z} \in \varLambda$ tal que:

$$\|\vec{w}-\vec{z}\| = mín\{\|\vec{w}-\vec{b}\|, \forall \vec{b} \in \varLambda\}$$

Es decir, dado un vector del espacio queremos encontrar el vector del retículo más cercano al primero. Esto se conoce como el Problema del Vector más Cercano (CVP, por las siglas en inglés "Closest Vector Problem").

 

Teniendo en cuenta que la región fundamental de un retículo es un n-paralelepípedo, es inmediato ver la relación con las entradas anteriores (1 y 2) en las que se plantea encontrar el vértice del n-paralelepípedo más cercano a un punto.

Resumiendo, para dimensiones altas el método exhaustivo consistente en calcular la distancia con todos los vértices del n-paralelepípedo tiene un coste computacional demasiado elevado. 

Por otra parte, el algoritmo de Babai solo ofrece garantías de obtener la solución correcta si la base es lo "suficientemente ortogonal". Pero a esto además le añadimos que con bases que tienen mucho defecto de ortogonalidad (muy "lejos" de ser ortogonales) resulta que el vector más cercano ni tan siquiera tiene porqué ser vértice del n-paralelepípedo que lo contiene.

Puede verse que hay un punto naranja (del retículo) más próximo a $Q$ que los vértices del n-paralelepípedo que lo contiene

Con todo lo anterior, podemos concluir lo siguiente sobre la resolución del problema del vector más próximo en un retículo: una persona que conozca una base "bastante próxima" a ser ortogonal podrá realizar los cálculos de manera relativamente sencilla, mientras que otra persona que conozca una base "suficientemente lejos" de ser ortogonal tendrá mucha más dificultad para resolverlo.

Vértice de un n-paralelepípedo más cercano a un punto. Algoritmo de Babai.

 En una entrada anterior planteé el siguiente problema:

 Sea $\mathcal{F}$ un n-paralelepípedo (sólido) generado por el conjunto de vectores linealmente independientes $B = \{\vec{b}_1,...,\vec{b}_n\}$. Sea $P\in\mathcal{F}$ un punto de dicho n-paralelepípedo. ¿Cuál es el vértice del n-paralelepípedo más cercano a $P$?

Expliqué y ejemplifiqué una posible estrategia consistente en el método exhaustivo, es decir, comprobar todos los posibles vértices. Concluí la entrada con la observación de que el número de vértices crece de manera exponencial con la dimensión y esto supone un problema de coste computacional en dimensiones grandes.

En esta entrada vamos a trabajar otra posible estrategia, basada en el algoritmo de Babai, desarrollado por el matemático húngaro László Babai.

El fundamento detrás del procedimiento es relativamente sencillo.

Si $P\in\mathcal{F}$ entonces $P$ se puede escribir como combinación lineal de la base $B$:

$$P = \sum_{i=1}^{n}{a_i·\vec{b}_i}$$

Lo que hacemos es redondear al entero los coeficientes $0 \leq a_i \leq 1$ de la combinación lineal:

$$z_i = redondear(a_i)$$

Entonces, el vértice del n-paralelepípedo más próximo a $P$ viene dado por:

$$V = \sum_{i=1}^{n}{z_i·\vec{b}_i}$$

 

Ejemplo: Hagamos este método con el mismo ejemplo que utilizamos en el método exhaustivo, en $\mathbb{R}^2$.

$B=\{(30, 3), (5, 0)\}$ y el punto del paralelogramo $Q=(25.5, 2.5)$. Queremos hallar el vértice del paralelogramo más cercano a $Q$.

 Primero calcularemos la combinación lineal de la base $B$ que da el punto $Q$:

$$\vec{a} = B^{-1} · \overrightarrow{OQ} =\begin{pmatrix}30 & 5\\3 & 0\end{pmatrix}^{-1} · \begin{pmatrix}25.5 \\ 2.5\end{pmatrix} \simeq \begin{pmatrix}0.8333333333333333 \\ 0.10000000000000053\end{pmatrix}$$

Ahora redondeamos los coeficientes obtenidos:

$$\vec{z} = \begin{pmatrix}1 \\ 0\end{pmatrix}$$

Y calculamos a qué vértice corresponde dicha combinación lineal:

$$\overrightarrow{OV} = B · \vec{z} = \begin{pmatrix}30 & 5\\3 & 0\end{pmatrix} · \begin{pmatrix}1 \\ 0\end{pmatrix} = \begin{pmatrix}30 \\ 3\end{pmatrix}$$

Es decir, el vértice más cercano al punto $Q$ es (30, 3). (Coincide con el obtenido por el método exhaustivo)

Los cálculos del ejemplo han sido realizados con wxMaxima:

 

Desde un punto de vista geométrico e informal podríamos decir que el procedimiento anterior es equivalente a dividir con "hiperplanos medianeros" el n-paralelepípedo y seleccionar el vértice del "trozo" en el que queda el punto.

 

 El algoritmo de Babai rebaja considerablemente el coste computacional, dado que no necesita recorrer todos los vértices del n-paralelepípedo y se basa en operaciones bastante rápidas desde el punto de vista del cálculo computacional.

Sin embargo, el algoritmo de Babai presenta un gran problema: solo en determinadas condiciones la solución que devuelve es la correcta.

Veamos esto con un ejemplo. Seguimos utilizando la misma base que en el ejemplo anterior, pero cambiamos el punto a "aproximar" (encontrar el vértice más cercano) por $R=(30, 2.7)$.

Los cálculos del algoritmo devuelven el vértice $(35, 3)$ como el más cercano al punto $R$.

 

Sin embargo, esto no es cierto. El vértice más cercano es claramente el $(30, 3)$. 

 

Puede observarse en la representación gráfica que, tras trazar las medianas, el punto cae en el "trozo" del vértice $(35, 3)$ y por eso es la respuesta que devuelve el algoritmo de Babai. Pero no es el vértice más cercano.

Llegados a este punto lo razonable es descartar por completo este algoritmo porque ni tan siquiera devuelve la solución correcta.

Sin embargo, el algoritmo sí funciona con fiabilidad cuando la base es ortogonal (o "cerca" de ser ortogonal).

¿Y esto tiene alguna utilidad práctica? Habrá que esperar a las siguientes entradas para averiguarlo. 

Razón de ortogonalidad de Hadamard con Python

 En una entrada anterior hablé sobre la razón de ortogonalidad de Hadamard:

$$H(B) = \sqrt[n]{\frac{|det(B)|}{\prod_{i=1}^{n}\|\vec{b}_i\|}} $$

Podemos realizar un script en Python para calcular dicha razón, utilizando la librería NumPy:

import numpy as np

def razon_hadamard(B):
    # Calculamos el valor absoluto del determinante de la matriz
    det = np.abs(np.linalg.det(B))
    # Si el determinante es 0 la matriz no es una base y la función devuelve 0
    if not det:
        return 0
    n = len(B)
    # Definimos una variable prod_norm que calcula el producto de la norma de cada vector (columna)
    prod_norm = np.prod(np.linalg.norm(B, axis=0))
    # Devolvemos la razón
    return (det / prod_norm) ** (1/n) 

 

By www.python.org - www.python.org, GPL,

 https://commons.wikimedia.org/w/index.php?curid=34991651

 

Medir la ortogonalidad de una base

En la entrada anterior hice un repaso rápido de qué son las bases ortogonales. Ahora voy a tratar el siguiente tema:

¿Hay alguna manera de cuantificar si una base está cerca o lejos de ser ortogonal?

La respuesta es sí.

Una manera de hacerlo es utilizando una aplicación de la desigualdad de Hadamard.

Dada una base $B = \{ \vec{b}_1, ..., \vec{b}_n \}$ del espacio euclídeo $\mathbb{R}^n$:

$$|det(B)| \leq \prod_{i=1}^{n}\|\vec{b}_i\|$$

Desde el punto de vista geométrico, la desigualdad anterior nos aporta una cota superior del volumen del n-paralelepídedo formado por $B$.

Pero para el caso que nos ocupa, es muy útil conocer que dicha desigualdad se convierte en igualdad cuando la base es ortogonal por lo que nos permite definir la siguiente "razón de ortogonalidad de Hadamart":

$$\frac{|det(B)|}{\prod_{i=1}^{n}\|\vec{b}_i\|} $$

 Dicho valor estará comprendido en el intervalo $(0,1]$ y será exactamente 1 cuando la base sea ortogonal. Cuanto más "cerca" esté una base de ser ortogonal, más cerca de 1 estará el valor de la razón anterior. Cuanto más "lejos" esté una base de ser ortogonal, más cerca de 0 estará dicho valor.

Desde un punto de vista intuitivo e informal, estamos diciendo que si fijamos el módulo de los vectores que generan un n-paralelepídedo entonces el volumen es máximo cuando estos son ortogonales (en el momento en el que variamos alguno de los ángulos el volumen del n-paralelepípedo baja). Por tanto, si comparamos el volumen del n-paralelepípedo generado por los vectores de la base con el volumen máximo (caso ortogonal) podemos tener una idea de si la base está "cerca" o "lejos" de ser ortogonal.

Vamos a calcular dicha razón en los ejemplos de la entrada anterior en $\mathbb{R}^3$.

Comenzamos con la base canónica $C = \{(1,0,0),(0,1,0),(0,0,1)\}$:

 

 $|det(C)|=1$

 $\|(1,0,0)\|=\sqrt{1^2+0^2+0^2}=1$ 

 $\|(0,1,0)\|=\sqrt{0^2+1^2+0^2}=1$ 

 $\|(0,0,1)\|=\sqrt{0^2+0^2+1^2}=1$

Por tanto,

$$\frac{|det(C)|}{\prod_{i=1}^{n}||\vec{c}_i||} = \frac{1}{1} = 1$$

Es decir, como el valor da 1 podemos afirmar que la base es ortogonal.

 

En el caso de la otra base utilizada, $D = \{(1,0,0),(1,1,1),(0,2,1)\}$ 

 $|det(D)|=1$

 $\|(1,0,0)\|=\sqrt{1^2+0^2+0^2}=1$ 

 $\|(1,1,1)\|=\sqrt{1^2+1^2+1^2}=\sqrt{3}$ 

 $\|(0,2,1)\|=\sqrt{0^2+2^2+1^2}=\sqrt{5}$

 Por tanto,

$$\frac{|det(D)|}{\prod_{i=1}^{n}\|\vec{d}_i\|} = \frac{1}{\sqrt{15}} = \frac{\sqrt{15}}{15} \simeq 0.2581$$

Da un valor alejado de 1 por lo que podemos afirmar que la base "está lejos" de ser ortogonal. 

 

En realidad resultaría de utilidad tener una "medida" normalizada y comparable entre dimensiones. Si añadimos una raíz n-ésima tendremos una especie de "media geométrica del grado de normalidad por vector". Así pues, es más frecuente utilizar la siguiente expresión cuando se habla de la razón de ortogonalidad de Hadamart:

$$H(B) = \sqrt[n]{\frac{|det(B)|}{\prod_{i=1}^{n}\|\vec{b}_i\|}} $$

Otros autores hablan del defecto de ortogonalidad de una base definiéndola de la siguiente manera:

$$\vartriangle(B) = \frac{\prod_{i=1}^{n}\|\vec{b}_i\|}{|det(B)|} $$

de manera que cuánto mayor es el cociente "menor" es la ortogonalidad de la base (que sigue siendo 1 para bases ortogonales).

PD: Entrada de Wikipedia sobre el matemático francés Jacques Hadamard. 

Bases ortogonales

Es sabido que en el espacio euclídeo $\mathbb{R}^n$ un conjunto de $n$ vectores linealmente independientes forman una base del espacio.

Decimos que una base es ortogonal cuando los vectores de la base son ortogonales dos a dos, es decir, que su producto escalar es 0:

$$ b_{i} · b_{j} = 0; \forall i,j \in \{1,...,n\} \mid i \neq j$$

Por ejemplo, en $\mathbb{R}^3$ la base canónica $\{(1,0,0),(0,1,0),(0,0,1)\}$ es una base ortogonal. Todos los productos escalares dan 0:

$(1,0,0)·(0,1,0)=0+0+0=0$

$(1,0,0)·(0,0,1)=0+0+0=0$

$(0,1,0)·(0,0,1)=0+0+0=0$

Los vectores forman ángulos rectos entre ellos.

Sin embargo, la base $\{(1,0,0),(1,1,1),(0,2,1)\}$ no es una base ortogonal. Por ejemplo, el siguiente producto escalar no da 0:

$(1,1,1)·(0,2,1)=0+2+1=3 \neq 0$

Existen vectores que no forman un ángulo recto.