evaluacion informe de investigacion

1

UNIVERSIDAD NACIONAL DE LA LIBERTAD
Facultad de Ciencias F´
ısicas y Matem´ticas
a
Departamento de Inform´tica
a

´
Algebra universal para la Ciencia de la
Computaci´n: Aplicaci´n a la Criptograf´
o
o
ıa

Jos´ A. Rodr´
e
ıguez Melquiades

Teresa Bracamonte Nole

MsC. Ciencia de la Computaci´n
o

Ing. Inform´tico
a

Trujillo - PERU
2009

2

Prefacio

´Indice general
1. Introducci´n a la criptograf´
o
ıa
1.1. Evoluci´n historica de la criptograf´ . . . . . . . .
o
ıa
1.1.1. Criptograf´ cl´sica . . . . . . . . . . . . . .
ıa a
1.1.2. Criptograf´ moderna . . . . . . . . . . . .
ıa
1.2. Elementos participantes en un modelo criptogr´fico
a
1.2.1. Entidades . . . . . . . . . . . . . . . . . . .
1.2.2. Escenario b´sico . . . . . . . . . . . .. . .
a
1.2.3. Criptosistema sim´trico . . . . . . . . . . .
e
1.2.4. Criptosistema asim´trico . . . . . . . . . . .
e
1.3. Investigadores que han aportado a la criptograf´ .
ıa
1.3.1. Antes del siglo XX . . . . . . . . . . . . . .
1.3.2. Durante las guerras mundiales . . . . . . .
1.3.3. Creadores de algoritmos sim´tricos . . . . .
e
1.3.4. Creadores de algoritmos asim´tricos . . . .e
1.4. Ejercicios . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
..
.
.
.
.
.

7
8
8
9
11
11
11
13
14
15
15
16
16
16
17

2. Algoritmos y Complejidad computacional
2.1. Algoritmos . . . . . . . . . . . . . . . . . . . . . .
2.2. Complejidad computacional . . . . . . . . . . . . .
2.2.1. An´lisis de algoritmos . . . . . . . . . . . .
a
2.2.2. Formalizaci´n del an´lisis de los algoritmos
o
a
2.2.3. Clases de problemas . . . . . . .. . . . . .
2.2.4. Complejidad computacional con enteros . .
2.3. Ejercicios . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

19
19
21
22
23
26
28
31

3. Teor´ de n´ meros
ıa
u
3.1. Qu´ es la teor´ den´meros . . . . . .
e
ıa
u
3.2. Divisibilidad . . . . . . . . . . . . . . .
3.3. MCD, MCM y N´meros primos . . . .
u
3.3.1. M´ximo com´n divisor (mcd) .
a
u
3.3.2. M´
ınimo com´n m´ltiplo (mcm)
u
u
3.3.3. N´meros primos . . . . . . . .
u
3.4. Congruencia . . . . . . . . . . . . . . .
3.5. Enteros modulo n: Zn . . . . . . . . .
3.5.1. Operaciones en Zn . . . . . . .
3.5.2. Grupomultiplicativo . . . . . .
3.6. Funci´n de Euler φ . . . . . . . . . . .
o
3.7. Problema de factorizaci´n entera . . .
o

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
..
.
.
.
.
.
.
.
.

33
33
35
36
37
40
40
45
48
48
50
51
52

3

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

´
INDICE GENERAL

4

3.7.1.Factorizaci´n de prop´sito especial . . . . . . .
o
o
3.7.2. Factorizaci´n de prop´sito general . . . . . . .
o
o
3.8. Residuo cuadr´tico . . . . . . . . . . . . . . . . . . . .
a
3.8.1. Residuo cuadr´tico y residuo no cuadr´tico . .
a
a
3.9. Problema de la ra´ cuadrada modulo n . . . . . . . .
ız
3.9.1. Ra´ cuadrada cuando n un n´mero primo . . .
ız
u
3.9.2. Ra´ cuadrada cuando n un...