Cursotan20141

Introducci´on a la teor´ıa algor´ıtmica de n´umeros
Oswaldo Vel´asquez
Facultad de Ciencias
Universidad Nacional de Ingenier´ıa
2014-I

Contenido
1 Preliminares
1.1 N´
umeros enteros . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Complejidad computacional . . . . . . . . . . . . . . . . . .
1.3 Aritm´etica Ilimitada . . . . . . . . . . . . . . . . . . . . . .
1.4 El M´
aximo Com´
un Divisor. . . . . . . . . . . . . . . . . .
1.5 Congruencias . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.1 Relaciones de equivalencia . . . . . . . . . . . . . . .
1.5.2 Definici´
on y propiedades de las congruencias . . . .
1.5.3 La funci´
on ϕ de Euler y el Teorema Chino del Resto
1.5.4 Congruencias lineales . . . . . . . . . . . . . . . . .
1.5.5 Aritm´etica modular . . . . . . . . . . . .. . . . . .
1.6 Grupos abelianos . . . . . . . . . . . . . . . . . . . . . . . .
1.6.1 Propiedades b´
asicas . . . . . . . . . . . . . . . . . .
1.6.2 Grupos cocientes . . . . . . . . . . . . . . . . . . . .
1.6.3 Homomorfismos . . . . . . . . . . . . . . . . . . . . .
1.7 Anillos e Ideales . . . . . . . . . . . . . . . . . . . . . . . .
1.8 Anillos de Polinomios . . . . . . . . . . . . . . . . .. . . .
1.9 Campos finitos . . . . . . . . . . . . . . . . . . . . . . . . .
1.10 Restos cuadr´
aticos . . . . . . . . . . . . . . . . . . . . . . .
1.11 Ra´ıces primitivas . . . . . . . . . . . . . . . . . . . . . . . .
1.12 Fracciones Continuas . . . . . . . . . . . . . . . . . . . . . .
1.13 Sobre la densidad de los n´
umeros primos . . . . . . . . . . .
1.14 N´
umeros aleatorios . . . . . . .. . . . . . . . . . . . . . . .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.3
3
4
7
8
13
13
14
15
17
18
18
18
22
23
25
29
32
32
38
40
46
48

2 Detectando n´
umeros compuestos
2.1 Un primer intento . . . . . . . . . . . . . . . . .
2.2 N´
umeros de Carmichael . . . . . . . . . . . . . .
2.3 Test de Miller-Rabin . . . . . . . . . . . . . . . .
2.4 La Hip´
otesis de Riemann Extendida . . . . . . .
2.5 Test de Solovay-Strassen . . . . . . . . . . . . . .
2.6 Pseudoprimos deLucas y de Fibonacci . . . . . .
2.7 Test de Grantham-Frobenius . . . . . . . . . . .
2.8 Implementaci´
on de los tests de Lucas y Frobenius
3 Verificando primalidad de n´
umeros
3.1 El test de Pocklington-Lehmer . .
3.1.1 N´
umeros de Fermat . . . .
3.2 El test n − 1 . . . . . . . . . . . .
3.3 El test n + 1 . . . . . . . . . . . .
3.3.1 El test de Lucas . . . . . .
3.3.2 N´
umeros de Mersenne . ..

de
. .
. .
. .
. .
. .
. .

forma
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .

1

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
..
.
.
.
.
.

.
.
.
.
.
.
.
.

50
50
50
53
55
56
57
60
61

especial
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

64
64
65
66...