Gram-Schmidt sobre GF$(2)$

Question

Estoy leyendo el papel de La Steganographic Sistema de Archivos por Ross Anderson, Roger Needham, y Adi Shamir. En la página 4, párrafo 2, los autores escriben:

Por último, utilizamos las bacterias Gram-Schmidt método para orthonormalise todos los vectores de $i$ en adelante restando de la candidata $K_i$ todos sus componentes a lo largo de más tarde $K_j$ que el usuario conoce por el encadenamiento de los propiedad de la $p_j$'s.

Esto simplemente significa que los autores utilizan el algoritmo de Gram-Schmidt con el campo de tierra GF$(2)$, y a partir del contexto, cada uno de los originales de los vectores el algoritmo se aplica a norma ha $1$. Sin embargo, en este caso, el algoritmo produce una base que no es necesariamente ortonormales, ni siquiera ortogonal. Estoy en lo cierto? Es este un grave defecto?

Answer 1

La respuesta a continuación fue publicado antes de la pieza de información acerca de todos los participantes vectores se marcará con bits aleatorios para asegurarse de que sus pesos son impares.

---

En mi humilde opinión, un problema más grave con el uso de Gram-Schmidt sobre $GF(2)$ es que de Gram-Schmidt puede llamar a la división por cero!!! Esto es debido a que en la proyección de la fórmula $$ y\mapsto y-\frac{(y,x)}{(x,x)}x $$ el denominador $(x,x)$ se desvanece al $x$ es ortogonal a sí mismo.

Por ejemplo, considere el siguiente subespacio de $GF(2)^3$: $$ V=\{(a,b,c)\en GF(2)^3\mediados de los a+b+c=0\}. $$ Enseguida se dará cuenta de que cada vector de $V$ es ortogonal a sí mismo. Diviértete tratando de Gram-Schmidt orthogonalize por ejemplo, la base $v_1=(1,1,0)$, $v_2=(1,0,1)$ $V$ : -)