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.

Particiones de $\mathbb{R}^n$ utilizando la región fundamental de un retículo

 La entrada anterior finalizó observando que con la región fundamental de un retículo completo podemos teselar todo el espacio $\mathbb{R}^n$.

Teselado de $\mathbb{R}^2$ con la región fundamental $\mathcal{F}(\varLambda(C))$.

 

 Esto es equivalente a afirmar que el conjunto $\{\vec{v}+\mathcal{F}(\varLambda) \mid \vec{v} \in \varLambda \}$ es una partición de $\mathbb{R}^n$. Es decir, que si hacemos la traslación de la región fundamental utilizando todos los vectores del retículo cubrimos todo el espacio y los "trozos" no se solapan.

 

Ejemplo de 2 traslaciones de una región fundamental

 

Así pues, conociendo una base $B$ de un retículo completo $\varLambda(B)$, podemos caracterizar de manera única cualquier punto/vector de $\mathbb{R}^n$ como la suma de un vector del retículo $\varLambda(B)$ con un vector de la región fundamental $\mathcal{F}(\varLambda(B))$.

 

Por ejemplo, si retomamos el retículo completo sobre $\mathbb{R}^2$ generado por $B = \{(5, 3), (5, 0)\}$ podemos escribir el vector $\overrightarrow{OP}=(9.2,6.8) \in \mathbb{R}^2$ como la suma de un vector del retículo $\vec{w}_1=(5,6) \in \varLambda(B)$ y un vector de la región fundamental $\vec{t}_1=(4.2,0.8) \in \mathcal{F}(\varLambda(B))$.

 

 

 

 

Región fundamental de un retículo

 Sea $\varLambda$ un retículo completo sobre $\mathbb{R}^n$. Sea $B$ una base que genera el retículo $\varLambda$.

Llamamos región fundamental del retículo $\varLambda(B)$ al conjunto:

$$\mathcal{F}(\varLambda(B)) = \{ \sum_{i=1}^{n}t_i·\vec{b_i} \mid t_i \in [0,1) \wedge \vec{b_i} \in B; \forall i \in \{1,...,n\} \}$$

Dicha región fundamental también es conocida como dominio fundamental o paralelepípedo fundamental.

A modo de ejemplo, retomamos el retículo completo sobre $\mathbb{R}^2$ generado por $B = \{ (5, 3), (5, 0) \}$

 

Su región fundamental tiene la siguiente representación gráfica (importante observar la frontera):

 

Una vez definida la región fundamental, podemos realizar las siguientes observaciones:

• El $\vec{0}$ siempre pertenece a la región fundamental, independientemente de la base que genera el retículo $\varLambda$.
• Excluyendo el $\vec{0}$, los vectores de la región fundamental NO pertenecen al retículo $\varLambda$.
• Si cambiamos la base generadora del retículo, la región fundamental asociada también cambia. 

Si en el mismo retículo completo del ejemplo anterior cogemos la base $C = \{(0,3), (5,0)\}$, la región fundamental queda representada de la siguiente manera:

Sin embargo,

• aunque cambie la región fundamental, el "volumen n-dimensional" de la región fundamental (n-paralelepípedo o paralelótopo) es invariante. ¿Por qué? Porque se calcula con el determinante y se explicó un resultado al respecto en la anterior entrada.
• Con la región fundamental podemos teselar todo el espacio $\mathbb{R}^n$.

Teselado de $\mathbb{R}^2$ con la región fundamental $\mathcal{F}(\varLambda(C))$.

 

 

Determinante de un retículo

 Sea $\varLambda$ un retículo completo sobre $\mathbb{R}^n$. Sea $B$ una base que genera el retículo $\varLambda$.

 Podemos definir el determinante del retículo como el valor absoluto del determinante de la matriz $B$:

$$det(\varLambda) = |det(B)|$$

Dicho resultado es independiente de la base escogida, dado que si tenemos otra base $C$ del retículo $\varLambda$, en la entrada anterior vimos que:

$\varLambda(B) = \varLambda(C) \Longleftrightarrow \exists U \in M_{nxn}(\mathbb{Z}) \mid U$ es invertible y $C = B · U$ 

 Por tanto, si escogemos otra base $C$ que genere el mismo retículo, como U es invertible:

 $$|det(C)|= |det(B · U)| = |det(B) · det(U)| = |det(B)| · |det(U)| = |det(B)| · 1 = |det(B)|$$

 

Ejemplo:

 Utilizamos de nuevo el retículo completo $\varLambda$ sobre $\mathbb{R}^2$ generado por la base $B = \pmatrix{5 && 5 \\ 3 && 0}$.

 

 El determinante de dicho retículo es:

$$det(\varLambda) = |det(B)| = |det\pmatrix{5 && 5 \\ 3 && 0}| = |5 · 0 - 5 · 3| = |-15| = 15$$

Bases que generan el mismo retículo

En la teoría de retículos sobre $\mathbb{R}^n$ hay un resultado muy interesante que es el siguiente: 

Sean $\varLambda(B)$ y $\varLambda(C)$ dos retículos completos sobre $\mathbb{R}^n$ generados por las bases $B$ y $C$ respectivamente.

$\varLambda(B) = \varLambda(C) \Longleftrightarrow \exists U \in M_{nxn}(\mathbb{Z}) \mid U$ es invertible y $B = C · U$ 

Voy a destacar dos aplicaciones del resultado anterior.

APLICACIÓN 1. Si conocemos las bases de 2 retículos completos, podemos saber si generan el mismo retículo. Como $C$ es invertible en $M(\mathbb{R})$ (por ser base):

$$B = C · U \Leftrightarrow C^{-1} · B = C^{-1} · C · U \Leftrightarrow C^{-1} · B = I · U \Leftrightarrow C^{-1} · B = U$$ 

Por tanto, si $C^{-1} · B \in M(\mathbb{Z})$ (todos sus elementos son enteros) y es invertible en $M(\mathbb{Z})$ (su determinante es 1 o -1), entonces $B$ y $C$ generan el mismo retículo.

 

Ejemplo: 

En la entrada anterior utilizamos la siguiente base $B = \pmatrix{5 && 5 \\ 3 && 0}$ de un retículo completo sobre $\mathbb{R}^2$.

 

Y acabé afirmando que era exactamente el mismo retículo que generaría el conjunto $C = \pmatrix{0 && 5 \\ 3 && 0}$ o el conjunto $D = \pmatrix{-5 && 0 \\ 3 && -3}$.

Vamos a realizar la comprobación con $D$. Es decir, queremos llegar a la conclusión de que $B$ y $D$ generan el mismo retículo.

 

Calculamos

$D^{-1} · B = \pmatrix{-5 && 0 \\ 3 && -3}^{-1} · \pmatrix{5 && 5 \\ 3 && 0} = \pmatrix{-1 && -1 \\ -2 && -1}$

 

Ahora calculamos su determinante:

$|D^{-1} · B| = \begin{vmatrix}-1 && -1 \\ -2 && -1\end{vmatrix} = -1$

 

Así pues, hemos visto que todos sus elementos son enteros y que el resultado del determinante es -1. Por tanto, podemos afirmar que $B$ y $D$ generan el mismo retículo.

 

Nota: las operaciones anteriores las he realizado con wxMaxima.

 

 APLICACIÓN 2. Si tenemos una base $B$ de un retículo completo $\varLambda(B)$, podemos construir otra base $C$ que genera el mismo retículo multiplicando $B$ por una matriz $U \in M_{nxn}(\mathbb{Z})$ con determinante 1 o -1.

 

Ejemplo: 

 Utilizamos el retículo completo del ejemplo anterior, generado por $C = \pmatrix{0 && 5 \\ 3 && 0}$.

Ahora creamos una matriz aleatoria con elementos enteros y cuyo determinante sea 1 o -1.

$U = \begin{pmatrix}2283 & -118\\1838 & -95\end{pmatrix}$; $|U| = -1$ 

Y multiplicamos la base original por esta matriz.

$C · U = \pmatrix{0 && 5 \\ 3 && 0} · \begin{pmatrix}2283 & -118\\1838 & -95\end{pmatrix} = \begin{pmatrix}9190 & -475\\6849 & -354\end{pmatrix}$

El resultado es otra base que genera el mismo retículo.

Cálculos con wxMaxima:

 

 ¿Qué utilidad puede tener generar otra base de esta manera? Esto lo trataré en otra entrada de esta serie sobre retículos.

Retículos sobre espacios euclídeos $\mathbb{R}^n$

 Un retículo (lattice) sobre un espacio euclídeo $\mathbb{R}^n$ es un subgrupo discreto de $\mathbb{R}^n$.

Dicho de otra manera, un retículo es un subconjunto no vacío de vectores de $\mathbb{R}^n$ que cumplen:

• Conjunto discreto. Intuitivamente podemos decir que puede hallarse una distancia mínima que cumplen TODOS los pares de vectores (no hay continuidad).
• Contiene el elemento neutro (el vector $\vec{0}$).
• Cerrado respecto a la suma. Es decir, si dos vectores ($\vec{u}$ y $\vec{v}$) pertenecen al retículo, entonces el resultado de su suma ($\vec{u} + \vec{v}$) también debe pertenecer al retículo.
• Cerrado respecto al opuesto. Es decir, si un vector ($\vec{u}$) pertenece al retículo, entonces su opuesto ($-\vec{u}$) también debe pertenecer al retículo.

Por ejemplo, sobre $\mathbb{R}^2$, los vectores del tipo (2·m, 0) con m entero (vectores con final en el eje X con coordenada x par) forman un retículo.

Representación de algunos vectores del primer retículo

Otro ejemplo sobre $\mathbb{R}^2$ son los vectores de la forma (5·a, 3·b) con a y b enteros.

Representación de algunos vectores del segundo retículo

Estas representaciones, aún siendo parciales, pueden llegar a ser bastante densas así que no representaremos los vectores completos sino únicamente el punto final al que apuntan. Si hacemos esto se observa que se forma una especie de red/malla/retículo.

Puntos finales de los vectores del primer retículo

Puntos finales de los vectores del segundo retículo

 Dichas mallas forman "trozos".

Los trozos que se forman en el primer retículo son segmentos de una recta (eje X)

 

Los "trozos" que se forman en el segundo retículo son rectángulos.

Si los "trozos" llenan todo el espacio decimos que el retículo es completo (otros nombres: de rango completo y de dimensión completa).

Sobre $\mathbb{R}^2$ el primer retículo no es completo porque no cubre todo el plano, pero el segundo retículo sí.