cap. 2: teor ia de numeros (ii)€¦ · polinomios sobre cuerpos divisi on de polinomios existencia...
TRANSCRIPT
![Page 1: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/1.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Curso de posgrado MATEMATICA DISCRETA
T. N. Hibbard - J. F. Yazlle
Facultad de Ciencias Exactas
Universidad Nacional de Salta
Cap. 2: TEORIA DE NUMEROS (II)
![Page 2: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/2.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Cuerpos
Definicion
Un cuerpo es (K ,+,×) tales que:
(K ,+) es grupo conmutativo (elemento neutro 0).
(K − {0},×) es grupo conmutativo (elemento neutro 1).
Se cumple la ley distributiva de + respecto de ×:∀a, b, c ∈ K , a× (b + c) = a× b + a× c .
Si p es primo, Zp es un cuerpo con la suma y el productomodulo p.
![Page 3: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/3.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Cuerpos
Definicion
Un cuerpo es (K ,+,×) tales que:
(K ,+) es grupo conmutativo (elemento neutro 0).
(K − {0},×) es grupo conmutativo (elemento neutro 1).
Se cumple la ley distributiva de + respecto de ×:∀a, b, c ∈ K , a× (b + c) = a× b + a× c .
Si p es primo, Zp es un cuerpo con la suma y el productomodulo p.
![Page 4: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/4.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Cuerpos
Definicion
Un cuerpo es (K ,+,×) tales que:
(K ,+) es grupo conmutativo (elemento neutro 0).
(K − {0},×) es grupo conmutativo (elemento neutro 1).
Se cumple la ley distributiva de + respecto de ×:∀a, b, c ∈ K , a× (b + c) = a× b + a× c .
Si p es primo, Zp es un cuerpo con la suma y el productomodulo p.
![Page 5: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/5.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Cuerpos
Definicion
Un cuerpo es (K ,+,×) tales que:
(K ,+) es grupo conmutativo (elemento neutro 0).
(K − {0},×) es grupo conmutativo (elemento neutro 1).
Se cumple la ley distributiva de + respecto de ×:∀a, b, c ∈ K , a× (b + c) = a× b + a× c .
Si p es primo, Zp es un cuerpo con la suma y el productomodulo p.
![Page 6: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/6.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Cuerpos
Definicion
Un cuerpo es (K ,+,×) tales que:
(K ,+) es grupo conmutativo (elemento neutro 0).
(K − {0},×) es grupo conmutativo (elemento neutro 1).
Se cumple la ley distributiva de + respecto de ×:∀a, b, c ∈ K , a× (b + c) = a× b + a× c .
Si p es primo, Zp es un cuerpo con la suma y el productomodulo p.
![Page 7: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/7.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Polinomios sobre cuerpos
Definicion
Polinomio p sobre un cuerpo K :
sucesion infinita p0, p1, . . . ∈ K , tal que∃n ≥ 0 : ∀j > n, pj = 0.
Polinomio nulo: ∀j ∈ N, pj = 0.
Si p no es nulo, ∃g ∈ N : pg 6= 0 ∧ ∀j > g , pj = 0g → grado de p.
Valor de p en a ∈ K : p(a) =∑∞
j=0 pjaj =
∑gj=0 pja
j .Si p(a) = 0, a es una raız de p.
Suma de polinomios p y q: p + q con (p + q)j = pj + qj .
Producto de polinomios p y q: p × q con(p × q)j =
∑i+k=j piqk .
∀a ∈ K , (p + q)(a) = p(a) + q(a) ∧ (p × q)(a) = p(a)× q(a).
![Page 8: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/8.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Polinomios sobre cuerpos
Definicion
Polinomio p sobre un cuerpo K :sucesion infinita p0, p1, . . . ∈ K , tal que∃n ≥ 0 : ∀j > n, pj = 0.
Polinomio nulo: ∀j ∈ N, pj = 0.
Si p no es nulo, ∃g ∈ N : pg 6= 0 ∧ ∀j > g , pj = 0g → grado de p.
Valor de p en a ∈ K : p(a) =∑∞
j=0 pjaj =
∑gj=0 pja
j .Si p(a) = 0, a es una raız de p.
Suma de polinomios p y q: p + q con (p + q)j = pj + qj .
Producto de polinomios p y q: p × q con(p × q)j =
∑i+k=j piqk .
∀a ∈ K , (p + q)(a) = p(a) + q(a) ∧ (p × q)(a) = p(a)× q(a).
![Page 9: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/9.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Polinomios sobre cuerpos
Definicion
Polinomio p sobre un cuerpo K :sucesion infinita p0, p1, . . . ∈ K , tal que∃n ≥ 0 : ∀j > n, pj = 0.
Polinomio nulo: ∀j ∈ N, pj = 0.
Si p no es nulo, ∃g ∈ N : pg 6= 0 ∧ ∀j > g , pj = 0g → grado de p.
Valor de p en a ∈ K : p(a) =∑∞
j=0 pjaj =
∑gj=0 pja
j .Si p(a) = 0, a es una raız de p.
Suma de polinomios p y q: p + q con (p + q)j = pj + qj .
Producto de polinomios p y q: p × q con(p × q)j =
∑i+k=j piqk .
∀a ∈ K , (p + q)(a) = p(a) + q(a) ∧ (p × q)(a) = p(a)× q(a).
![Page 10: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/10.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Polinomios sobre cuerpos
Definicion
Polinomio p sobre un cuerpo K :sucesion infinita p0, p1, . . . ∈ K , tal que∃n ≥ 0 : ∀j > n, pj = 0.
Polinomio nulo: ∀j ∈ N, pj = 0.
Si p no es nulo, ∃g ∈ N : pg 6= 0 ∧ ∀j > g , pj = 0
g → grado de p.
Valor de p en a ∈ K : p(a) =∑∞
j=0 pjaj =
∑gj=0 pja
j .Si p(a) = 0, a es una raız de p.
Suma de polinomios p y q: p + q con (p + q)j = pj + qj .
Producto de polinomios p y q: p × q con(p × q)j =
∑i+k=j piqk .
∀a ∈ K , (p + q)(a) = p(a) + q(a) ∧ (p × q)(a) = p(a)× q(a).
![Page 11: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/11.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Polinomios sobre cuerpos
Definicion
Polinomio p sobre un cuerpo K :sucesion infinita p0, p1, . . . ∈ K , tal que∃n ≥ 0 : ∀j > n, pj = 0.
Polinomio nulo: ∀j ∈ N, pj = 0.
Si p no es nulo, ∃g ∈ N : pg 6= 0 ∧ ∀j > g , pj = 0g → grado de p.
Valor de p en a ∈ K : p(a) =∑∞
j=0 pjaj =
∑gj=0 pja
j .Si p(a) = 0, a es una raız de p.
Suma de polinomios p y q: p + q con (p + q)j = pj + qj .
Producto de polinomios p y q: p × q con(p × q)j =
∑i+k=j piqk .
∀a ∈ K , (p + q)(a) = p(a) + q(a) ∧ (p × q)(a) = p(a)× q(a).
![Page 12: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/12.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Polinomios sobre cuerpos
Definicion
Polinomio p sobre un cuerpo K :sucesion infinita p0, p1, . . . ∈ K , tal que∃n ≥ 0 : ∀j > n, pj = 0.
Polinomio nulo: ∀j ∈ N, pj = 0.
Si p no es nulo, ∃g ∈ N : pg 6= 0 ∧ ∀j > g , pj = 0g → grado de p.
Valor de p en a ∈ K : p(a) =∑∞
j=0 pjaj =
∑gj=0 pja
j .
Si p(a) = 0, a es una raız de p.
Suma de polinomios p y q: p + q con (p + q)j = pj + qj .
Producto de polinomios p y q: p × q con(p × q)j =
∑i+k=j piqk .
∀a ∈ K , (p + q)(a) = p(a) + q(a) ∧ (p × q)(a) = p(a)× q(a).
![Page 13: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/13.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Polinomios sobre cuerpos
Definicion
Polinomio p sobre un cuerpo K :sucesion infinita p0, p1, . . . ∈ K , tal que∃n ≥ 0 : ∀j > n, pj = 0.
Polinomio nulo: ∀j ∈ N, pj = 0.
Si p no es nulo, ∃g ∈ N : pg 6= 0 ∧ ∀j > g , pj = 0g → grado de p.
Valor de p en a ∈ K : p(a) =∑∞
j=0 pjaj =
∑gj=0 pja
j .Si p(a) = 0, a es una raız de p.
Suma de polinomios p y q: p + q con (p + q)j = pj + qj .
Producto de polinomios p y q: p × q con(p × q)j =
∑i+k=j piqk .
∀a ∈ K , (p + q)(a) = p(a) + q(a) ∧ (p × q)(a) = p(a)× q(a).
![Page 14: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/14.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Polinomios sobre cuerpos
Definicion
Polinomio p sobre un cuerpo K :sucesion infinita p0, p1, . . . ∈ K , tal que∃n ≥ 0 : ∀j > n, pj = 0.
Polinomio nulo: ∀j ∈ N, pj = 0.
Si p no es nulo, ∃g ∈ N : pg 6= 0 ∧ ∀j > g , pj = 0g → grado de p.
Valor de p en a ∈ K : p(a) =∑∞
j=0 pjaj =
∑gj=0 pja
j .Si p(a) = 0, a es una raız de p.
Suma de polinomios p y q: p + q con (p + q)j = pj + qj .
Producto de polinomios p y q: p × q con(p × q)j =
∑i+k=j piqk .
∀a ∈ K , (p + q)(a) = p(a) + q(a) ∧ (p × q)(a) = p(a)× q(a).
![Page 15: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/15.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Polinomios sobre cuerpos
Definicion
Polinomio p sobre un cuerpo K :sucesion infinita p0, p1, . . . ∈ K , tal que∃n ≥ 0 : ∀j > n, pj = 0.
Polinomio nulo: ∀j ∈ N, pj = 0.
Si p no es nulo, ∃g ∈ N : pg 6= 0 ∧ ∀j > g , pj = 0g → grado de p.
Valor de p en a ∈ K : p(a) =∑∞
j=0 pjaj =
∑gj=0 pja
j .Si p(a) = 0, a es una raız de p.
Suma de polinomios p y q: p + q con (p + q)j = pj + qj .
Producto de polinomios p y q: p × q con(p × q)j =
∑i+k=j piqk .
∀a ∈ K , (p + q)(a) = p(a) + q(a) ∧ (p × q)(a) = p(a)× q(a).
![Page 16: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/16.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Polinomios sobre cuerpos
Definicion
Polinomio p sobre un cuerpo K :sucesion infinita p0, p1, . . . ∈ K , tal que∃n ≥ 0 : ∀j > n, pj = 0.
Polinomio nulo: ∀j ∈ N, pj = 0.
Si p no es nulo, ∃g ∈ N : pg 6= 0 ∧ ∀j > g , pj = 0g → grado de p.
Valor de p en a ∈ K : p(a) =∑∞
j=0 pjaj =
∑gj=0 pja
j .Si p(a) = 0, a es una raız de p.
Suma de polinomios p y q: p + q con (p + q)j = pj + qj .
Producto de polinomios p y q: p × q con(p × q)j =
∑i+k=j piqk .
∀a ∈ K , (p + q)(a) = p(a) + q(a) ∧ (p × q)(a) = p(a)× q(a).
![Page 17: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/17.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Polinomios sobre cuerpos
Notacion
Para a ∈ K y n ∈ N:
El polinomio a es el polinomio p tal que p0 = a y∀j > 0, pj = 0.
El polinomio xn representa al polinomio p tal que pn = 1y ∀j 6= n, pj = 0.(x × p designa el polinomio q tal que q0 = 0 y qi+1 = pipara todo i .)
Para polinomios p, q, decimos que p < q cuando
p = 0 y q 6= 0, o bienp 6= 0 6= q y el grado de p es menor que el grado de q.
![Page 18: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/18.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Polinomios sobre cuerpos
Notacion
Para a ∈ K y n ∈ N:
El polinomio a es el polinomio p tal que p0 = a y∀j > 0, pj = 0.El polinomio xn representa al polinomio p tal que pn = 1y ∀j 6= n, pj = 0.
(x × p designa el polinomio q tal que q0 = 0 y qi+1 = pipara todo i .)
Para polinomios p, q, decimos que p < q cuando
p = 0 y q 6= 0, o bienp 6= 0 6= q y el grado de p es menor que el grado de q.
![Page 19: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/19.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Polinomios sobre cuerpos
Notacion
Para a ∈ K y n ∈ N:
El polinomio a es el polinomio p tal que p0 = a y∀j > 0, pj = 0.El polinomio xn representa al polinomio p tal que pn = 1y ∀j 6= n, pj = 0.(x × p designa el polinomio q tal que q0 = 0 y qi+1 = pipara todo i .)
Para polinomios p, q, decimos que p < q cuando
p = 0 y q 6= 0, o bienp 6= 0 6= q y el grado de p es menor que el grado de q.
![Page 20: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/20.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Polinomios sobre cuerpos
Notacion
Para a ∈ K y n ∈ N:
El polinomio a es el polinomio p tal que p0 = a y∀j > 0, pj = 0.El polinomio xn representa al polinomio p tal que pn = 1y ∀j 6= n, pj = 0.(x × p designa el polinomio q tal que q0 = 0 y qi+1 = pipara todo i .)
Para polinomios p, q, decimos que p < q cuando
p = 0 y q 6= 0, o bienp 6= 0 6= q y el grado de p es menor que el grado de q.
![Page 21: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/21.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Polinomios sobre cuerpos
Notacion
Para a ∈ K y n ∈ N:
El polinomio a es el polinomio p tal que p0 = a y∀j > 0, pj = 0.El polinomio xn representa al polinomio p tal que pn = 1y ∀j 6= n, pj = 0.(x × p designa el polinomio q tal que q0 = 0 y qi+1 = pipara todo i .)
Para polinomios p, q, decimos que p < q cuando
p = 0 y q 6= 0, o bien
p 6= 0 6= q y el grado de p es menor que el grado de q.
![Page 22: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/22.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Polinomios sobre cuerpos
Notacion
Para a ∈ K y n ∈ N:
El polinomio a es el polinomio p tal que p0 = a y∀j > 0, pj = 0.El polinomio xn representa al polinomio p tal que pn = 1y ∀j 6= n, pj = 0.(x × p designa el polinomio q tal que q0 = 0 y qi+1 = pipara todo i .)
Para polinomios p, q, decimos que p < q cuando
p = 0 y q 6= 0, o bienp 6= 0 6= q y el grado de p es menor que el grado de q.
![Page 23: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/23.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Division de polinomios
Teorema de la division para polinomios
Dados dos polinomios p, q sobre un cuerpo K con q 6= 0,existen dos polinomios c , r sobre K con r < q tal quep = c × q + r .
Algoritmo para division de polinomios
D(p, q) =. si (p < q) (0, p). sino. . si (p y q tienen el mismo grado g). . . (pg/qg , p − (pg/qg )× q). . sino. . . (c, r) := D(p, x × q). . . (c1, r1) := D(r , q). . . (x × c + c1, r1)
![Page 24: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/24.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Division de polinomios
Teorema de la division para polinomios
Dados dos polinomios p, q sobre un cuerpo K con q 6= 0,existen dos polinomios c , r sobre K con r < q tal quep = c × q + r .
Algoritmo para division de polinomios
D(p, q) =
. si (p < q) (0, p)
. sino
. . si (p y q tienen el mismo grado g)
. . . (pg/qg , p − (pg/qg )× q)
. . sino
. . . (c, r) := D(p, x × q)
. . . (c1, r1) := D(r , q)
. . . (x × c + c1, r1)
![Page 25: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/25.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Division de polinomios
Teorema de la division para polinomios
Dados dos polinomios p, q sobre un cuerpo K con q 6= 0,existen dos polinomios c , r sobre K con r < q tal quep = c × q + r .
Algoritmo para division de polinomios
D(p, q) =. si (p < q) (0, p). sino
. . si (p y q tienen el mismo grado g)
. . . (pg/qg , p − (pg/qg )× q)
. . sino
. . . (c, r) := D(p, x × q)
. . . (c1, r1) := D(r , q)
. . . (x × c + c1, r1)
![Page 26: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/26.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Division de polinomios
Teorema de la division para polinomios
Dados dos polinomios p, q sobre un cuerpo K con q 6= 0,existen dos polinomios c , r sobre K con r < q tal quep = c × q + r .
Algoritmo para division de polinomios
D(p, q) =. si (p < q) (0, p). sino. . si (p y q tienen el mismo grado g)
. . . (pg/qg , p − (pg/qg )× q)
. . sino
. . . (c, r) := D(p, x × q)
. . . (c1, r1) := D(r , q)
. . . (x × c + c1, r1)
![Page 27: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/27.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Division de polinomios
Teorema de la division para polinomios
Dados dos polinomios p, q sobre un cuerpo K con q 6= 0,existen dos polinomios c , r sobre K con r < q tal quep = c × q + r .
Algoritmo para division de polinomios
D(p, q) =. si (p < q) (0, p). sino. . si (p y q tienen el mismo grado g). . . (pg/qg , p − (pg/qg )× q). . sino
. . . (c, r) := D(p, x × q)
. . . (c1, r1) := D(r , q)
. . . (x × c + c1, r1)
![Page 28: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/28.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Division de polinomios
Teorema de la division para polinomios
Dados dos polinomios p, q sobre un cuerpo K con q 6= 0,existen dos polinomios c , r sobre K con r < q tal quep = c × q + r .
Algoritmo para division de polinomios
D(p, q) =. si (p < q) (0, p). sino. . si (p y q tienen el mismo grado g). . . (pg/qg , p − (pg/qg )× q). . sino. . . (c, r) := D(p, x × q)
. . . (c1, r1) := D(r , q)
. . . (x × c + c1, r1)
![Page 29: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/29.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Division de polinomios
Teorema de la division para polinomios
Dados dos polinomios p, q sobre un cuerpo K con q 6= 0,existen dos polinomios c , r sobre K con r < q tal quep = c × q + r .
Algoritmo para division de polinomios
D(p, q) =. si (p < q) (0, p). sino. . si (p y q tienen el mismo grado g). . . (pg/qg , p − (pg/qg )× q). . sino. . . (c, r) := D(p, x × q). . . (c1, r1) := D(r , q)
. . . (x × c + c1, r1)
![Page 30: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/30.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Division de polinomios
Teorema de la division para polinomios
Dados dos polinomios p, q sobre un cuerpo K con q 6= 0,existen dos polinomios c , r sobre K con r < q tal quep = c × q + r .
Algoritmo para division de polinomios
D(p, q) =. si (p < q) (0, p). sino. . si (p y q tienen el mismo grado g). . . (pg/qg , p − (pg/qg )× q). . sino. . . (c, r) := D(p, x × q). . . (c1, r1) := D(r , q). . . (x × c + c1, r1)
![Page 31: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/31.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Existencia de elementos primitivos
Teorema
Un polinomio de grado n sobre un cuerpo no tiene mas que nraıces en el cuerpo.
Teorema
Todo cuerpo finito tiene un elemento primitivo.
Podemos demostrarlo si logramos demostrar que
Lema
En cualquier cuerpo finito, si hay un elemento de ordenmultiplicativo m y otro de orden multiplicativo n, entonces hayun elemento de orden multiplicativo mcm(m, n).
![Page 32: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/32.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Existencia de elementos primitivos
Teorema
Un polinomio de grado n sobre un cuerpo no tiene mas que nraıces en el cuerpo.
Teorema
Todo cuerpo finito tiene un elemento primitivo.
Podemos demostrarlo si logramos demostrar que
Lema
En cualquier cuerpo finito, si hay un elemento de ordenmultiplicativo m y otro de orden multiplicativo n, entonces hayun elemento de orden multiplicativo mcm(m, n).
![Page 33: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/33.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Existencia de elementos primitivos
Teorema
Un polinomio de grado n sobre un cuerpo no tiene mas que nraıces en el cuerpo.
Teorema
Todo cuerpo finito tiene un elemento primitivo.
Podemos demostrarlo si logramos demostrar que
Lema
En cualquier cuerpo finito, si hay un elemento de ordenmultiplicativo m y otro de orden multiplicativo n, entonces hayun elemento de orden multiplicativo mcm(m, n).
![Page 34: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/34.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Existencia de elementos primitivos
Teorema
Un polinomio de grado n sobre un cuerpo no tiene mas que nraıces en el cuerpo.
Teorema
Todo cuerpo finito tiene un elemento primitivo.
Podemos demostrarlo si logramos demostrar que
Lema
En cualquier cuerpo finito, si hay un elemento de ordenmultiplicativo m y otro de orden multiplicativo n, entonces hayun elemento de orden multiplicativo mcm(m, n).
![Page 35: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/35.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Existencia de elementos primitivos
Lema
Si un grupo tiene un elemento de orden n y m es factor de nentonces existe un elemento de orden m.
Lema
En un grupo finito conmutativo, si elementos a, b tienenordenes m, n respectivamente y m, n son coprimos entonces elorden de ab es mn.
Lema
En un grupo finito conmutativo, sean m1, ...,mk los ordenes delos elementos a1, ..., ak respectivamente, con mi coprimo conmj siempre que i 6= j . Entonces el orden de a1 · · · ak esm1 · · ·mk .
![Page 36: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/36.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Existencia de elementos primitivos
Lema
Si un grupo tiene un elemento de orden n y m es factor de nentonces existe un elemento de orden m.
Lema
En un grupo finito conmutativo, si elementos a, b tienenordenes m, n respectivamente y m, n son coprimos entonces elorden de ab es mn.
Lema
En un grupo finito conmutativo, sean m1, ...,mk los ordenes delos elementos a1, ..., ak respectivamente, con mi coprimo conmj siempre que i 6= j . Entonces el orden de a1 · · · ak esm1 · · ·mk .
![Page 37: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/37.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Existencia de elementos primitivos
Lema
Si un grupo tiene un elemento de orden n y m es factor de nentonces existe un elemento de orden m.
Lema
En un grupo finito conmutativo, si elementos a, b tienenordenes m, n respectivamente y m, n son coprimos entonces elorden de ab es mn.
Lema
En un grupo finito conmutativo, sean m1, ...,mk los ordenes delos elementos a1, ..., ak respectivamente, con mi coprimo conmj siempre que i 6= j . Entonces el orden de a1 · · · ak esm1 · · ·mk .
![Page 38: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/38.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Mas sobre primalidad
¿Como encontrar primos grandes?
Es un problema interesante por sı mismo.
Y tambien porque hay aplicaciones importantes querequieren de primos grandes.
Por calculos a mano
Ano Dıgitos
1588 6
1772 10
1867 13
1876 39
Con computadorasAno Dıgitos
1952 687
1963 3.376
1971 6.002
1979 13.395
1989 65.087
1999 2.098.960
2006 9.808.358
2008 12.978.189
2013 17.425.170
![Page 39: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/39.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Mas sobre primalidad
¿Como encontrar primos grandes?
Es un problema interesante por sı mismo.
Y tambien porque hay aplicaciones importantes querequieren de primos grandes.
Por calculos a mano
Ano Dıgitos
1588 6
1772 10
1867 13
1876 39
Con computadorasAno Dıgitos
1952 687
1963 3.376
1971 6.002
1979 13.395
1989 65.087
1999 2.098.960
2006 9.808.358
2008 12.978.189
2013 17.425.170
![Page 40: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/40.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Mas sobre primalidad
¿Como encontrar primos grandes?
Es un problema interesante por sı mismo.
Y tambien porque hay aplicaciones importantes querequieren de primos grandes.
Por calculos a mano
Ano Dıgitos
1588 6
1772 10
1867 13
1876 39
Con computadorasAno Dıgitos
1952 687
1963 3.376
1971 6.002
1979 13.395
1989 65.087
1999 2.098.960
2006 9.808.358
2008 12.978.189
2013 17.425.170
![Page 41: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/41.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Mas sobre primalidad
¿Como encontrar primos grandes?
Es un problema interesante por sı mismo.
Y tambien porque hay aplicaciones importantes querequieren de primos grandes.
Por calculos a mano
Ano Dıgitos
1588 6
1772 10
1867 13
1876 39
Con computadorasAno Dıgitos
1952 687
1963 3.376
1971 6.002
1979 13.395
1989 65.087
1999 2.098.960
2006 9.808.358
2008 12.978.189
2013 17.425.170
![Page 42: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/42.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Primos de Mersenne
Definicion
Un numero primo de la forma 2p − 1 se dice primo deMersenne.
Teorema
Sea n > 2. 2n − 1 es primo si y solo si
1 n es primo, y
2 Ln−2 = 0, siendo {Lm} la sucesion definida por
L0 = 4 Lm+1 = resto(L2m − 2, 2n − 1)
![Page 43: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/43.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Primos de Mersenne
Definicion
Un numero primo de la forma 2p − 1 se dice primo deMersenne.
Teorema
Sea n > 2. 2n − 1 es primo si y solo si
1 n es primo, y
2 Ln−2 = 0, siendo {Lm} la sucesion definida por
L0 = 4 Lm+1 = resto(L2m − 2, 2n − 1)
![Page 44: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/44.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Primos de Mersenne
Definicion
Un numero primo de la forma 2p − 1 se dice primo deMersenne.
Teorema
Sea n > 2. 2n − 1 es primo si y solo si
1 n es primo, y
2 Ln−2 = 0, siendo {Lm} la sucesion definida por
L0 = 4 Lm+1 = resto(L2m − 2, 2n − 1)
![Page 45: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/45.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Primos de Mersenne
Definicion
Un numero primo de la forma 2p − 1 se dice primo deMersenne.
Teorema
Sea n > 2. 2n − 1 es primo si y solo si
1 n es primo, y
2 Ln−2 = 0, siendo {Lm} la sucesion definida por
L0 = 4 Lm+1 = resto(L2m − 2, 2n − 1)
![Page 46: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/46.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Primos de Mersenne
Definicion
Un numero primo de la forma 2p − 1 se dice primo deMersenne.
Teorema
Sea n > 2. 2n − 1 es primo si y solo si
1 n es primo, y
2 Ln−2 = 0, siendo {Lm} la sucesion definida por
L0 = 4 Lm+1 = resto(L2m − 2, 2n − 1)
![Page 47: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/47.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Test de no primalidad
Consecuencia del Pequeno Teorema de Fermat
Dado n ∈ N:si existe a t.q. 1 < a < n y an−1 6≡n 1, entonces n no es primo.
Ejemplo
Fermat conjeturo que todo numero de la forma 22n + 1 esprimo.Pero 3232 ≡232+1 3029026160.
Luego, por su propio teorema, 225+ 1 no es primo.
![Page 48: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/48.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Test de no primalidad
Consecuencia del Pequeno Teorema de Fermat
Dado n ∈ N:si existe a t.q. 1 < a < n y an−1 6≡n 1, entonces n no es primo.
Ejemplo
Fermat conjeturo que todo numero de la forma 22n + 1 esprimo.
Pero 3232 ≡232+1 3029026160.
Luego, por su propio teorema, 225+ 1 no es primo.
![Page 49: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/49.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Test de no primalidad
Consecuencia del Pequeno Teorema de Fermat
Dado n ∈ N:si existe a t.q. 1 < a < n y an−1 6≡n 1, entonces n no es primo.
Ejemplo
Fermat conjeturo que todo numero de la forma 22n + 1 esprimo.Pero 3232 ≡232+1 3029026160.
Luego, por su propio teorema, 225+ 1 no es primo.
![Page 50: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/50.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Test de no primalidad
Consecuencia del Pequeno Teorema de Fermat
Dado n ∈ N:si existe a t.q. 1 < a < n y an−1 6≡n 1, entonces n no es primo.
Ejemplo
Fermat conjeturo que todo numero de la forma 22n + 1 esprimo.Pero 3232 ≡232+1 3029026160.
Luego, por su propio teorema, 225+ 1 no es primo.
![Page 51: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/51.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Test de primalidad
Generalizacion del Pequeno Teorema de Fermat
Sean n, a ∈ N con mcd(n, a) = 1.
Entonces,n es primo ⇐⇒ ∀x ∈ N, (x + a)n ≡n xn + a
Notacion
Para n ≥ 2 y polinomios p(x), q(x), s(x), si resto(p(x), s(x)) yresto(q(x), s(x)) tienen los mismos coeficientes modulo n,entonces decimos que p(x) ≡ q(x) mod (s(x), n)
Clave para un algoritmo de tiempo polinomico
Dado n primo impar, existe r ≤⌈log5
2 n⌉
tal que para todo asuficientemente pequeno ocurre
(x + a)n ≡ xn + a mod (x r − 1, n)
![Page 52: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/52.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Test de primalidad
Generalizacion del Pequeno Teorema de Fermat
Sean n, a ∈ N con mcd(n, a) = 1. Entonces,n es primo ⇐⇒ ∀x ∈ N, (x + a)n ≡n xn + a
Notacion
Para n ≥ 2 y polinomios p(x), q(x), s(x), si resto(p(x), s(x)) yresto(q(x), s(x)) tienen los mismos coeficientes modulo n,entonces decimos que p(x) ≡ q(x) mod (s(x), n)
Clave para un algoritmo de tiempo polinomico
Dado n primo impar, existe r ≤⌈log5
2 n⌉
tal que para todo asuficientemente pequeno ocurre
(x + a)n ≡ xn + a mod (x r − 1, n)
![Page 53: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/53.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Test de primalidad
Generalizacion del Pequeno Teorema de Fermat
Sean n, a ∈ N con mcd(n, a) = 1. Entonces,n es primo ⇐⇒ ∀x ∈ N, (x + a)n ≡n xn + a
Notacion
Para n ≥ 2 y polinomios p(x), q(x), s(x),
si resto(p(x), s(x)) yresto(q(x), s(x)) tienen los mismos coeficientes modulo n,entonces decimos que p(x) ≡ q(x) mod (s(x), n)
Clave para un algoritmo de tiempo polinomico
Dado n primo impar, existe r ≤⌈log5
2 n⌉
tal que para todo asuficientemente pequeno ocurre
(x + a)n ≡ xn + a mod (x r − 1, n)
![Page 54: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/54.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Test de primalidad
Generalizacion del Pequeno Teorema de Fermat
Sean n, a ∈ N con mcd(n, a) = 1. Entonces,n es primo ⇐⇒ ∀x ∈ N, (x + a)n ≡n xn + a
Notacion
Para n ≥ 2 y polinomios p(x), q(x), s(x), si resto(p(x), s(x)) yresto(q(x), s(x)) tienen los mismos coeficientes modulo n,
entonces decimos que p(x) ≡ q(x) mod (s(x), n)
Clave para un algoritmo de tiempo polinomico
Dado n primo impar, existe r ≤⌈log5
2 n⌉
tal que para todo asuficientemente pequeno ocurre
(x + a)n ≡ xn + a mod (x r − 1, n)
![Page 55: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/55.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Test de primalidad
Generalizacion del Pequeno Teorema de Fermat
Sean n, a ∈ N con mcd(n, a) = 1. Entonces,n es primo ⇐⇒ ∀x ∈ N, (x + a)n ≡n xn + a
Notacion
Para n ≥ 2 y polinomios p(x), q(x), s(x), si resto(p(x), s(x)) yresto(q(x), s(x)) tienen los mismos coeficientes modulo n,entonces decimos que p(x) ≡ q(x) mod (s(x), n)
Clave para un algoritmo de tiempo polinomico
Dado n primo impar, existe r ≤⌈log5
2 n⌉
tal que para todo asuficientemente pequeno ocurre
(x + a)n ≡ xn + a mod (x r − 1, n)
![Page 56: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/56.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Test de primalidad
Generalizacion del Pequeno Teorema de Fermat
Sean n, a ∈ N con mcd(n, a) = 1. Entonces,n es primo ⇐⇒ ∀x ∈ N, (x + a)n ≡n xn + a
Notacion
Para n ≥ 2 y polinomios p(x), q(x), s(x), si resto(p(x), s(x)) yresto(q(x), s(x)) tienen los mismos coeficientes modulo n,entonces decimos que p(x) ≡ q(x) mod (s(x), n)
Clave para un algoritmo de tiempo polinomico
Dado n primo impar,
existe r ≤⌈log5
2 n⌉
tal que para todo asuficientemente pequeno ocurre
(x + a)n ≡ xn + a mod (x r − 1, n)
![Page 57: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/57.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Test de primalidad
Generalizacion del Pequeno Teorema de Fermat
Sean n, a ∈ N con mcd(n, a) = 1. Entonces,n es primo ⇐⇒ ∀x ∈ N, (x + a)n ≡n xn + a
Notacion
Para n ≥ 2 y polinomios p(x), q(x), s(x), si resto(p(x), s(x)) yresto(q(x), s(x)) tienen los mismos coeficientes modulo n,entonces decimos que p(x) ≡ q(x) mod (s(x), n)
Clave para un algoritmo de tiempo polinomico
Dado n primo impar, existe r ≤⌈log5
2 n⌉
tal que
para todo asuficientemente pequeno ocurre
(x + a)n ≡ xn + a mod (x r − 1, n)
![Page 58: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/58.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Test de primalidad
Generalizacion del Pequeno Teorema de Fermat
Sean n, a ∈ N con mcd(n, a) = 1. Entonces,n es primo ⇐⇒ ∀x ∈ N, (x + a)n ≡n xn + a
Notacion
Para n ≥ 2 y polinomios p(x), q(x), s(x), si resto(p(x), s(x)) yresto(q(x), s(x)) tienen los mismos coeficientes modulo n,entonces decimos que p(x) ≡ q(x) mod (s(x), n)
Clave para un algoritmo de tiempo polinomico
Dado n primo impar, existe r ≤⌈log5
2 n⌉
tal que para todo asuficientemente pequeno ocurre
(x + a)n ≡ xn + a mod (x r − 1, n)
![Page 59: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/59.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Test de primalidad
Generalizacion del Pequeno Teorema de Fermat
Sean n, a ∈ N con mcd(n, a) = 1. Entonces,n es primo ⇐⇒ ∀x ∈ N, (x + a)n ≡n xn + a
Notacion
Para n ≥ 2 y polinomios p(x), q(x), s(x), si resto(p(x), s(x)) yresto(q(x), s(x)) tienen los mismos coeficientes modulo n,entonces decimos que p(x) ≡ q(x) mod (s(x), n)
Clave para un algoritmo de tiempo polinomico
Dado n primo impar, existe r ≤⌈log5
2 n⌉
tal que para todo asuficientemente pequeno ocurre
(x + a)n ≡ xn + a mod (x r − 1, n)
![Page 60: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/60.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Algoritmo AKS para primalidad
AKS(n) =
. si (∃a ∈ N, b > 1 : n = ab) NO
. r := mın{m : mcd(n,m) = 1 ∧mın{k > 0 : nk ≡m 1} > log2
2n}. si (∃a ≤ r : 1 < mcd(a, n) < n) NO. si (n ≤ r) SI
. para a = 1..⌊√
Φ(r) log2 n⌋
. . si ((X + a)n 6= X n + a mod (X r − 1, n)) NO
. SI
![Page 61: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/61.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Algoritmo AKS para primalidad
AKS(n) =. si (∃a ∈ N, b > 1 : n = ab) NO
. r := mın{m : mcd(n,m) = 1 ∧mın{k > 0 : nk ≡m 1} > log2
2n}. si (∃a ≤ r : 1 < mcd(a, n) < n) NO. si (n ≤ r) SI
. para a = 1..⌊√
Φ(r) log2 n⌋
. . si ((X + a)n 6= X n + a mod (X r − 1, n)) NO
. SI
![Page 62: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/62.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Algoritmo AKS para primalidad
AKS(n) =. si (∃a ∈ N, b > 1 : n = ab) NO. r := mın{m : mcd(n,m) = 1 ∧
mın{k > 0 : nk ≡m 1} > log22n}
. si (∃a ≤ r : 1 < mcd(a, n) < n) NO
. si (n ≤ r) SI
. para a = 1..⌊√
Φ(r) log2 n⌋
. . si ((X + a)n 6= X n + a mod (X r − 1, n)) NO
. SI
![Page 63: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/63.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Algoritmo AKS para primalidad
AKS(n) =. si (∃a ∈ N, b > 1 : n = ab) NO. r := mın{m : mcd(n,m) = 1 ∧
mın{k > 0 : nk ≡m 1} > log22n}
. si (∃a ≤ r : 1 < mcd(a, n) < n) NO
. si (n ≤ r) SI
. para a = 1..⌊√
Φ(r) log2 n⌋
. . si ((X + a)n 6= X n + a mod (X r − 1, n)) NO
. SI
![Page 64: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/64.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Algoritmo AKS para primalidad
AKS(n) =. si (∃a ∈ N, b > 1 : n = ab) NO. r := mın{m : mcd(n,m) = 1 ∧
mın{k > 0 : nk ≡m 1} > log22n}
. si (∃a ≤ r : 1 < mcd(a, n) < n) NO
. si (n ≤ r) SI
. para a = 1..⌊√
Φ(r) log2 n⌋
. . si ((X + a)n 6= X n + a mod (X r − 1, n)) NO
. SI
![Page 65: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/65.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Algoritmo AKS para primalidad
AKS(n) =. si (∃a ∈ N, b > 1 : n = ab) NO. r := mın{m : mcd(n,m) = 1 ∧
mın{k > 0 : nk ≡m 1} > log22n}
. si (∃a ≤ r : 1 < mcd(a, n) < n) NO
. si (n ≤ r) SI
. para a = 1..⌊√
Φ(r) log2 n⌋
. . si ((X + a)n 6= X n + a mod (X r − 1, n)) NO
. SI
![Page 66: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/66.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Algoritmo AKS para primalidad
AKS(n) =. si (∃a ∈ N, b > 1 : n = ab) NO. r := mın{m : mcd(n,m) = 1 ∧
mın{k > 0 : nk ≡m 1} > log22n}
. si (∃a ≤ r : 1 < mcd(a, n) < n) NO
. si (n ≤ r) SI
. para a = 1..⌊√
Φ(r) log2 n⌋
. . si ((X + a)n 6= X n + a mod (X r − 1, n)) NO
. SI
![Page 67: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/67.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Algoritmo AKS para primalidad
AKS(n) =. si (∃a ∈ N, b > 1 : n = ab) NO. r := mın{m : mcd(n,m) = 1 ∧
mın{k > 0 : nk ≡m 1} > log22n}
. si (∃a ≤ r : 1 < mcd(a, n) < n) NO
. si (n ≤ r) SI
. para a = 1..⌊√
Φ(r) log2 n⌋
. . si ((X + a)n 6= X n + a mod (X r − 1, n)) NO
. SI
![Page 68: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/68.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Algoritmo AKS para primalidad
AKS(n) =. si (∃a ∈ N, b > 1 : n = ab) NO. r := mın{m : mcd(n,m) = 1 ∧
mın{k > 0 : nk ≡m 1} > log22n}
. si (∃a ≤ r : 1 < mcd(a, n) < n) NO
. si (n ≤ r) SI
. para a = 1..⌊√
Φ(r) log2 n⌋
. . si ((X + a)n 6= X n + a mod (X r − 1, n)) NO
. SI
![Page 69: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/69.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Criptografıa
Descripcion del problema
Personajes: Emisor (E)
- Receptor (R) - Intruso (I).
R desea recibir mensaje secreto M que envıa E.
I puede leer lo que E mande.
Entonces E, en lugar de M, envıa C = f (M), con alguna findicada por R.(M: mensaje original C : mensaje cifrado.)
R conoce un metodo para calcular f −1. Recibido C ,calcula f −1(C ) = M, recuperando ası el M original.
Si I no conoce f −1, no puede enterarse del contenido deM.
¿Cuales f son apropiadas?
![Page 70: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/70.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Criptografıa
Descripcion del problema
Personajes: Emisor (E) - Receptor (R)
- Intruso (I).
R desea recibir mensaje secreto M que envıa E.
I puede leer lo que E mande.
Entonces E, en lugar de M, envıa C = f (M), con alguna findicada por R.(M: mensaje original C : mensaje cifrado.)
R conoce un metodo para calcular f −1. Recibido C ,calcula f −1(C ) = M, recuperando ası el M original.
Si I no conoce f −1, no puede enterarse del contenido deM.
¿Cuales f son apropiadas?
![Page 71: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/71.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Criptografıa
Descripcion del problema
Personajes: Emisor (E) - Receptor (R) - Intruso (I).
R desea recibir mensaje secreto M que envıa E.
I puede leer lo que E mande.
Entonces E, en lugar de M, envıa C = f (M), con alguna findicada por R.(M: mensaje original C : mensaje cifrado.)
R conoce un metodo para calcular f −1. Recibido C ,calcula f −1(C ) = M, recuperando ası el M original.
Si I no conoce f −1, no puede enterarse del contenido deM.
¿Cuales f son apropiadas?
![Page 72: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/72.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Criptografıa
Descripcion del problema
Personajes: Emisor (E) - Receptor (R) - Intruso (I).
R desea recibir mensaje secreto M que envıa E.
I puede leer lo que E mande.
Entonces E, en lugar de M, envıa C = f (M), con alguna findicada por R.(M: mensaje original C : mensaje cifrado.)
R conoce un metodo para calcular f −1. Recibido C ,calcula f −1(C ) = M, recuperando ası el M original.
Si I no conoce f −1, no puede enterarse del contenido deM.
¿Cuales f son apropiadas?
![Page 73: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/73.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Criptografıa
Descripcion del problema
Personajes: Emisor (E) - Receptor (R) - Intruso (I).
R desea recibir mensaje secreto M que envıa E.
I puede leer lo que E mande.
Entonces E, en lugar de M, envıa C = f (M), con alguna findicada por R.(M: mensaje original C : mensaje cifrado.)
R conoce un metodo para calcular f −1. Recibido C ,calcula f −1(C ) = M, recuperando ası el M original.
Si I no conoce f −1, no puede enterarse del contenido deM.
¿Cuales f son apropiadas?
![Page 74: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/74.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Criptografıa
Descripcion del problema
Personajes: Emisor (E) - Receptor (R) - Intruso (I).
R desea recibir mensaje secreto M que envıa E.
I puede leer lo que E mande.
Entonces E, en lugar de M, envıa C = f (M), con alguna findicada por R.
(M: mensaje original C : mensaje cifrado.)
R conoce un metodo para calcular f −1. Recibido C ,calcula f −1(C ) = M, recuperando ası el M original.
Si I no conoce f −1, no puede enterarse del contenido deM.
¿Cuales f son apropiadas?
![Page 75: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/75.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Criptografıa
Descripcion del problema
Personajes: Emisor (E) - Receptor (R) - Intruso (I).
R desea recibir mensaje secreto M que envıa E.
I puede leer lo que E mande.
Entonces E, en lugar de M, envıa C = f (M), con alguna findicada por R.(M: mensaje original
C : mensaje cifrado.)
R conoce un metodo para calcular f −1. Recibido C ,calcula f −1(C ) = M, recuperando ası el M original.
Si I no conoce f −1, no puede enterarse del contenido deM.
¿Cuales f son apropiadas?
![Page 76: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/76.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Criptografıa
Descripcion del problema
Personajes: Emisor (E) - Receptor (R) - Intruso (I).
R desea recibir mensaje secreto M que envıa E.
I puede leer lo que E mande.
Entonces E, en lugar de M, envıa C = f (M), con alguna findicada por R.(M: mensaje original C : mensaje cifrado.)
R conoce un metodo para calcular f −1. Recibido C ,calcula f −1(C ) = M, recuperando ası el M original.
Si I no conoce f −1, no puede enterarse del contenido deM.
¿Cuales f son apropiadas?
![Page 77: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/77.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Criptografıa
Descripcion del problema
Personajes: Emisor (E) - Receptor (R) - Intruso (I).
R desea recibir mensaje secreto M que envıa E.
I puede leer lo que E mande.
Entonces E, en lugar de M, envıa C = f (M), con alguna findicada por R.(M: mensaje original C : mensaje cifrado.)
R conoce un metodo para calcular f −1. Recibido C ,calcula f −1(C ) = M, recuperando ası el M original.
Si I no conoce f −1, no puede enterarse del contenido deM.
¿Cuales f son apropiadas?
![Page 78: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/78.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Criptografıa
Descripcion del problema
Personajes: Emisor (E) - Receptor (R) - Intruso (I).
R desea recibir mensaje secreto M que envıa E.
I puede leer lo que E mande.
Entonces E, en lugar de M, envıa C = f (M), con alguna findicada por R.(M: mensaje original C : mensaje cifrado.)
R conoce un metodo para calcular f −1. Recibido C ,calcula f −1(C ) = M, recuperando ası el M original.
Si I no conoce f −1, no puede enterarse del contenido deM.
¿Cuales f son apropiadas?
![Page 79: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/79.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Criptografıa
Descripcion del problema
Personajes: Emisor (E) - Receptor (R) - Intruso (I).
R desea recibir mensaje secreto M que envıa E.
I puede leer lo que E mande.
Entonces E, en lugar de M, envıa C = f (M), con alguna findicada por R.(M: mensaje original C : mensaje cifrado.)
R conoce un metodo para calcular f −1. Recibido C ,calcula f −1(C ) = M, recuperando ası el M original.
Si I no conoce f −1, no puede enterarse del contenido deM.
¿Cuales f son apropiadas?
![Page 80: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/80.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Funciones de encriptacion apropiadas
Propiedades deseables de f
1 Que sea facilmente aplicable a M.
2 Invertible (o casi).
3 Que f −1(C ) sea facil de calcular para R pero difıcil para I,por mas que conozca f (M), ¡y aun conociendo f !.
Consecuencias de ello (si se logra):
La seguridad de la comunicacion no esta basada enmantener f en secreto.
E y R no necesitan reunirse para intercambiar f y f −1.
f puede ser periodicamente modificada.
![Page 81: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/81.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Funciones de encriptacion apropiadas
Propiedades deseables de f
1 Que sea facilmente aplicable a M.
2 Invertible (o casi).
3 Que f −1(C ) sea facil de calcular para R pero difıcil para I,por mas que conozca f (M), ¡y aun conociendo f !.
Consecuencias de ello (si se logra):
La seguridad de la comunicacion no esta basada enmantener f en secreto.
E y R no necesitan reunirse para intercambiar f y f −1.
f puede ser periodicamente modificada.
![Page 82: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/82.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Funciones de encriptacion apropiadas
Propiedades deseables de f
1 Que sea facilmente aplicable a M.
2 Invertible (o casi).
3 Que f −1(C ) sea facil de calcular para R pero difıcil para I,
por mas que conozca f (M), ¡y aun conociendo f !.
Consecuencias de ello (si se logra):
La seguridad de la comunicacion no esta basada enmantener f en secreto.
E y R no necesitan reunirse para intercambiar f y f −1.
f puede ser periodicamente modificada.
![Page 83: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/83.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Funciones de encriptacion apropiadas
Propiedades deseables de f
1 Que sea facilmente aplicable a M.
2 Invertible (o casi).
3 Que f −1(C ) sea facil de calcular para R pero difıcil para I,por mas que conozca f (M),
¡y aun conociendo f !.
Consecuencias de ello (si se logra):
La seguridad de la comunicacion no esta basada enmantener f en secreto.
E y R no necesitan reunirse para intercambiar f y f −1.
f puede ser periodicamente modificada.
![Page 84: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/84.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Funciones de encriptacion apropiadas
Propiedades deseables de f
1 Que sea facilmente aplicable a M.
2 Invertible (o casi).
3 Que f −1(C ) sea facil de calcular para R pero difıcil para I,por mas que conozca f (M), ¡y aun conociendo f !.
Consecuencias de ello (si se logra):
La seguridad de la comunicacion no esta basada enmantener f en secreto.
E y R no necesitan reunirse para intercambiar f y f −1.
f puede ser periodicamente modificada.
![Page 85: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/85.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Funciones de encriptacion apropiadas
Propiedades deseables de f
1 Que sea facilmente aplicable a M.
2 Invertible (o casi).
3 Que f −1(C ) sea facil de calcular para R pero difıcil para I,por mas que conozca f (M), ¡y aun conociendo f !.
Consecuencias de ello (si se logra):
La seguridad de la comunicacion no esta basada enmantener f en secreto.
E y R no necesitan reunirse para intercambiar f y f −1.
f puede ser periodicamente modificada.
![Page 86: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/86.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Funciones de encriptacion apropiadas
Propiedades deseables de f
1 Que sea facilmente aplicable a M.
2 Invertible (o casi).
3 Que f −1(C ) sea facil de calcular para R pero difıcil para I,por mas que conozca f (M), ¡y aun conociendo f !.
Consecuencias de ello (si se logra):
La seguridad de la comunicacion no esta basada enmantener f en secreto.
E y R no necesitan reunirse para intercambiar f y f −1.
f puede ser periodicamente modificada.
![Page 87: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/87.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Funciones de encriptacion apropiadas
Propiedades deseables de f
1 Que sea facilmente aplicable a M.
2 Invertible (o casi).
3 Que f −1(C ) sea facil de calcular para R pero difıcil para I,por mas que conozca f (M), ¡y aun conociendo f !.
Consecuencias de ello (si se logra):
La seguridad de la comunicacion no esta basada enmantener f en secreto.
E y R no necesitan reunirse para intercambiar f y f −1.
f puede ser periodicamente modificada.
![Page 88: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/88.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Funciones de encriptacion apropiadas
Propiedades deseables de f
1 Que sea facilmente aplicable a M.
2 Invertible (o casi).
3 Que f −1(C ) sea facil de calcular para R pero difıcil para I,por mas que conozca f (M), ¡y aun conociendo f !.
Consecuencias de ello (si se logra):
La seguridad de la comunicacion no esta basada enmantener f en secreto.
E y R no necesitan reunirse para intercambiar f y f −1.
f puede ser periodicamente modificada.
![Page 89: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/89.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Ejemplos de esquemas (no satisfactorios)
1 p: un primo grande
a: elemento primitivo de Zp
f (M) = aM mod p (es biyeccion).Debilidad: f −1 es difıcil de calcular (incluso para R).
2 p: un primo grande tal que p ≡4 3f (M) = M2 mod p (es casi invertible).f −1(C ) = ±C (p+1)/4 mod pDebilidad: El calculo de f −1 es facil para I.
![Page 90: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/90.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Ejemplos de esquemas (no satisfactorios)
1 p: un primo grandea: elemento primitivo de Zp
f (M) = aM mod p (es biyeccion).Debilidad: f −1 es difıcil de calcular (incluso para R).
2 p: un primo grande tal que p ≡4 3f (M) = M2 mod p (es casi invertible).f −1(C ) = ±C (p+1)/4 mod pDebilidad: El calculo de f −1 es facil para I.
![Page 91: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/91.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Ejemplos de esquemas (no satisfactorios)
1 p: un primo grandea: elemento primitivo de Zp
f (M) = aM mod p (es biyeccion).
Debilidad: f −1 es difıcil de calcular (incluso para R).
2 p: un primo grande tal que p ≡4 3f (M) = M2 mod p (es casi invertible).f −1(C ) = ±C (p+1)/4 mod pDebilidad: El calculo de f −1 es facil para I.
![Page 92: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/92.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Ejemplos de esquemas (no satisfactorios)
1 p: un primo grandea: elemento primitivo de Zp
f (M) = aM mod p (es biyeccion).Debilidad: f −1 es difıcil de calcular (incluso para R).
2 p: un primo grande tal que p ≡4 3f (M) = M2 mod p (es casi invertible).f −1(C ) = ±C (p+1)/4 mod pDebilidad: El calculo de f −1 es facil para I.
![Page 93: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/93.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Ejemplos de esquemas (no satisfactorios)
1 p: un primo grandea: elemento primitivo de Zp
f (M) = aM mod p (es biyeccion).Debilidad: f −1 es difıcil de calcular (incluso para R).
2 p: un primo grande tal que p ≡4 3
f (M) = M2 mod p (es casi invertible).f −1(C ) = ±C (p+1)/4 mod pDebilidad: El calculo de f −1 es facil para I.
![Page 94: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/94.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Ejemplos de esquemas (no satisfactorios)
1 p: un primo grandea: elemento primitivo de Zp
f (M) = aM mod p (es biyeccion).Debilidad: f −1 es difıcil de calcular (incluso para R).
2 p: un primo grande tal que p ≡4 3f (M) = M2 mod p (es casi invertible).
f −1(C ) = ±C (p+1)/4 mod pDebilidad: El calculo de f −1 es facil para I.
![Page 95: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/95.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Ejemplos de esquemas (no satisfactorios)
1 p: un primo grandea: elemento primitivo de Zp
f (M) = aM mod p (es biyeccion).Debilidad: f −1 es difıcil de calcular (incluso para R).
2 p: un primo grande tal que p ≡4 3f (M) = M2 mod p (es casi invertible).f −1(C ) = ±C (p+1)/4 mod p
Debilidad: El calculo de f −1 es facil para I.
![Page 96: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/96.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Ejemplos de esquemas (no satisfactorios)
1 p: un primo grandea: elemento primitivo de Zp
f (M) = aM mod p (es biyeccion).Debilidad: f −1 es difıcil de calcular (incluso para R).
2 p: un primo grande tal que p ≡4 3f (M) = M2 mod p (es casi invertible).f −1(C ) = ±C (p+1)/4 mod pDebilidad: El calculo de f −1 es facil para I.
![Page 97: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/97.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
El metodo de Rabin
n = pq con p y q primos grandes y distintos, ambos ≡4 3
f (M) = M2 mod n (tambien es casi invertible).Si C = f (M), entonces M es la solucion a uno de los siguientescuatro sistemas:{
M ≡p Cp+1
4
M ≡q Cq+1
4
{M ≡p C
p+14
M ≡q −Cq+1
4{M ≡p −C
p+14
M ≡q Cq+1
4
{M ≡p −C
p+14
M ≡q −Cq+1
4
![Page 98: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/98.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
El metodo de Rabin
n = pq con p y q primos grandes y distintos, ambos ≡4 3f (M) = M2 mod n (tambien es casi invertible).
Si C = f (M), entonces M es la solucion a uno de los siguientescuatro sistemas:{
M ≡p Cp+1
4
M ≡q Cq+1
4
{M ≡p C
p+14
M ≡q −Cq+1
4{M ≡p −C
p+14
M ≡q Cq+1
4
{M ≡p −C
p+14
M ≡q −Cq+1
4
![Page 99: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/99.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
El metodo de Rabin
n = pq con p y q primos grandes y distintos, ambos ≡4 3f (M) = M2 mod n (tambien es casi invertible).Si C = f (M), entonces M es la solucion a uno de los siguientescuatro sistemas:
{M ≡p C
p+14
M ≡q Cq+1
4
{M ≡p C
p+14
M ≡q −Cq+1
4{M ≡p −C
p+14
M ≡q Cq+1
4
{M ≡p −C
p+14
M ≡q −Cq+1
4
![Page 100: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/100.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
El metodo de Rabin
n = pq con p y q primos grandes y distintos, ambos ≡4 3f (M) = M2 mod n (tambien es casi invertible).Si C = f (M), entonces M es la solucion a uno de los siguientescuatro sistemas:{
M ≡p Cp+1
4
M ≡q Cq+1
4
{M ≡p C
p+14
M ≡q −Cq+1
4{M ≡p −C
p+14
M ≡q Cq+1
4
{M ≡p −C
p+14
M ≡q −Cq+1
4
![Page 101: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/101.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
El metodo de Rabin
n = pq con p y q primos grandes y distintos, ambos ≡4 3f (M) = M2 mod n (tambien es casi invertible).Si C = f (M), entonces M es la solucion a uno de los siguientescuatro sistemas:{
M ≡p Cp+1
4
M ≡q Cq+1
4
{M ≡p C
p+14
M ≡q −Cq+1
4
{M ≡p −C
p+14
M ≡q Cq+1
4
{M ≡p −C
p+14
M ≡q −Cq+1
4
![Page 102: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/102.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
El metodo de Rabin
n = pq con p y q primos grandes y distintos, ambos ≡4 3f (M) = M2 mod n (tambien es casi invertible).Si C = f (M), entonces M es la solucion a uno de los siguientescuatro sistemas:{
M ≡p Cp+1
4
M ≡q Cq+1
4
{M ≡p C
p+14
M ≡q −Cq+1
4{M ≡p −C
p+14
M ≡q Cq+1
4
{M ≡p −C
p+14
M ≡q −Cq+1
4
![Page 103: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/103.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
El metodo de Rabin
n = pq con p y q primos grandes y distintos, ambos ≡4 3f (M) = M2 mod n (tambien es casi invertible).Si C = f (M), entonces M es la solucion a uno de los siguientescuatro sistemas:{
M ≡p Cp+1
4
M ≡q Cq+1
4
{M ≡p C
p+14
M ≡q −Cq+1
4{M ≡p −C
p+14
M ≡q Cq+1
4
{M ≡p −C
p+14
M ≡q −Cq+1
4
![Page 104: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/104.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
El metodo RSA
n = pq con p y q primos grandes y distintos
d : cualquier coprimo con (p − 1)(q − 1)e: el inverso de d en Z(p−1)(q−1)
f (M) = Me mod nf −1(C ) = Cd mod n
Claves del funcionamiento
Para todo n, {k ∈ Zn : mcd(k, n) = 1} es grupo con elproducto modulo n. Su orden se denota ϕ(n).
Si a es coprimo con n, entonces aϕ(n)+1 ≡n a.
En particular, para n = pq con p y q primos distintos:
ϕ(n) = (p − 1)(q − 1).∀a ∈ Zn, a
(p−1)(q−1)+1 ≡n a.Si d , e se eligen de acuerdo al metodo, entonces(Md)e = M.
![Page 105: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/105.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
El metodo RSA
n = pq con p y q primos grandes y distintosd : cualquier coprimo con (p − 1)(q − 1)
e: el inverso de d en Z(p−1)(q−1)
f (M) = Me mod nf −1(C ) = Cd mod n
Claves del funcionamiento
Para todo n, {k ∈ Zn : mcd(k, n) = 1} es grupo con elproducto modulo n. Su orden se denota ϕ(n).
Si a es coprimo con n, entonces aϕ(n)+1 ≡n a.
En particular, para n = pq con p y q primos distintos:
ϕ(n) = (p − 1)(q − 1).∀a ∈ Zn, a
(p−1)(q−1)+1 ≡n a.Si d , e se eligen de acuerdo al metodo, entonces(Md)e = M.
![Page 106: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/106.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
El metodo RSA
n = pq con p y q primos grandes y distintosd : cualquier coprimo con (p − 1)(q − 1)e: el inverso de d en Z(p−1)(q−1)
f (M) = Me mod nf −1(C ) = Cd mod n
Claves del funcionamiento
Para todo n, {k ∈ Zn : mcd(k, n) = 1} es grupo con elproducto modulo n. Su orden se denota ϕ(n).
Si a es coprimo con n, entonces aϕ(n)+1 ≡n a.
En particular, para n = pq con p y q primos distintos:
ϕ(n) = (p − 1)(q − 1).∀a ∈ Zn, a
(p−1)(q−1)+1 ≡n a.Si d , e se eligen de acuerdo al metodo, entonces(Md)e = M.
![Page 107: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/107.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
El metodo RSA
n = pq con p y q primos grandes y distintosd : cualquier coprimo con (p − 1)(q − 1)e: el inverso de d en Z(p−1)(q−1)
f (M) = Me mod n
f −1(C ) = Cd mod n
Claves del funcionamiento
Para todo n, {k ∈ Zn : mcd(k, n) = 1} es grupo con elproducto modulo n. Su orden se denota ϕ(n).
Si a es coprimo con n, entonces aϕ(n)+1 ≡n a.
En particular, para n = pq con p y q primos distintos:
ϕ(n) = (p − 1)(q − 1).∀a ∈ Zn, a
(p−1)(q−1)+1 ≡n a.Si d , e se eligen de acuerdo al metodo, entonces(Md)e = M.
![Page 108: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/108.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
El metodo RSA
n = pq con p y q primos grandes y distintosd : cualquier coprimo con (p − 1)(q − 1)e: el inverso de d en Z(p−1)(q−1)
f (M) = Me mod nf −1(C ) = Cd mod n
Claves del funcionamiento
Para todo n, {k ∈ Zn : mcd(k, n) = 1} es grupo con elproducto modulo n. Su orden se denota ϕ(n).
Si a es coprimo con n, entonces aϕ(n)+1 ≡n a.
En particular, para n = pq con p y q primos distintos:
ϕ(n) = (p − 1)(q − 1).∀a ∈ Zn, a
(p−1)(q−1)+1 ≡n a.Si d , e se eligen de acuerdo al metodo, entonces(Md)e = M.
![Page 109: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/109.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
El metodo RSA
n = pq con p y q primos grandes y distintosd : cualquier coprimo con (p − 1)(q − 1)e: el inverso de d en Z(p−1)(q−1)
f (M) = Me mod nf −1(C ) = Cd mod n
Claves del funcionamiento
Para todo n, {k ∈ Zn : mcd(k, n) = 1} es grupo con elproducto modulo n. Su orden se denota ϕ(n).
Si a es coprimo con n, entonces aϕ(n)+1 ≡n a.
En particular, para n = pq con p y q primos distintos:
ϕ(n) = (p − 1)(q − 1).∀a ∈ Zn, a
(p−1)(q−1)+1 ≡n a.Si d , e se eligen de acuerdo al metodo, entonces(Md)e = M.
![Page 110: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/110.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
El metodo RSA
n = pq con p y q primos grandes y distintosd : cualquier coprimo con (p − 1)(q − 1)e: el inverso de d en Z(p−1)(q−1)
f (M) = Me mod nf −1(C ) = Cd mod n
Claves del funcionamiento
Para todo n, {k ∈ Zn : mcd(k, n) = 1} es grupo con elproducto modulo n. Su orden se denota ϕ(n).
Si a es coprimo con n, entonces aϕ(n)+1 ≡n a.
En particular, para n = pq con p y q primos distintos:
ϕ(n) = (p − 1)(q − 1).∀a ∈ Zn, a
(p−1)(q−1)+1 ≡n a.Si d , e se eligen de acuerdo al metodo, entonces(Md)e = M.
![Page 111: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/111.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
El metodo RSA
n = pq con p y q primos grandes y distintosd : cualquier coprimo con (p − 1)(q − 1)e: el inverso de d en Z(p−1)(q−1)
f (M) = Me mod nf −1(C ) = Cd mod n
Claves del funcionamiento
Para todo n, {k ∈ Zn : mcd(k, n) = 1} es grupo con elproducto modulo n. Su orden se denota ϕ(n).
Si a es coprimo con n, entonces aϕ(n)+1 ≡n a.
En particular, para n = pq con p y q primos distintos:
ϕ(n) = (p − 1)(q − 1).∀a ∈ Zn, a
(p−1)(q−1)+1 ≡n a.Si d , e se eligen de acuerdo al metodo, entonces(Md)e = M.
![Page 112: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/112.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
El metodo RSA
n = pq con p y q primos grandes y distintosd : cualquier coprimo con (p − 1)(q − 1)e: el inverso de d en Z(p−1)(q−1)
f (M) = Me mod nf −1(C ) = Cd mod n
Claves del funcionamiento
Para todo n, {k ∈ Zn : mcd(k, n) = 1} es grupo con elproducto modulo n. Su orden se denota ϕ(n).
Si a es coprimo con n, entonces aϕ(n)+1 ≡n a.
En particular, para n = pq con p y q primos distintos:
ϕ(n) = (p − 1)(q − 1).
∀a ∈ Zn, a(p−1)(q−1)+1 ≡n a.
Si d , e se eligen de acuerdo al metodo, entonces(Md)e = M.
![Page 113: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/113.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
El metodo RSA
n = pq con p y q primos grandes y distintosd : cualquier coprimo con (p − 1)(q − 1)e: el inverso de d en Z(p−1)(q−1)
f (M) = Me mod nf −1(C ) = Cd mod n
Claves del funcionamiento
Para todo n, {k ∈ Zn : mcd(k, n) = 1} es grupo con elproducto modulo n. Su orden se denota ϕ(n).
Si a es coprimo con n, entonces aϕ(n)+1 ≡n a.
En particular, para n = pq con p y q primos distintos:
ϕ(n) = (p − 1)(q − 1).∀a ∈ Zn, a
(p−1)(q−1)+1 ≡n a.
Si d , e se eligen de acuerdo al metodo, entonces(Md)e = M.
![Page 114: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/114.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
El metodo RSA
n = pq con p y q primos grandes y distintosd : cualquier coprimo con (p − 1)(q − 1)e: el inverso de d en Z(p−1)(q−1)
f (M) = Me mod nf −1(C ) = Cd mod n
Claves del funcionamiento
Para todo n, {k ∈ Zn : mcd(k, n) = 1} es grupo con elproducto modulo n. Su orden se denota ϕ(n).
Si a es coprimo con n, entonces aϕ(n)+1 ≡n a.
En particular, para n = pq con p y q primos distintos:
ϕ(n) = (p − 1)(q − 1).∀a ∈ Zn, a
(p−1)(q−1)+1 ≡n a.Si d , e se eligen de acuerdo al metodo, entonces(Md)e = M.
![Page 115: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/115.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Ataque a Rabin y RSA
Si I puede factorizar n, entonces puede decodificar los mensajes.
Un metodo de factorizacion: sacar raıces cuadradas en Zn
Si a, b ∈ Zn satisfacen simultaneamente
a 6= ±b
a2 ≡n b2,
entonces mcd(a + b, n) es factor propio de n.
![Page 116: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/116.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Ataque a Rabin y RSA
Si I puede factorizar n, entonces puede decodificar los mensajes.
Un metodo de factorizacion: sacar raıces cuadradas en Zn
Si a, b ∈ Zn satisfacen simultaneamente
a 6= ±b
a2 ≡n b2,
entonces mcd(a + b, n) es factor propio de n.
![Page 117: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/117.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Ataque a Rabin y RSA
Si I puede factorizar n, entonces puede decodificar los mensajes.
Un metodo de factorizacion: sacar raıces cuadradas en Zn
Si a, b ∈ Zn satisfacen simultaneamente
a 6= ±b
a2 ≡n b2,
entonces mcd(a + b, n) es factor propio de n.
![Page 118: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/118.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Ataque a Rabin y RSA
Si I puede factorizar n, entonces puede decodificar los mensajes.
Un metodo de factorizacion: sacar raıces cuadradas en Zn
Si a, b ∈ Zn satisfacen simultaneamente
a 6= ±b
a2 ≡n b2,
entonces mcd(a + b, n) es factor propio de n.
![Page 119: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/119.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Ataque a Rabin y RSA
Si I puede factorizar n, entonces puede decodificar los mensajes.
Un metodo de factorizacion: sacar raıces cuadradas en Zn
Si a, b ∈ Zn satisfacen simultaneamente
a 6= ±b
a2 ≡n b2,
entonces mcd(a + b, n) es factor propio de n.
![Page 120: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/120.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Aritmetica de numeros grandes
Representacion de numeros
Se elige B > 1 (la base de numeracion).
n se representa mediante sucesion d = [d0, . . . , dk ]:
0 ≤ di < B para cada i .n =
∑ki=0 di × B i .
(Sucesion vacıa: ∅ → representa a 0.)
Valor a partir de la representacion
val(d ,B) =. si (d = ∅) 0. sino d0 + B × val(resto(d))
![Page 121: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/121.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Aritmetica de numeros grandes
Representacion de numeros
Se elige B > 1 (la base de numeracion).
n se representa mediante sucesion d = [d0, . . . , dk ]:
0 ≤ di < B para cada i .n =
∑ki=0 di × B i .
(Sucesion vacıa: ∅ → representa a 0.)
Valor a partir de la representacion
val(d ,B) =. si (d = ∅) 0. sino d0 + B × val(resto(d))
![Page 122: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/122.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Aritmetica de numeros grandes
Representacion de numeros
Se elige B > 1 (la base de numeracion).
n se representa mediante sucesion d = [d0, . . . , dk ]:
0 ≤ di < B para cada i .
n =∑k
i=0 di × B i .
(Sucesion vacıa: ∅ → representa a 0.)
Valor a partir de la representacion
val(d ,B) =. si (d = ∅) 0. sino d0 + B × val(resto(d))
![Page 123: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/123.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Aritmetica de numeros grandes
Representacion de numeros
Se elige B > 1 (la base de numeracion).
n se representa mediante sucesion d = [d0, . . . , dk ]:
0 ≤ di < B para cada i .n =
∑ki=0 di × B i .
(Sucesion vacıa: ∅ → representa a 0.)
Valor a partir de la representacion
val(d ,B) =. si (d = ∅) 0. sino d0 + B × val(resto(d))
![Page 124: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/124.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Aritmetica de numeros grandes
Representacion de numeros
Se elige B > 1 (la base de numeracion).
n se representa mediante sucesion d = [d0, . . . , dk ]:
0 ≤ di < B para cada i .n =
∑ki=0 di × B i .
(Sucesion vacıa: ∅ → representa a 0.)
Valor a partir de la representacion
val(d ,B) =. si (d = ∅) 0. sino d0 + B × val(resto(d))
![Page 125: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/125.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Aritmetica de numeros grandes
Representacion de numeros
Se elige B > 1 (la base de numeracion).
n se representa mediante sucesion d = [d0, . . . , dk ]:
0 ≤ di < B para cada i .n =
∑ki=0 di × B i .
(Sucesion vacıa: ∅ → representa a 0.)
Valor a partir de la representacion
val(d ,B) =. si (d = ∅) 0
. sino d0 + B × val(resto(d))
![Page 126: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/126.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Aritmetica de numeros grandes
Representacion de numeros
Se elige B > 1 (la base de numeracion).
n se representa mediante sucesion d = [d0, . . . , dk ]:
0 ≤ di < B para cada i .n =
∑ki=0 di × B i .
(Sucesion vacıa: ∅ → representa a 0.)
Valor a partir de la representacion
val(d ,B) =. si (d = ∅) 0. sino d0 + B × val(resto(d))
![Page 127: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/127.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Aritmetica de numeros grandes
Representacion a partir del valor
rep(n,B) =
. si (n = 0) ∅
. sino
. . (c , r) := cr(n,B)
. . [r , rep(c ,B)]
val(rep(n,B),B) = n
rep(val(d ,B),B) = d salvo dıgitos 0 no significativos.
¿Operaciones entre numeros dados por representaciones?
Implementar algoritmos en base a representaciones.
Se supone accesibilidad a las tablas de operaciones entredıgitos.
![Page 128: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/128.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Aritmetica de numeros grandes
Representacion a partir del valor
rep(n,B) =. si (n = 0) ∅
. sino
. . (c , r) := cr(n,B)
. . [r , rep(c ,B)]
val(rep(n,B),B) = n
rep(val(d ,B),B) = d salvo dıgitos 0 no significativos.
¿Operaciones entre numeros dados por representaciones?
Implementar algoritmos en base a representaciones.
Se supone accesibilidad a las tablas de operaciones entredıgitos.
![Page 129: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/129.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Aritmetica de numeros grandes
Representacion a partir del valor
rep(n,B) =. si (n = 0) ∅. sino. . (c , r) := cr(n,B)
. . [r , rep(c ,B)]
val(rep(n,B),B) = n
rep(val(d ,B),B) = d salvo dıgitos 0 no significativos.
¿Operaciones entre numeros dados por representaciones?
Implementar algoritmos en base a representaciones.
Se supone accesibilidad a las tablas de operaciones entredıgitos.
![Page 130: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/130.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Aritmetica de numeros grandes
Representacion a partir del valor
rep(n,B) =. si (n = 0) ∅. sino. . (c , r) := cr(n,B). . [r , rep(c ,B)]
val(rep(n,B),B) = n
rep(val(d ,B),B) = d salvo dıgitos 0 no significativos.
¿Operaciones entre numeros dados por representaciones?
Implementar algoritmos en base a representaciones.
Se supone accesibilidad a las tablas de operaciones entredıgitos.
![Page 131: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/131.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Aritmetica de numeros grandes
Representacion a partir del valor
rep(n,B) =. si (n = 0) ∅. sino. . (c , r) := cr(n,B). . [r , rep(c ,B)]
val(rep(n,B),B) = n
rep(val(d ,B),B) = d salvo dıgitos 0 no significativos.
¿Operaciones entre numeros dados por representaciones?
Implementar algoritmos en base a representaciones.
Se supone accesibilidad a las tablas de operaciones entredıgitos.
![Page 132: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/132.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Aritmetica de numeros grandes
Representacion a partir del valor
rep(n,B) =. si (n = 0) ∅. sino. . (c , r) := cr(n,B). . [r , rep(c ,B)]
val(rep(n,B),B) = n
rep(val(d ,B),B) = d salvo dıgitos 0 no significativos.
¿Operaciones entre numeros dados por representaciones?
Implementar algoritmos en base a representaciones.
Se supone accesibilidad a las tablas de operaciones entredıgitos.
![Page 133: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/133.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Aritmetica de numeros grandes
Representacion a partir del valor
rep(n,B) =. si (n = 0) ∅. sino. . (c , r) := cr(n,B). . [r , rep(c ,B)]
val(rep(n,B),B) = n
rep(val(d ,B),B) = d salvo dıgitos 0 no significativos.
¿Operaciones entre numeros dados por representaciones?
Implementar algoritmos en base a representaciones.
Se supone accesibilidad a las tablas de operaciones entredıgitos.
![Page 134: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/134.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Aritmetica de numeros grandes
Representacion a partir del valor
rep(n,B) =. si (n = 0) ∅. sino. . (c , r) := cr(n,B). . [r , rep(c ,B)]
val(rep(n,B),B) = n
rep(val(d ,B),B) = d salvo dıgitos 0 no significativos.
¿Operaciones entre numeros dados por representaciones?
Implementar algoritmos en base a representaciones.
Se supone accesibilidad a las tablas de operaciones entredıgitos.
![Page 135: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/135.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Suma a partir de representaciones
d + e = suma(d , e, 0)
dondesuma(d , e, c) =. si (d = ∅) si (c = 0) e sino aumentar(e). sino. . si (e = ∅) si (c = 0) d sino aumentar(d). . sino. . . si (d0 + e0 + c < B) [d0 + e0 + c , suma(resto(d), resto(e), 0)]. . . sino [d0 + e0 + c − B, suma(resto(d), resto(e), 1)]dondeaumentar(d) =. si (d = ∅) [1]. sino. . si (d0 < B − 1) [d0 + 1, resto(d)]. . sino [0, aumentar(resto(d))]
![Page 136: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/136.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Suma a partir de representaciones
d + e = suma(d , e, 0)dondesuma(d , e, c) =
. si (d = ∅) si (c = 0) e sino aumentar(e)
. sino
. . si (e = ∅) si (c = 0) d sino aumentar(d)
. . sino
. . . si (d0 + e0 + c < B) [d0 + e0 + c , suma(resto(d), resto(e), 0)]
. . . sino [d0 + e0 + c − B, suma(resto(d), resto(e), 1)]dondeaumentar(d) =. si (d = ∅) [1]. sino. . si (d0 < B − 1) [d0 + 1, resto(d)]. . sino [0, aumentar(resto(d))]
![Page 137: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/137.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Suma a partir de representaciones
d + e = suma(d , e, 0)dondesuma(d , e, c) =. si (d = ∅) si (c = 0) e sino aumentar(e)
. sino
. . si (e = ∅) si (c = 0) d sino aumentar(d)
. . sino
. . . si (d0 + e0 + c < B) [d0 + e0 + c , suma(resto(d), resto(e), 0)]
. . . sino [d0 + e0 + c − B, suma(resto(d), resto(e), 1)]dondeaumentar(d) =. si (d = ∅) [1]. sino. . si (d0 < B − 1) [d0 + 1, resto(d)]. . sino [0, aumentar(resto(d))]
![Page 138: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/138.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Suma a partir de representaciones
d + e = suma(d , e, 0)dondesuma(d , e, c) =. si (d = ∅) si (c = 0) e sino aumentar(e). sino. . si (e = ∅) si (c = 0) d sino aumentar(d)
. . sino
. . . si (d0 + e0 + c < B) [d0 + e0 + c , suma(resto(d), resto(e), 0)]
. . . sino [d0 + e0 + c − B, suma(resto(d), resto(e), 1)]dondeaumentar(d) =. si (d = ∅) [1]. sino. . si (d0 < B − 1) [d0 + 1, resto(d)]. . sino [0, aumentar(resto(d))]
![Page 139: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/139.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Suma a partir de representaciones
d + e = suma(d , e, 0)dondesuma(d , e, c) =. si (d = ∅) si (c = 0) e sino aumentar(e). sino. . si (e = ∅) si (c = 0) d sino aumentar(d). . sino. . . si (d0 + e0 + c < B) [d0 + e0 + c , suma(resto(d), resto(e), 0)]
. . . sino [d0 + e0 + c − B, suma(resto(d), resto(e), 1)]dondeaumentar(d) =. si (d = ∅) [1]. sino. . si (d0 < B − 1) [d0 + 1, resto(d)]. . sino [0, aumentar(resto(d))]
![Page 140: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/140.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Suma a partir de representaciones
d + e = suma(d , e, 0)dondesuma(d , e, c) =. si (d = ∅) si (c = 0) e sino aumentar(e). sino. . si (e = ∅) si (c = 0) d sino aumentar(d). . sino. . . si (d0 + e0 + c < B) [d0 + e0 + c , suma(resto(d), resto(e), 0)]. . . sino [d0 + e0 + c − B, suma(resto(d), resto(e), 1)]
dondeaumentar(d) =. si (d = ∅) [1]. sino. . si (d0 < B − 1) [d0 + 1, resto(d)]. . sino [0, aumentar(resto(d))]
![Page 141: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/141.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Suma a partir de representaciones
d + e = suma(d , e, 0)dondesuma(d , e, c) =. si (d = ∅) si (c = 0) e sino aumentar(e). sino. . si (e = ∅) si (c = 0) d sino aumentar(d). . sino. . . si (d0 + e0 + c < B) [d0 + e0 + c , suma(resto(d), resto(e), 0)]. . . sino [d0 + e0 + c − B, suma(resto(d), resto(e), 1)]dondeaumentar(d) =
. si (d = ∅) [1]
. sino
. . si (d0 < B − 1) [d0 + 1, resto(d)]
. . sino [0, aumentar(resto(d))]
![Page 142: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/142.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Suma a partir de representaciones
d + e = suma(d , e, 0)dondesuma(d , e, c) =. si (d = ∅) si (c = 0) e sino aumentar(e). sino. . si (e = ∅) si (c = 0) d sino aumentar(d). . sino. . . si (d0 + e0 + c < B) [d0 + e0 + c , suma(resto(d), resto(e), 0)]. . . sino [d0 + e0 + c − B, suma(resto(d), resto(e), 1)]dondeaumentar(d) =. si (d = ∅) [1]
. sino
. . si (d0 < B − 1) [d0 + 1, resto(d)]
. . sino [0, aumentar(resto(d))]
![Page 143: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/143.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Suma a partir de representaciones
d + e = suma(d , e, 0)dondesuma(d , e, c) =. si (d = ∅) si (c = 0) e sino aumentar(e). sino. . si (e = ∅) si (c = 0) d sino aumentar(d). . sino. . . si (d0 + e0 + c < B) [d0 + e0 + c , suma(resto(d), resto(e), 0)]. . . sino [d0 + e0 + c − B, suma(resto(d), resto(e), 1)]dondeaumentar(d) =. si (d = ∅) [1]. sino. . si (d0 < B − 1) [d0 + 1, resto(d)]
. . sino [0, aumentar(resto(d))]
![Page 144: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/144.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Suma a partir de representaciones
d + e = suma(d , e, 0)dondesuma(d , e, c) =. si (d = ∅) si (c = 0) e sino aumentar(e). sino. . si (e = ∅) si (c = 0) d sino aumentar(d). . sino. . . si (d0 + e0 + c < B) [d0 + e0 + c , suma(resto(d), resto(e), 0)]. . . sino [d0 + e0 + c − B, suma(resto(d), resto(e), 1)]dondeaumentar(d) =. si (d = ∅) [1]. sino. . si (d0 < B − 1) [d0 + 1, resto(d)]. . sino [0, aumentar(resto(d))]
![Page 145: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/145.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Resta
Muy similar → EJERCICIO.
Multiplicacion
No tan similar, pero de todos modos → EJERCICIO.Claves:
Multiplicar por la base equivale a insertar un 0.
Hacer subfuncion que multiplica un dıgito por unasucesion.
La funcion principal:
Hace llamada recursiva conveniente.Multiplica esa respuesta por B.Invoca convenientemente a la subfuncion.Ejecuta la suma correspondiente para obtener el resultado.
![Page 146: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/146.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Resta
Muy similar → EJERCICIO.
Multiplicacion
No tan similar, pero de todos modos → EJERCICIO.
Claves:
Multiplicar por la base equivale a insertar un 0.
Hacer subfuncion que multiplica un dıgito por unasucesion.
La funcion principal:
Hace llamada recursiva conveniente.Multiplica esa respuesta por B.Invoca convenientemente a la subfuncion.Ejecuta la suma correspondiente para obtener el resultado.
![Page 147: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/147.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Resta
Muy similar → EJERCICIO.
Multiplicacion
No tan similar, pero de todos modos → EJERCICIO.Claves:
Multiplicar por la base equivale a insertar un 0.
Hacer subfuncion que multiplica un dıgito por unasucesion.
La funcion principal:
Hace llamada recursiva conveniente.Multiplica esa respuesta por B.Invoca convenientemente a la subfuncion.Ejecuta la suma correspondiente para obtener el resultado.
![Page 148: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/148.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Resta
Muy similar → EJERCICIO.
Multiplicacion
No tan similar, pero de todos modos → EJERCICIO.Claves:
Multiplicar por la base equivale a insertar un 0.
Hacer subfuncion que multiplica un dıgito por unasucesion.
La funcion principal:
Hace llamada recursiva conveniente.Multiplica esa respuesta por B.Invoca convenientemente a la subfuncion.Ejecuta la suma correspondiente para obtener el resultado.
![Page 149: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/149.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Resta
Muy similar → EJERCICIO.
Multiplicacion
No tan similar, pero de todos modos → EJERCICIO.Claves:
Multiplicar por la base equivale a insertar un 0.
Hacer subfuncion que multiplica un dıgito por unasucesion.
La funcion principal:
Hace llamada recursiva conveniente.Multiplica esa respuesta por B.Invoca convenientemente a la subfuncion.Ejecuta la suma correspondiente para obtener el resultado.
![Page 150: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/150.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Resta
Muy similar → EJERCICIO.
Multiplicacion
No tan similar, pero de todos modos → EJERCICIO.Claves:
Multiplicar por la base equivale a insertar un 0.
Hacer subfuncion que multiplica un dıgito por unasucesion.
La funcion principal:
Hace llamada recursiva conveniente.Multiplica esa respuesta por B.Invoca convenientemente a la subfuncion.Ejecuta la suma correspondiente para obtener el resultado.
![Page 151: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/151.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Resta
Muy similar → EJERCICIO.
Multiplicacion
No tan similar, pero de todos modos → EJERCICIO.Claves:
Multiplicar por la base equivale a insertar un 0.
Hacer subfuncion que multiplica un dıgito por unasucesion.
La funcion principal:
Hace llamada recursiva conveniente.
Multiplica esa respuesta por B.Invoca convenientemente a la subfuncion.Ejecuta la suma correspondiente para obtener el resultado.
![Page 152: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/152.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Resta
Muy similar → EJERCICIO.
Multiplicacion
No tan similar, pero de todos modos → EJERCICIO.Claves:
Multiplicar por la base equivale a insertar un 0.
Hacer subfuncion que multiplica un dıgito por unasucesion.
La funcion principal:
Hace llamada recursiva conveniente.Multiplica esa respuesta por B.
Invoca convenientemente a la subfuncion.Ejecuta la suma correspondiente para obtener el resultado.
![Page 153: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/153.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Resta
Muy similar → EJERCICIO.
Multiplicacion
No tan similar, pero de todos modos → EJERCICIO.Claves:
Multiplicar por la base equivale a insertar un 0.
Hacer subfuncion que multiplica un dıgito por unasucesion.
La funcion principal:
Hace llamada recursiva conveniente.Multiplica esa respuesta por B.Invoca convenientemente a la subfuncion.
Ejecuta la suma correspondiente para obtener el resultado.
![Page 154: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/154.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Resta
Muy similar → EJERCICIO.
Multiplicacion
No tan similar, pero de todos modos → EJERCICIO.Claves:
Multiplicar por la base equivale a insertar un 0.
Hacer subfuncion que multiplica un dıgito por unasucesion.
La funcion principal:
Hace llamada recursiva conveniente.Multiplica esa respuesta por B.Invoca convenientemente a la subfuncion.Ejecuta la suma correspondiente para obtener el resultado.
![Page 155: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/155.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Division a partir de representaciones
crB(d , e,B) =
. si (d < e) (∅, d)
. sino
. . (c , r) := crB(d , [0, e],B)
. . (c1, r1) := cr(r , e)
. . ([0, c] + c1, r1)
¿Como saber si d < e?
si (d = ∅). si (e = ∅) NO sino SIsino. si (e = ∅) NO. sino. . si (resto(d) < resto( ¡OPS! Falta Espacio → EJERCICIO
![Page 156: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/156.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Division a partir de representaciones
crB(d , e,B) =. si (d < e) (∅, d)
. sino
. . (c , r) := crB(d , [0, e],B)
. . (c1, r1) := cr(r , e)
. . ([0, c] + c1, r1)
¿Como saber si d < e?
si (d = ∅). si (e = ∅) NO sino SIsino. si (e = ∅) NO. sino. . si (resto(d) < resto( ¡OPS! Falta Espacio → EJERCICIO
![Page 157: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/157.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Division a partir de representaciones
crB(d , e,B) =. si (d < e) (∅, d). sino. . (c , r) := crB(d , [0, e],B)
. . (c1, r1) := cr(r , e)
. . ([0, c] + c1, r1)
¿Como saber si d < e?
si (d = ∅). si (e = ∅) NO sino SIsino. si (e = ∅) NO. sino. . si (resto(d) < resto( ¡OPS! Falta Espacio → EJERCICIO
![Page 158: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/158.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Division a partir de representaciones
crB(d , e,B) =. si (d < e) (∅, d). sino. . (c , r) := crB(d , [0, e],B). . (c1, r1) := cr(r , e)
. . ([0, c] + c1, r1)
¿Como saber si d < e?
si (d = ∅). si (e = ∅) NO sino SIsino. si (e = ∅) NO. sino. . si (resto(d) < resto( ¡OPS! Falta Espacio → EJERCICIO
![Page 159: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/159.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Division a partir de representaciones
crB(d , e,B) =. si (d < e) (∅, d). sino. . (c , r) := crB(d , [0, e],B). . (c1, r1) := cr(r , e). . ([0, c] + c1, r1)
¿Como saber si d < e?
si (d = ∅)
. si (e = ∅) NO sino SIsino. si (e = ∅) NO. sino. . si (resto(d) < resto( ¡OPS! Falta Espacio → EJERCICIO
![Page 160: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/160.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Division a partir de representaciones
crB(d , e,B) =. si (d < e) (∅, d). sino. . (c , r) := crB(d , [0, e],B). . (c1, r1) := cr(r , e). . ([0, c] + c1, r1)
¿Como saber si d < e?
si (d = ∅). si (e = ∅) NO sino SI
sino. si (e = ∅) NO. sino. . si (resto(d) < resto( ¡OPS! Falta Espacio → EJERCICIO
![Page 161: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/161.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Division a partir de representaciones
crB(d , e,B) =. si (d < e) (∅, d). sino. . (c , r) := crB(d , [0, e],B). . (c1, r1) := cr(r , e). . ([0, c] + c1, r1)
¿Como saber si d < e?
si (d = ∅). si (e = ∅) NO sino SIsino. si (e = ∅) NO
. sino
. . si (resto(d) < resto( ¡OPS! Falta Espacio → EJERCICIO
![Page 162: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/162.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Division a partir de representaciones
crB(d , e,B) =. si (d < e) (∅, d). sino. . (c , r) := crB(d , [0, e],B). . (c1, r1) := cr(r , e). . ([0, c] + c1, r1)
¿Como saber si d < e?
si (d = ∅). si (e = ∅) NO sino SIsino. si (e = ∅) NO. sino
. . si (resto(d) < resto( ¡OPS! Falta Espacio → EJERCICIO
![Page 163: Cap. 2: TEOR IA DE NUMEROS (II)€¦ · Polinomios sobre cuerpos Divisi on de polinomios Existencia de elementos primitivos M as sobre primalidad Primos de Mersenne Algoritmo AKS](https://reader034.vdocumento.com/reader034/viewer/2022043001/5f7c5cac7d297d2ed87c99f4/html5/thumbnails/163.jpg)
TEORIA DENUMEROS
Cuerpos
Polinomios sobrecuerpos
Division depolinomios
Existencia deelementosprimitivos
Mas sobreprimalidad
Primos deMersenne
Algoritmo AKS
Criptografıa
El metodo deRabin
El metodo RSA
Aritmetica denumerosgrandes
Representaciones
Operaciones
Operaciones
Division a partir de representaciones
crB(d , e,B) =. si (d < e) (∅, d). sino. . (c , r) := crB(d , [0, e],B). . (c1, r1) := cr(r , e). . ([0, c] + c1, r1)
¿Como saber si d < e?
si (d = ∅). si (e = ∅) NO sino SIsino. si (e = ∅) NO. sino. . si (resto(d) < resto( ¡OPS! Falta Espacio → EJERCICIO