Teoria dos Números - Segurança na Internet (Em Espanhol)

Vista previa del material en texto

1
Teoría de los números
Seguridad en Internet
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Índice
ƒ Aritmética Modular: 
ƒ Operador Módulo. 
ƒ Congruencia, Clases de Equivalencia.
ƒ Algoritmo de Euclides: cálculo de mcd(a,b).
ƒ Cálculo de Inversa aplicando aritmética modular: 
ƒ Condición de existencia de inversa.
ƒ Función de Euler: nº de residuos de un número.
ƒ Función de Euclides: cálculo de inversa conociendo F. Euler.
ƒ Algoritmo extendido de Euclides: cálculo de inversa sin conocer F. 
Euler. 
ƒ Teorema de Resto Chino: operar con números grandes.
ƒ Exponenciación y logaritmos discretos.
ƒ Factorización y números primos.
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Aritmética modular
ƒ Operador módulo
ƒ Congruencia
ƒ Algoritmo de Euclides
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Operador módulo
ƒ Resto:
ƒ Dados dos enteros m y n, donde n > 0. 
ƒ Resto R de dividir m entre n es el menor entero no negativo que 
difiere de m y un múltiplo de n. R=m-kn
ƒ Resto = m mod n (mod significa módulo)
ƒ Operaciones:
ƒ Con la suma y producto se puede aplicar la operación ordinaria y 
después aplicar mod n al resultado
ƒ Suma: a+b mod n = (a+b) mod n = (a mod n + b mod n) mod n
ƒ Producto: a*b mod n = (a*b) mod n = (a mod n * b mod n) mod n 
ƒ Con la exponenciación el exponente no es mod n
ƒ ab mod n = (ab) mod n = (a mod n) b mod n
ƒ La aritmética modular facilita los cálculos en aplicaciones de cifrado 
ya que se pueden operar con números grandes con resultados 
intermedios de las operaciones limitados (mod n) 
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Congruencia
ƒ Dos números a y b son congruentes módulo n cuando difieren un múltiplo de 
n: a, b, n ∈ N; a ≡ b mod n si a = b + kn; k ∈ Z
ƒ a mod n = r ⇒ a ≡ r mod n. Lo contrario no es cierto. 
ƒ Dos números congruentes mod n tienen el mismo residuo (0..n-1). 
ƒ Ejemplos: -7≡ 3 mod 10 y -7≡ 13 mod 10. 
ƒ Tanto -7 como 3 y 13 tienen R = 3.
0
K=0
10
K=1-10K=-1 133-7
R R R
ƒ Un número n induce n clases de equivalencia: nº congruentes con 0, 1...n-1 mod n
ƒ Ejem: para n=3 hay clases de 0 (0, 3, 6…) de 1 (1, 4, 7…) y de 2 (2,5,8… )
ƒ Operaciones suma y producto en el conjunto de clases de equivalencia:
ƒ a + b ≡ c mod n ⇔ a + b = c + kn k ∈ Z
ƒ a * b ≡ c mod n ⇔ a * b = c + kn k ∈ Z
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Algoritmo de Euclides (I)
ƒ Permite calcular el máximo común divisor (mcd) m de dos números a
y n.
ƒ Utilizaremos n|a para indicar que n divide a a, es decir a es múltiplo 
de n.
ƒ Se aplica la propiedad: 
m|a ∧ m|n ⇒ m|(a-kn) con k ∈ Z ⇒ m|(a mod n)
Donde m es un divisor común
ƒ Si llamamos c a a mod n podemos aplicar la propiedad de nuevo: 
m|n ∧ m|c ⇒ m|(n mod c)
ƒ Aplicando sucesivamente la propiedad, m divide a todos los restos.
ƒ Paramos cuando obtengamos el valor de resto 0.
ƒ El mcd entre a y n es el penúltimo valor obtenido. 
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Algoritmo de Euclides (II)
ƒ Invariante: mi+1=mi-1mod mi. Valores iniciales: 
m0=a; m1=n 
int mcd(int a, int n)
{
int i=1; m[0]=a; m[1]=n;
while(m[i]!=0) {
m[i+1]=m[i-1]%m[i];
i++;}
return(m[i-1]);}
Ejemplos:
•mcd(55,22) = mcd(22,55mod22)=
mcd(22,11)=mcd(11, 22mod11)=mcd(11,0)=11
• mcd(18,12) = mcd(12,18mod12)=
mcd(12,6)=mcd(6, 12mod6)=mcd(6,0)=6
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Cálculo de inversas en aritmética modular
ƒ La aritmética modular permite, al contrario que la 
aritmética entera convencional, calcular el inverso 
multiplicativo:
ƒ Dado un entero a en el rango (0, n-1)
ƒ Es posible encontrar un entero x en el rango (0, n-1) que 
cumpla:
a*x mod n = 1
ƒ Analizaremos el problema en los siguientes 
apartados:
ƒ Primero veremos la condición de existencia de inversa
ƒ Calculo de inversa mediante la función de Euler
ƒ Algoritmo extendidos de Euclides para calculo de inversa
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Condición de existencia de inversa
ƒ Elemento simétrico del producto: inversa en un conjunto finito.
ƒ Lema:
Dados a, n ∈ N; mcd(a,n) = 1 ⇒ a*i ≠ a*j (mod n) ∀ i ≠ j 0 < i, j < n
ƒ Conclusión: si a*i ≠ a*j (mod n) ∀ i ≠ j; si multiplicamos a (mod n) por 
todos los elementos del grupo finito modulo n (0,1,2…n-1), obtenemos una 
permutación de los elementos del grupo (excepto 0), por lo que debe existir 
un elemento (inversa) que al multiplicarlo por a nos de 1. 
ƒ Teorema: Si mcd(a,n) = 1, a tiene inversa módulo n.
Ejemplo: a=9, n=7. 
mcd(9,7) = mcd(7,2)=mcd(2,1)=mcd(1,0)=1 existe inversa.
9*1 mod 7 = 2 9*2 mod 7 = 4 9*3 mod 7 = 6 
9*4 mod 7 = 1 9*5 mod 7 = 3 9*6 mod 7 = 5
La inversa de 9 es 4. 
ƒ Corolario: si n es primo, el grupo finito que genera (0..n-1) tiene 
estructura de Cuerpo. Es decir, todos los elementos (excepto el 0) tienen 
inversa para el producto. (Cuerpos o Campos de Galois GFn)
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Función de Euler
ƒ Conjunto reducido de residuos módulo n es el conjunto 
de números primos relativos con n (todos los números 
que tienen inversa mod n: mcd(a,n)=1). 
ƒ Ejemplos: 
ƒ Residuos de 10 (no primo) son {1, 3, 7, 9}.
ƒ Residuos de 7 (primo) son {1,2,3,4,5,6}
ƒ El cardinal del conjunto de residuos viene dado:
Donde pi son los factores primos de n y ei su multiplicidad
ƒ Φ(n) es la función de Euler sobre n
ƒ Ejemplos: Φ(10)=(2-1)(5-1)=4; Φ(7)=(7-1)=6
ƒ Si n es producto de dos números primos n=p*q 
entonces: Φ(n)=(p-1)(q-1)
)1()(
1
1 −=Φ ∏
=
−
i
n
i
e
i ppn i
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Teoremas de Euler y Fermat
ƒ Teorema de Euler:
si mcd(a,n)=1 ⇒ aΦ(n)≡1(mod n) ó aΦ(n) mod n=1
ƒ Teorema de Fermat: 
Aplicando el teorema anterior, si p es primo 
Φ(p)=p-1; ap-1≡1(mod p) ó ap-1mod p = 1 
ƒ Corolario de T. Euler: 
Dados dos primos p y q 
Un entero n = pq, y m con 0 < m < n 
Se cumple: mkΦ(n)+1 = m k(p-1)(q-1)+1 ≡ m mod n
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Cálculo de inversa aplicando Euler
ƒ Podemos emplear el teorema de Euler para el cálculo de 
inversa mod n resolviendo la siguiente ecuación:
aΦ(n) mod n = 1 
aaΦ(n)-1 mod n=1 
Llamemos x a la inversa = a-1 mod n 
x = aΦ(n)-1 mod n
ƒ Si n es primo Φ(n)=n-1 y queda:
x = an-2 mod n
ƒ Ejemplo: n = 7 y a = 11 (primo)
ƒ La inversa de 11 será x = 117-2 mod 7= 115 mod 7 = 2
ƒ Comprobación: 2*11 mod 7 = 1
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Algoritmo extendido de Euclides (I)
ƒ Utilizado para calcular inversas cuando 
desconocemos Φ(n).
ƒ Si a y n son relativamente primos ∃ u, v / n*u +
a*v = 1 ó a*v = 1 mod n
Aclaración: mcd(a,n)=1; v*a=1 mod n; v*a = 1 + kn; 
v*a+(-k)n=1; u=-k
ƒ Aplicamos algoritmo de Euclides para resolver la 
ecuación mcd(a,n)=1
ƒ Cuando encontremos mcd, el valor de v es la 
inversa de a (inversa única). 
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Algoritmo extendido de Euclides (II)
Algoritmo:
ƒ Invariante: mi=nui+avi. Valores iniciales: m0=n, m1=a; v0=0, 
v1=1; u0=1, u1=0; 
ƒ Cuando mi=0, mi-1=mcd(a,n)=1 y vi-1 es entonces la inversa de 
a.
int inversa(int a, int n) {
int i=1; int cociente; 
m[0]=n; m[1]=a;
u[0]=1; u[1]=0; v[0]=0; v[1]=1;
while(m[i]!=0) {
cociente=m[i-1]/m[i]; 
m[i+1]=m[i-1]%m[i]; // mcd
u[i+1]=u[i-1]-cociente*u[i];
v[i+1]=v[i-1]-cociente*v[i];i++;}
return(v[i-1]%n);}
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Ejemplo
ƒ Inversa de 797 mod
1047
ƒ Ecuación de la última 
línea:
1047*373 + 797*(-490) 
= 1
ƒ Por lo tanto:
797-1 = -490 mod 1047 = 
557 
- - 0 - -
6 7 1 -490 373
5 3 125 67 -51
4 5 15 -21 16
3 3 47 4 -3
2 1 250 -1 1
1 797a 1 0
0 1047n 0 1
i cociente mi vi ui
mi = vi*a + ui * n
0 1047-1047 -490
557
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Teorema del resto chino
ƒ Este teorema básicamente dice que es posible reconstruir un entero 
en un cierto rango a partir de los residuos de una pareja de factores 
del entero relativamente primos.
ƒ De esta forma se obtiene una representación distinta del número en 
forma de números más cortos.
ƒ Aporta una forma sencilla de manipular número módulo M muy largos 
(M > 150 dígitos) en forma de tuplas de números menores.
ƒ Ejemplo: dado el número 10, podemos reconstruir cualquier elemento 
de Z10(0..9) a partir de los residuos de 2 y 5 (factores de 10 
relativamente primos dado que mcd(2,5) = 1).
ƒ 1 mod 2 = 1; 1 mod 5 = 1; 2 mod 2 = 0, 2 mod 5 = 2; 3 mod 2 = 1, 3 
mod 5 = 3…
ƒ 1 → (1,1) 2 → (0,2)
ƒ 3 → (1,3) 4 → (0,4)
ƒ 5 → (1,0) 6 → (0,1)
ƒ 7 → (1,2) 8 → (0,3)
ƒ 9 → (1,4) 
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Formalización
Si mi son parejas de números relativamente primos: 
mcd(mi,mj) = 1 para 1≤i,j≤k e i≠ j 
Podemos representar cualquier entero en ZM por una k-tupla en Zmi, usando la 
siguiente correspondencia:
A↔(a1, a2, …, ak)
Donde:
A ∈ZM (0 ≤ A < M); ai ∈Zmi (0 ≤ ai < mi) y ai=A mod Zmi para 1 ≤ i ≤ k
Propiedades:
ƒ La relación entre A y (a1, a2, …, ak) es uno a uno en ambos sentidos.
ƒ La transformación es por lo tanto única.
ƒ Operaciones implementadas en los elementos de ZM son equivalentes a realizarlas 
sobre cada elemento de la k-tupla:
ƒ Si A↔(a1, a2, …, ak) y B↔(b1, b2, …, bk). Representa ⊗ el operador +, - ó *.
ƒ (A ⊗ B) mod M ↔ ((a1 ⊗ b1) mod m1, (a2 ⊗ b2) mod m2,…, (ak ⊗
bk) mod mk) 
∏
=
=
k
i
imM
1
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Cálculos
ƒ A ⇒ (a1, a2, …, ak)
ƒ ai = A mod mi ∀ 1 ≤ i ≤ k
ƒ A ⇐ (a1, a2, …, ak)
ƒ Hacemos Mi=M/mi para 1 ≤ i ≤ k, es decir, Mi=m1*m2*…*mi-
1*mi+1*…*mk
ƒ Así se cumple que Mi ≡ 0 (mod mj) ∀ j ≠ i 
ƒ Hacemos ci = Mi * (Ii mod mi) para 1 ≤ i ≤ k, donde Ii es el inverso de 
Mi
ƒ Por definición Mi es relativamente primo de mi y por lo tanto tiene un 
único inverso multiplicativo mod mi. Entonces ci es único. mcd(Mi, 
mi)=1
ƒ Podemos calcular: 
ƒ Para comprobar que A es correcto podemos calcular ai = A mod mi ∀
1 ≤ i ≤ k
ƒ Note que cj ≡ Mj ≡ 0 (mod mi) si j ≠ i y que ci ≡ 1 (mod mi) 
MmiIMaMmicaA
k
i
iii
k
i
ii mod)mod(mod)mod(
11
⎟⎠
⎞⎜⎝
⎛⎯→⎯⎟⎠
⎞⎜⎝
⎛≡ ∑∑
==
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Ejemplo de aplicación
ƒ Representar: A=973 mod 1813, como par de números mod 37 y 49
ƒ Tomando los residuos módulo 37 y 49 la representación de 973 es (11, 42):
ƒ 973 mod 37 = 11
ƒ 973 mod 49 = 42
ƒ Hacemos m1=37, m2=49, M = 1813
ƒ Calculamos: M1= 49, M2=37. 
ƒ Usando el algoritmo extendido de Euclides calculamos inversas de M1 y M2 
resultando respectivamente: I1 = 34 mod 37 e I2 = 4 mod 49
ƒ Operaciones:
ƒ Suma: 678 + 973
ƒ Calculamos (678 mod 37, 678 mod 49) = (12, 41)
ƒ Sumamos: (12 + 11 mod 37, 41 + 42mod 49) = (23, 34)
ƒ Verificación, vemos si coinciden:
ƒ (23, 34) ↔ a1M1I1+ a2M2I2mod M=[(23)(49)(34)+(34)(37)(4)] mod 1813=1651 
ƒ (973 + 678) mod 1813 = 1651
ƒ Multiplicación: 73*1651(mod 1813); 73 equivale a (36,24)
ƒ Por lo tanto: (23 *36 mod 37, 34*24 mod 49)=(14, 32) 
ƒ Verificación, vemos si coinciden:
ƒ (14, 32) ↔ [(14)(49)(34) + (32)(37)(4)] mod 1813 = 865 
ƒ 1651*73 mod 1813 = 865 
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Exponenciación. Logaritmos discretos.
ƒ Campo de aplicación de la exponenciación
ƒ Algoritmo de exponenciación rápida
ƒ Problema de los logaritmos discretos
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Campo de aplicación de la 
exponenciación
ƒ Muchos algoritmos de clave pública utilizan exponenciación
dentro de grupos finitos (aritmética modular) para codificar 
mensajes.
ƒ Bases y exponentes son números muy grandes (miles de 
bits).
ƒ Realizar exponenciaciones mediante multiplicación de la base 
por si misma tantas veces como indique el exponente es 
inviable para números grandes.
ƒ Es necesario buscar algoritmos de exponenciación eficientes.
ƒ El logaritmo discreto es operación inversa y en ella se 
basa la resistencia de los algoritmos de cifrado.
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Algoritmo de exponenciación rápida
ƒ Dados a, b ∈ N. Queremos calcular ab. 
ƒ Representación binaria de b: b= 20b0+ 21b1+ 22b2+ 23b3+ 
24b4+….+ 2nbn
ƒ Expresamos ab como:
bi sólo puede valer 0 ó 1, sólo se consideran los términos en 
los que vale 1
ƒ También debemos considerar que: por lo 
que partiendo de a podemos ir calculando sucesivamente 
los distintos valores elevando el anterior al cuadrado.
∏
=
+++ ==
n
i
bbnbbb i
in
aaa
0
22...22 1
1
0
0
222 )(
1−= ii aa
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Algoritmo de exponenciación rápida
int expon_rapida(int a, int b)
{ 
int x, y, resultado; 
y=b; // va obteniendo el bit menos significativo de b
x=a; // valores sucesivos de 
resultado = 1;
while(y >0) {
if (y%2==1) // bit menos significativo vale 1
resultado= resultado * x; // ¿mod n?
x=x*x; // ¿mod n?
y=y/2; //desplaza a la derecha para buscar siguiente bit
}
return(resultado)}
i
a2
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Problema de los logaritmos discretos
ƒ Dados dos números a y b y el módulo n. Se define logaritmo 
discreto de a en base b de módulo n:
c=logb(a)(mod n) ⇔ a ≡ bc (mod n)
ƒ La resistencia de los algoritmos basados en la 
exponenciación se basa en que no existen actualmente 
algoritmos de logaritmos eficaces para realizar estos cálculos 
en tiempo razonable.
ƒ Existe una relación entre este problema y el de la 
factorización: si se calcula un logaritmo se puede factorizar 
fácilmente (el recíproco no se ha demostrado).
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
ƒ Factorización.
ƒ Números primos
ƒ Método de Lehmann
ƒ Método de Rabin-Miller
ƒ Generación de números primos.
ƒ Primos fuertes
Factorización
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Problema de factorización
ƒ Para aumentar la dificultad en el cálculo de logaritmos discretos los 
algoritmos utilizan operaciones de exponenciación en grupos finitos.
ƒ Propiedades del valor del módulo n que define el grupo finito:
ƒ Valor muy grande.
ƒ Pocos factores: normalmente dos.
ƒ Se debe hacer público n y sus factores se deben mantener secretos.
ƒ Problema inverso. Factorización: 
ƒ Dado n descomponer producto de factores.
ƒ Para que la solución sea única los factores deben ser primos.
ƒ Cálculo de n: 
ƒ Obtener dos números primos grandes (p y q).
ƒ n=p*q (p y q son los factores secretos)
ƒ Son necesarios mecanismos de obtención de números primos grandes.
ƒ No existen algoritmos eficientes para el cálculo de factores de n si se 
eligen estos adecuadamente.
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
ƒ Cálculo de primos grandes: para obtenerp y q.
ƒ Se puede aplicar un algoritmo de factorización: inviable para números 
grandes.
ƒ Existen algoritmos probabilísticos rápidos que permiten predecir con un 
alto grado de certeza si un número grande es primo o compuesto.
ƒ ¿Existen suficientes números primos grandes para no repetirlos?
El conjunto es suficientemente grande para no repetirlos, se estima 
que existen 10151 primos de hasta 512 bits.
ƒ ¿Se podría calcular previamente los 10151 primos y almacenarlos para 
utilizarlos en un algoritmo de factorización rápido?
La unidad de almacenamiento sería inviable, tendría un volumen de 
10130 m3 y masa de 10135 kg.
ƒ Métodos más comunes que permiten saber si un número es primo:
ƒ Método de Lehmann.
ƒ Método de Rabin-Miller.
Números primos
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Método de Lehmann
ƒ Pasos:
c Elige un número aleatorio a < p
d Calcula b = a(p-1)/2(mod p)
e Si b ≠ 1 (mod p) y b ≠ -1 (mod p), p no es primo
f Si b ≡ 1 (mod p) ó b ≡ -1 (mod p). La probabilidad de que p sea 
primo es ≥ 50%.
ƒ Nivel de confianza:
Repitiendo el algoritmo n veces, la probabilidad de que p 
supere el test y no sea primo será 1/ 2n.
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Método de Rabin-Miller
ƒ Sea p el número a comprobar
ƒ Se calcula b: número de veces que 2 divide a (p-1)
ƒ Se calcula m que cumple p = 1 + 2b * m 
ƒ Pasos:
c Elegir un número aleatorio a < p
d Sea j = 0 y z = am(mod p)
e Si z = 1 ó z = p-1, p pasa el test y puede ser primo 
f Si j > 0 y z = 1, p no es primo 
g Sea j = j+1. Si j = b y z ≠ p-1, p no es primo
h Si j < b y z ≠ p-1, z = z2(mod p). Volver al paso 4
i Si j < b y z = p-1, p pasa el test y puede ser primo (75%)
j p no es primo
ƒ Nivel de confianza: 
La probabilidad de que un número compuesto pase este 
algoritmo para un valor de a, es del 25%. 
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Generación de números primos
ƒ El algoritmo generalmente empleado en la práctica es:
c Generar un número aleatorio p de n bits.
d Poner a 1 los bits:
ƒ De mayor peso para hacer que sea de n bits.
ƒ De menor peso para hacerlo impar (los primos son impares).
e Intentar dividir p por una tabla de primos precalculados 
(normalmente los primeros 2000 primos). El 99.8 % de los números 
impares no primos es divisible por algún primo menor de 2000. 
f Ejecutar el test de Rabin-Miller como mínimo 5 veces. 
Tema 4. Teoría de los Números
Seguridad en Internet B. Alarcos, E. de la Hoz
Primos fuertes
ƒ Aunque p y q sean primos grandes, hay casos en los que es 
sencillo factorizar n = p*q.
ƒ Los primos fuertes cumplen condiciones que hacen difícil 
factorizar n:
ƒ mcd((p-1),(q-1)) debe ser pequeño.
ƒ p-1 y q-1 deben tener algún factor primo grande p’ y q’.
ƒ Tanto p’-1 como q’-1 deben tener factores primos grandes.
ƒ Tanto p’+1 como q’+1 deben tener factores primos grandes.
ƒ Las dos primeras condiciones se cumplen si tanto (p-1)/2 como (q-
1)/2 son primos.