¡¡Códigos en todas partes!!

Edgar Martínez Moro (IMUVa)

Material para la exposición de la charla dedicada al Bachillerato de Excelencia

Transparencias en http://www.singacom.uva.es/~edgar/bachilleratoexcelencia/transparencias.pdf

Sage Cell Server: http://sagecell.sagemath.org/

Cálculo del ISBN

libro=vector([0,3,8,7,2,3,7,0,7])

pesos=Matrix([[1],[2],[3],[4],[5],[6],[7],[8],[9]])

a=libro*pesos; a

 $\newcommand{\Bold}[1]{\mathbf{#1}}\left(198\right)$

a[0] % 11

 $\newcommand{\Bold}[1]{\mathbf{#1}}0$

Cálculo de la letra del NIF

999427 % 23

 $\newcommand{\Bold}[1]{\mathbf{#1}}8$

¿Por qué detecta un error?

x=1 while x<=7: for y in [1,2,3,4,5,6,7,8,9]: print (y*10^x),"-",(y*10^x % 23), "|", x=x+1

10 - 10 | 20 - 20 | 30 - 7 | 40 - 17 | 50 - 4 | 60 - 14 | 70 - 1 |
80 - 11 | 90 - 21 | 100 - 8 | 200 - 16 | 300 - 1 | 400 - 9 | 500 -
17 | 600 - 2 | 700 - 10 | 800 - 18 | 900 - 3 | 1000 - 11 | 2000 - 22
| 3000 - 10 | 4000 - 21 | 5000 - 9 | 6000 - 20 | 7000 - 8 | 8000 -
19 | 9000 - 7 | 10000 - 18 | 20000 - 13 | 30000 - 8 | 40000 - 3 |
50000 - 21 | 60000 - 16 | 70000 - 11 | 80000 - 6 | 90000 - 1 |
100000 - 19 | 200000 - 15 | 300000 - 11 | 400000 - 7 | 500000 - 3 |
600000 - 22 | 700000 - 18 | 800000 - 14 | 900000 - 10 | 1000000 - 6
| 2000000 - 12 | 3000000 - 18 | 4000000 - 1 | 5000000 - 7 | 6000000
- 13 | 7000000 - 19 | 8000000 - 2 | 9000000 - 8 | 10000000 - 14 |
20000000 - 5 | 30000000 - 19 | 40000000 - 10 | 50000000 - 1 |
60000000 - 15 | 70000000 - 6 | 80000000 - 20 | 90000000 - 11 |

Aritmética modular: ¿Qué es más rápido, saber el cociente o el resto? ¿Por qué?

time 21^190000000 // 23

Traceback (click to the left of this block for traceback)
...
__SAGE__

time 21^190000000 & 23

 $\newcommand{\Bold}[1]{\mathbf{#1}}1$ 

Time: CPU 10.50 s, Wall: 10.58 s

Código de Hamming

C = HammingCode(3,GF(2)) C

 $\newcommand{\Bold}[1]{\mathbf{#1}}\verb|Linear|\phantom{\verb!x!}\verb|code|\phantom{\verb!x!}\verb|of|\phantom{\verb!x!}\verb|length|\phantom{\verb!x!}\verb|7,|\phantom{\verb!x!}\verb|dimension|\phantom{\verb!x!}\verb|4|\phantom{\verb!x!}\verb|over|\phantom{\verb!x!}\verb|Finite|\phantom{\verb!x!}\verb|Field|\phantom{\verb!x!}\verb|of|\phantom{\verb!x!}\verb|size|\phantom{\verb!x!}\verb|2|$

C.minimum_distance()

 $\newcommand{\Bold}[1]{\mathbf{#1}}3$

G=C.gen_mat() G

 $\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrr} 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{array}\right)$

C.check_mat()

 $\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrr} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{array}\right)$

w = C.weight_distribution(); w

 $\newcommand{\Bold}[1]{\mathbf{#1}}\left[1, 0, 0, 7, 7, 0, 0, 1\right]$

C.list()

 $\newcommand{\Bold}[1]{\mathbf{#1}}\left[\left(0,\,0,\,0,\,0,\,0,\,0,\,0\right), \left(1,\,0,\,0,\,0,\,0,\,1,\,1\right), \left(0,\,1,\,0,\,0,\,1,\,0,\,1\right), \left(1,\,1,\,0,\,0,\,1,\,1,\,0\right), \left(0,\,0,\,1,\,0,\,1,\,1,\,0\right), \left(1,\,0,\,1,\,0,\,1,\,0,\,1\right), \left(0,\,1,\,1,\,0,\,0,\,1,\,1\right), \left(1,\,1,\,1,\,0,\,0,\,0,\,0\right), \left(0,\,0,\,0,\,1,\,1,\,1,\,1\right), \left(1,\,0,\,0,\,1,\,1,\,0,\,0\right), \left(0,\,1,\,0,\,1,\,0,\,1,\,0\right), \left(1,\,1,\,0,\,1,\,0,\,0,\,1\right), \left(0,\,0,\,1,\,1,\,0,\,0,\,1\right), \left(1,\,0,\,1,\,1,\,0,\,1,\,0\right), \left(0,\,1,\,1,\,1,\,1,\,0,\,0\right), \left(1,\,1,\,1,\,1,\,1,\,1,\,1\right)\right]$

Descodificar

recibido = [0,1,1,1,1,1,0]

C.decode(recibido)

 $\newcommand{\Bold}[1]{\mathbf{#1}}\left(0,\,1,\,1,\,1,\,1,\,0,\,0\right)$

Más detalladamente

recibido=matrix([0,1,1,1,1,1,0])

C.check_mat()*recibido.transpose()

 $\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{r} 0 \\ 1 \\ 1 \end{array}\right)$

McEliece

Inicialización

k=4; n=7; # Matriz S S=matrix(GF(2),k,[random()<.5 for _ in range(k^2)]); while (rank(S)<k): S[floor(k*random()),floor(k*random())] +=1; print str(S) print " " # Matriz P rng=range(n);P=matrix(GF(2),n); for i in range(n): p=floor(len(rng)*random()); P[i,rng[p]]=1;rng=rng[:p]+rng[p+1:]; print str(P)

[0 1 1 0]
[1 1 1 0]
[0 1 0 1]
[1 1 0 0]
      
[1 0 0 0 0 0 0]
[0 0 0 0 1 0 0]
[0 0 1 0 0 0 0]
[0 0 0 1 0 0 0]
[0 1 0 0 0 0 0]
[0 0 0 0 0 0 1]
[0 0 0 0 0 1 0]

Clave pública (Pub)

#La llave publica es (Pub,1) Pub=S*G*P; print "Clave publica es: (Pub,1)"; print str(Pub) + " , " + "1";

Clave publica es: (Pub,1)
[0 0 1 0 1 1 1]
[1 0 1 0 1 0 0]
[0 0 0 1 1 0 1]
[1 1 0 0 1 0 1] , 1

Mensaje a enviar

m=vector(GF(2),[1,0,0,1]); m

 $\newcommand{\Bold}[1]{\mathbf{#1}}\left(1,\,0,\,0,\,1\right)$

Añadimos aleatoriamente un error

c_prima=m*Pub; print "m*G': " + str(c_prima); e=vector(GF(2),n);#e=zero vector; for trial in range(1): j=randint(0,n-1); e[j] +=1; print "e : " + str(e); e_prima=e*P; print "e': " + str(e*P); y_prima=c_prima+e_prima; print "y': " + str(y_prima);

m*G':  (1, 1, 1, 0, 0, 1, 0)
e :    (0, 0, 1, 0, 0, 0, 0)
e':    (0, 0, 1, 0, 0, 0, 0)
y':    (1, 1, 0, 0, 0, 1, 0)

Descifrar (decodificar)

y=y_prima*(P^(-1)); print "y: " + str(y); # mS=C.decode(y) print "mS: " + str(mS); # #Quitamos de mS las coordenadas de paridad; m_final=vector(GF(2),k); for i in range(k): m_final[i]=mS[i]; i=i+1; print "m_final: " + str(m_final); # final=m_final*(S^(-1)); print "Final: " + str(final);

y:       (1, 0, 0, 0, 1, 0, 1)
mS:      (1, 0, 1, 0, 1, 0, 1)
m_final: (1, 0, 1, 0)
Final:   (1, 0, 0, 1)

Para sistema Niederreiter ver

http://tlapixqui.izt.uam.mx/novenocol/Mexico2011/ejemplo.html.html