notasaritmmod

NOTAS SOBRE ARITMTICA MODULAR BSICA

ANDRS VILLAVECES - BASADO PARCIALMENTE EN LAURITZEN

Las siguientes notas (esquelticas, por ahora) ilustran conexiones (profundas)entre los siguientes temas: Nmeros naturales Nmeros enteros. Cifrado y descifrado1. Congruencias y teoremas de Gau. Algoritmo de Euclides. Teorema chino del residuo. Primos grandes y RSA.

En esta primera versin sigo de cerca el estilo de presentacin de Niels Lau-ritzen (Concrete Abstract Algebra [1] - un libro para cursos de lgebra Abstractaque arranca con un captulo de teora de nmeros bsica como motivacin para laTeora de Grupos). Sin embargo, estas notas seguirn evolucionando ms all dela conexin con Lauritzen.

1. Las bases1.1. Construccin. Z (N N)/ donde (a, b) (c, d) si y solo si a + d =b+ c. La relacin binaria es de equivalencia, y es compatible con + y en N.

Ver detalles en [2, Cap. 6].Teorema 1.1. Sea d Z con d > 0. Dado x Z existe un nico resto r N talque

x = qd+ r

con q Z y 0 r < d.1.2. Congruencias. Gau, Disquisitiones Arithmeticae.Denicin 1.2. a b mod c si y solo si c | b a.

Dado c, la relacin la relacin binaria a y b son congruentes mdulo c es deequivalencia.Proposicin 1.3. Dado c Z, c > 0,

(1) a [a]c mod c,(2) a b mod c si y solo si [a]c = [b]c1respectivamente, encryption y decryption en ingls - en espaol es frecuente el par de anglicismos (incorrectos) en-

criptacin y decriptacin1

2 ANDRS VILLAVECES - BASADO PARCIALMENTE EN LAURITZEN

Proposicin 1.4. Si x y mod d y z z mod d entonces x+ z y+w mod d yxz yw mod d.Corolario 1.5. Dados x, y Z, [xy] = [[x][y]].

Ejemplo inmediato: el resto de dividir 132010 por 4 es 1.

1.3. Cuadrados repetidos. Un ejemplo de lo anterior: 1211 mod 21. Escriba 11 en base 2 11 = 23 + 21 + 20. Use el corolario 1.5 para lograr [1211] = [1223+21+20 ] = [122312212] =[[122

3][122][12]].

Note que [121] = 12,[122] = 18,[122

2] = [(122)2] = [[122][122]] = [18 18] = [3 3] = 9,

[1223] = [(122

2)2] = [[122

2][122

2]] = [9 9] = 18.

Concluya: [1211] = [[1223 ][122][12]] = [[18 18] 12] = [9 12] = 3.El punto clave siempre es

[a2n

] = [(a2n1

)2] = [[a2n1

][a2n1

]].

2. RSA (1)Al enviar mensajes por internet uno mantener la privacidad. Como cualquier

mensaje debe pasar por servidores intermedios, los mensajes deben ir cifrados...pero deben ser descifrados a la llegada. Es posible que si E enva y R recibe el men-saje (cifrado), E pueda darle una clave, tambin por internet, a R para descifrarel mensaje?

Obviamente, no tiene sentido que E enve directamente la clave - sta podraser interceptada y se perdera completamente el secreto del mensaje. Sin embargo,curiosamente, una idea matemtica permite lo anterior: existen funciones de sen-tido nico f(X).

De X a f(X) es fcil ir de f(X) es MUY difcil2 regresar de f(X) a X.

Ejemplo 2.1. Fije un natural N y sea f : Z/N Z/N dada por (X) = [X3], donde[Y] denota el resto de la divisin por N.

X 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14f(X) 0 1 8 12 4 5 6 13 2 9 10 11 3 7 14

SiN fuera ahora un nmero enorme, calcular X a partir de f(X) se vuelve suma-mente difcil.

En el caso anterior la informacin clave es que f(f(X)) = X.

2la medida exacta de esta complejidad es un rea importante de la teora de la recursin en lgica matemtica y de lateora de la computacin

NOTAS SOBRE ARITMTICA MODULAR BSICA 3

2.0.1. Detalles. R debe calcular dos primos gigantescos p y q y formarN = pq. Laidea es que R consigue (usando los primos que conoce p y q) un par de nmerose y d (encrypter, decrypter). Slo da a conocer al pblico los nmeros N y e. Sialguien quiere enviarle un mensaje secreto puede usar la funcin f(X) = [Xe] (Ydenota aqu el resto de divisin porN). Cuando llega un mensaje f(X), R lo descifra(obtiene X) usando su funcin secreta g(X) = [Xd]... pues estas fueron armadas demanera tal que g(f(X)) = X. En el ejemplo anterior p = 3, q = 5,N = 15, e =3, d = 3. Lo clave es lograr (dados N = pq) un par de nmeros e y d tales que

[[Xe]d] = X

y obviamente lograr esto de tal manera que conociendoN y e solamente sea suma-mente difcil encontrar d.

3. Euclides, BzoutProposicin 3.1. Dadosm,n Z, se tiene

(1) mcd(m, 0) = m,(2) mcd(m,n) = mcd(m qn,n).

Ver ejemplo en [2]. Desenredndolo obtenemos el siguiente hecho suprema-mente til.

Teorema 3.2 (Identidad de Bzout). Dadosm,n Z, existen , Z tales quem+ n = mcd(m,n).

En particular, si a, b Z son relativamente primos (es decir, si mcd(a, b) = 1),se tiene que existen , tales que a+ b = 1.Demostracin ver [2].

Corolario 3.3. Sean a, b, c Z. Entonces(1) Si a | bc y adems a y b son relativamente primos, entonces a | c.(2) Si a y b son rel. primos, a | c y b | c, entonces ab | c.(3) Si a y b son rel. primos y adems a y c son rel. primos, entonces a y bc

son rel. primos.

La demostracin usa que a y b son relativamente primos si y solo existen y tales que a+ b = 1. As, multiplicando por c obtenemos

ac+ bc = c.

Pero a | bc; por lo tanto a divide el lado izquierdo y as, tambin a | c. Las otrasdos se demuestran de manera similar.


4. El teorema chino del residuoEl acertijo del 30 (que vemos en clase) tiene como eje el teorema chino del

residuo, o (equivalentemente, pero escrito de manera ms compacta) el isomor-smo (de anillos) del residuo

r : Z/30 Z/2 Z/3 Z/5dado por

r([X]30) = ([X]2, [X]3, [X]5)

De manera ms general, si n1, n2, ..., nk son relativamente primos, y N = n1 n2 nk entonces

r : Z/N Z/n1 Z/nkdado por

r([X]N) = ([X]n1 , , [X]nk)es un isomorsmo.Demostracin Es un ejercicio ver que r es un homomorsmo de grupos. Cal-culamos ker(r). Si X ker(r) entonces r(X) = ([0]n1 , , [0]nk), es decir n1 |X, , nk | X. Por 3.3 (iterado k veces) tenemos que N = n1 n2 nk | X, esdecir [X]N = [0]N. Con esto, concluimos que r es un homomorsmo inyectivo.Ahora, como el dominio y el recorrido son nitos y del mismo cardinal (N), r debeser una funcin biyectiva tambin, y concluimos que r es un isomorsmo.

Como r es un isomorsmo, al tener la informacin ([X]2, [X]3, [X]5) se tiene queexiste un nico elemento de Z/30 cuyos residuos al dividir por 2, por 3 y por 5sean los dados.

Una manera ms clsica de expresar lo anterior es la siguiente3

Teorema 4.1 (Teorema chino del residuo - TChR). Suponga queN = n1 n2 nk,donde n1, , nk Z \ {0} son relativamente primos dos a dos. Considere elsistema de congruencias

X a1 mod n1X a2 mod n2

...X ak mod nk

para a1, ..., ak Z. Entonces(1) El sistema tiene alguna solucin X Z.(2) Si X, Y Z son soluciones del sistema entonces X Y mod N. Si X es

solucin del sistema y Y X entonces Y tambin es solucin.3El estudiante debe revisar que el isomorsmo anterior y el Teorema Chino son equivalentes. Hay sin embargo una

sutileza que emerge en la demostracin del TChR: en la prueba del isomorsmo usamos un argumento general de cardi-nalidad para demostrar la sobreyectividad de r - en la prueba del TChR exhibimos explcitamente la solucin X - lo cualcorresponde a calcular explcitamente r1(X) - algo que la demostracin anterior no nos da!


Demostracin Primero probamos (2): si X, Y son soluciones del sistema, X aj mod nj y Y aj mod nj, para j = 1, ..., k. Entonces X Y mod nj. Esto es,nj | XY; como losnj son dos a dos relativamente primos, por el lema 3.3 tenemosque N | X Y, es decir X Y mod N. Por otro lado, si X Y mod N entoncesclaramente X Y mod nj para j = 1, ..., k, es decir Y tambin es solucin.Demostramos ahora (1):

(1) Los nmeros nj y N/nj son relativamente primos, para j = 1, ..., k.(2) Por lo tanto, por la identidad de Bzout, existen j, j Z tales que

1n1 + 1N/n1 = 1,

2n2 + 2N/n2 = 1,

...knk + kN/nk = 1.

(3) Con esto, si Aj = j(N/nj) para j = 1, ..., k entonces se tiene que

Aj {1 mod nj0 mod ni si i 6= j.

Pero con esto, es fcil vericar queX = a1A1 + + akAk

es solucin al sistema.

5. El teorema de Euler5.1. La funcin de Euler. Sean

(Z/N) := {X Z/N | mcd(X,N) = 1}.y

: N N : (N) = |(Z/N)|.La funcin cuenta el nmero de naturales primos relativos con N menores

que N. Se llama la funcin de Euler. Aunque uno puede fcilmente dar algunosvalores de , en general es un problema muy difcil calcularla4.

Sin embargo, algunos casos sencillos se tienen.

Proposicin 5.1. Seanm y n nmeros naturales relativamente primos. Entonces(mn) = (m)(n).

Demostracin(1) Sea N = mn. Por TChR, como m y n relativamente primos, sabemos quer : Z/N Z/m Z/n es una biyeccin.

4Ms an: si usted pudiera encontrar una manera efectiva de calcular la funcin de Euler, usted volvera obsoleto elsistema de cifrado RSA!


(2) Basta ver que

r((Z/N)) = (Z/m) (Z/n).[Por qu?] Es decir, hay que ver quemcd(X,N) = 1 si y solo simcd([X]m,m) =1 = mcd([X]n, n).

(3) Por Euclides, mcd(a, c) = mcd(c, [a]c), para a, c Z con c > 0. En-tonces mcd([X]m,m) = 1 = mcd([X]n, n) si y solo si mcd(X,m) = 1 =mcd(X,n). Pero esto sucede si y solo si mcd(X,mn) = 1.

Teorema 5.2 (Euler). Dados a, n enteros relativamente primos, n N, se tienea(n) 1 mod n.

Demostracin Ms adelante en Teora de Grupos, una de las aplicaciones queusted estudiar al inicio del curso es justamente una demostracin de este teo-rema de Euler (usando conteo de clases laterales). Sin embargo, podemos dar unademostracin distinta de esa.

Sea a1 < a2 < < a(n) la lista de todos los elementos de (Z/n) (o sea, lalista de los elementos entre 0 y n 1 que son primos relativos con n).

Armacin 5.3. Los conjuntos {a1, ..., a(n)} y {[aa1], ..., [aa(n)]} son iguales.

Demostracin de la Armacin 5.3 - En efecto, basta ver que si ai 6= aj en-tonces [aai] 6= [aaj], y que todo [aai] es relativamente primo con n. Esto es su-ciente, pues lo primero muestra que no hay repeticiones en la lista {[aa1], ..., [aa(n)]}y lo segundo muestra que todo [aai] est en la lista {a1, ..., a(n)}.Si [aai] = [aaj] entonces aai aaj mod n; por lo tanto, n | aai aaj =a(ai aj). Pero como mcd(n, a) = 1, podemos concluir que n | ai aj. Comoestos nmeros son positivos y menores que n, la nica posibilidad es ai = aj.Ahora vericamos que todo [aai] es relativamente primo conn. Comomcd(a, n) =1 y mcd(ai, n) = 1, por la identidad de Bzout existen enteros 1, 2, 1, 2 talesque

1a+ 1n = 1

y2ai + 2n = 1.

Multiplicando a ambos lados, obtenemos

12aai + (2ai1 + 1a2 + 12n)n = 1.

Pero esto implica (ejercicio) que mcd(aai, n) = 1. Af. 5.3Ahora podemos terminar la demostracin de Euler: como los dos conjuntos

{a1, ..., a(n)} y {[aa1], ..., [aa(n)]} son iguales, sus productorias lo son, con locual (tomando residuos mdulo n),


[a1 a(n)] = [[aa1] [aa(n)]] = [aa1 aa(n)] = [a(n)a1 a(n)] =[a(n)][a1 a(n)]. Pero entonces,

[a(n)] = 1,

es decir, a(n) 1 mod n. Teorema 5.25.2. Ms propiedades de los primos.Lema 5.4. Todo nmero natural n es producto de nmeros primos.Demostracin Por induccin, vista en clase.

El siguiente teorema de Euclides es muy bsico en toda la matemtica, y a la vezla demostracin es impresionante5.Teorema 5.5 (Euclides). Existen innitos nmeros primos.Demostracin Suponga que existe una lista nita de todos los nmeros primos

p1, p2, . . . , pn.

Ahora arme el nmero naturalN = p1 pn+1. Por el lema, existe un nmeroprimo p que divide aN; sin embargo, p no puede estar en la lista anterior (pues aldividir N por cualquiera de los primos de la lista el residuo es 1). As, la lista noera exhaustiva. Contradiccin. 5.3. Factorizacin nica. Aparentemente, la unicidad de factorizaciones de nat-urales (es decir, si p1 p2 pr, q1 q2 qs son primos yp1p2 pr = q1q2 qs entonces las dos sucesiones de primos son iguales) fueusada sin demostracin durante siglos, pero Gau en Disquisitiones Arithmeticaehizo la pregunta explcita.Lema 5.6. Si p es primo y p | ab entonces p | a o p | b.Demostracin Si p - a entonces mcd(p, a) = 1 y por lo tanto p | b. Similar sip - b. Teorema 5.7. Todo natural distinto de 0 y 1 se puede factorizar de manera nicacomo producto de primos (mdulo el orden de los factores):

n = p1 ps.Demostracin Suponga que n = p1p2 pr = q1q2 qs.

(1) Sin prdida de generalidad, podemos suponer que no aparece ningn pj allado derecho (si esto no es as, dividimos a ambos lados).

(2) Podemos suponer que r 1 y s > 1.(3) Como p1 | n, por el lema (aplicado s1 veces) tenemos que p1 | q1 o p1 | q2

o ... o p1 | qs. Si p1 | qj es porque son iguales (al ser primos). Contradiccin.5Existen muchas demostraciones diferentes de la original de Euclides, todas muy distintas entre s. Por ejemplo, uno

puede demostrar que 12+ 1

3+ 1

5+ 1

7+ 1

11+ es innita, lo cual implica que existen innitos primos.


6. De vuelta a RSA6.1. Entender RSA ahora s. Ahora podemos entender mejor RSA. Quien quiererecibir un mensaje cifrado debe hacer pblicos dos nmeros N y e. El nmero N(la clave pblica) es el producto de dos primos distintos p y q. Si alguien quiereenviar el nmero X (0 X < N), lo enva cifrado como [Xe]. El receptor puededescifrar el mensaje pues conoce el nmero secreto d con el cual [[Xe]d] = X(residuos mdulo N).

Cmo construir e y d?(1) Note que [[Xe]d] = [Xed] = X si y solo si X Xed mod N.(2) Sabemos que (N) = (p)(q) = (p 1)(q 1).(3) La clave de todo est aqu:

Proposicin 6.1. Sean X un entero y k un natural. Entonces

Xk(p1)(q1)+1 X mod N.[Demostracin Basta ver queXk(p1)(q1)+1 X mod p yXk(p1)(q1)+1

X mod q, pues N = pq y p 6= q. Probamos la primera. Si p | X entoncesse tiene claramente la armacin. Si p - X entonces mcd(p, X) = 1. Por lotanto, por el teorema de Euler, X(p) = Xp1 1 mod p. Usando congru-encias,

Xk(p1)(q1) (Xp1)k(q1) 1 mod p.Multiplicando por X a ambos lados obtenemos Xk(p1)(q1)+1 X mod p.]

(4) Escogemos e (el exponente de cifrado) como algn natural relativamenteprimo con (N) = (p 1)(q 1). Despus de escoger e calculamos d.

(5) Como e y (p 1)(q 1) son rel. primos, existen y enteros tales que(p 1)(q 1) + e = 1.

Podemos tomar spdg 0 < < (p 1)(q 1) [Por qu?]. Entonces < 0.Escogemos d = y k = .

(6) La escogencia anterior sirve: se tiene que k(p 1)(q 1) + 1 = de. Por lotanto,

[[Xe]d] = [Xed] = [Xk(p1)(q1)+1] = X.

El gran secreto est oculto en (N) = (p 1)(q 1): si uno puede calcular(N) y le dan una clave de cifrado e, puede calcular una clave de descifrado dusando el algoritmo de Euclides. Sin embargo, calcular (N) es al menos tandifcil como factorizar N.

Queda pendiente una cuestin prctica: la clave pblicaN debe ser el productode dos primos enormes p y q para que sea realmente difcil de descifrar (debentener por lo menos 100 dgitos cada uno). Cmo encuentra uno primos as degrandes?


7. Primos grandes7.1. El pequeo teorema de Fermat, pseudoprimos.

Tout nombre premier mesure infailliblement une des puissancesmoins un de quelque progression que ce soit, et lexposant de ladite puissance est sous-multiple du nombre premier donn moinsun ... Et cette proposition est le plus souvent vraie en toutes pro-gressions et en tous nombres premiers; de quoi je vous envoieroisla dmonstration, si je napprhendois dtre trop long

Carta de Pierre de Fermat a Frnicle de Bessy, 1640.En ese fragmento leemos por primera vez el resultado que ya conocemos (en su

forma ms general de Euler):Teorema 7.1 (Pequeo teorema de Fermat). Sean p primo y a entero, tales que(a, p) = 1. Entonces

ap1 1 mod p.Generar primos grandes es un problema natural en cifrado RSA (y en muchos

otros temas).Compare las dos situaciones siguientes: 55 5 6= 1 mod 6. (Por qu? Use congruencias arrancando de 5 1 mod 6.) 88 (1)8 = 1 mod 9.

En ambos casos el formato es similar al del pequeo teorema de Fermat (PTF:ar1 1 mod r)... excepto que en este caso r no es primo. En el primer casopodemos concluir inmediatamente que 6 no es primo (pues falla la consecuenciadel PTF), pero en el segundo caso, aunque sabemos que 9 no es primo, an se tienela consecuencia del PTF. En cierto sentido que 6 es no-primo de manera ms fcilde ver que en el caso de 9. Obviamente, para nmeros tan bajos como 6 o 9 laprimalidad o no-primalidad no requiere estas cuentas, pero imagnese la situacinsi le dan un nmeroM grande y le piden averiguar si es primo o no. Si no pasa eltest del PTF, es fcil ver que no es primo.Denicin 7.2. Sean N un nmero natural compuesto y a un entero. Se dice queN es un pseudoprimo con respecto a la base a si aN1 1 mod N.

Note que para que N pueda ser pseudoprimo con respecto a la base a, a deentrada tiene que ser primo relativo con N.Denicin 7.3 (Nmeros de Carmichael). Un nmero de CarmichaelN es un nmeroque es pseudoprimo con respecto a toda base relativamente prima.

Por ejemplo, N = 561 = 3 11 17 es un nmero de Carmichael. En 1994 sedemostr que existen innitos nmeros de Carmichael.

Los pseudoprimos son entonces nmeros que no son primos, pero que pasan eltest del pequeo teorema de Fermat (con respecto a la base de pseudoprimalidad).


7.2. Ms ltros de primalidad - Teorema de Rabin. Un segundo ltro lo dael siguiente lema.

Lema 7.4. Sean p un nmero primo y x Z. Si x2 1 mod p entonces x 1 mod p.

La demostracin es inmediata: si p | x2 1 = (x 1)(x+ 1), entonces p | x 1o p | x+ 1 (verique por qu).

Un ejemplo de un nmero (argumento en cadena) que no pasa este test es N =341. 2340 1 mod 341. [Aqu vale la pena usar cuadrados repetidos - haga elargumento para clase.] De modo que o bien 341 es primo o bien 341 esun pseudoprimo con respecto a la base 2. An no sabemos. Por el lema anterior, si 341 fuera primo, deberamos tener que2170 1 mod 341. Veamos si 341 pasa este segundo chequeo. Y s, se puede calcular que 2170 1 mod 341. Ejercicio: calcule esto con

cuadrados repetidos. Pero entonces no se puede an concluir nada. Sinembargo, usando que (285)2 = 2170, podemos continuar aplicando el lema. Si 341 es primo, podramos concluir que 285 1 mod 341. Pero NO:

tenemos que 285 32 mod 341, con lo cual 285 6 1 mod 341. AhoraS podemos concluir que 341 no es primo... y claro que es entonces unpseudoprimo con respecto a la base 2.

Denicin 7.5 (Pseudoprimos fuertes). Un nmero compuesto imparN es un pseu-doprimo fuerte con respecto a la base a si o bien aq 1 mod N o existe i {0, , k 1} tal que

a2iq 1 mod N,

donde N 1 = 2kq y 2 no divide a q.

Estos pseudoprimos fuertes son por lo tanto los nmeros compuestos que pasanlos dos chequeos de primalidad - son nmeros compuestos que no son tan fcilesde sealar como no primos.

Michael Rabin tiene el siguiente resultado importante que muestra el contrasteentre los pseudoprimos fuertes y los pseudoprimos con base a.

Teorema 7.6 (Rabin). Suponga que N > 4 es un entero compuesto impar, y sea Bel nmero de bases a (1 < a < N) con respecto a las cuales N es pseudoprimofuerte. Entonces

B < (N)/4 (N 1)/4.Hay por lo tanto muchas bases a que muestran que un nmero compuesto no es

primo: al menos 34

del punto de arranque. Leyendo el mismo resultado en direccincontra-recproca, obtenemos que si un nmero es pseudoprimo fuerte, resultaque en realidad es compuesto... en < 1

4de los casos. Especicamos la idea aqu:


7.2.1. Tests de primalidad, de nuevo. Suponga que le dan un nmero naturalN y un a escogido al azar entre 2 yN 1. SiN es compuesto impar, entonces la probabilidad de queN sea unpseudoprimo con respecto a a es < 1

4por el teorema de Rabin.

Suponga ahora que tiene un buen mtodo para generar nmeros aleato-rios distribuidos uniformemente,6 puede intentar con una sucesin de basesaleatorias 1 < a1 < a2 < < am < N. Al nal del da si N es un pseu-doprimo fuerte con respecto a las m bases aleatorias a1, , am entoncesla probabilidad de que N sea compuesto es menor a(

1

4

)m.

De hecho esa probabilidad suele ser mucho menor. Si un nmero p tienealrededor de 600 bits (180 dgitos), y se sabe que p es pseudoprimo conrespecto a una base, entonces la probabilidad de que p sea compuesto esmenor que ( 1

2)76.

Dice Lauritzen, citando a Knuth, que ya para m 30 la estimacin burda( 14)m es comparable con la probabilidad de que un rayo csmico genere un

error de hardware en su computador. As que un nmero que sea pseudo-primo fuerte con respecto a ms de 30 bases aleatorias lo podemos tomarcomo primo para efectos prcticos (con nuestro computador no podremosdeterminar que no lo es).

7.3. La distribucin de los primos. La historia del estudio de la distribucin delos nmeros primos es antigua. En estos ltimos das (noviembre de 2013) hanpasado cosas interesantes. Resumo los enunciados, pero doy los enlaces por siquieren revisar ms.

Teorema 7.7 (Maynard). (Anunciado el 19 de noviembre de 2013.) H1 600. Hm Cm3e4m, para cualquierm 1 y para una constante absoluta C.

Adicionalmente, suponiendo otras conjeturas, Maynard reduce las cotas Hm demanera dramtica.

Qu quiere decir sto?Primero que todo, la denicin: Hm es la mnima cantidad tal que existe una

cantidad innita de intervalos de longitud Hm que contienen al menos m + 1primos. Formalmente,

Hm := lim infn pn+m pn

donde pn denota el n-simo primo.

6Este es otro problema difcil. Aparentemente, el ruido atmosfrico de ondas de radio es una buena fuente de aleato-riedad. http://www.random.org tiene mucho ms sobre este problema.


Dicho de manera cruda, si usted escoge un nmerom, habr innitos clustersacotados conm+ 1 primos.

La famosa conjetura antigua de los primos gemelos tiene que ver conH1: por elteorema de Maynard, hay innitos intervalos de longitud 600 dentro de los cualeshay al menos dos primos. El salto de longitud 600, aunque puede parecer altocomparado con el nmero 2, es bajsimo si se piensa que clusters de longitud 600con al menos 2 primos ocurren innitas veces.

El esfuerzo ha sido colaborativo - adems de James Maynard, los nombres deYitang Zhang y el famoso medallista Fields Terence Tao juegan un papel crucialen la bsqueda de prime gaps.

Ver ms detalles (y una descripcin por Tao de la prueba de Maynard) en estosdos enlaces:

https://www.simonsfoundation.org/quanta/20131119-together-and-alone-closing-the-prime-gap/

http://terrytao.wordpress.com/2013/11/19/polymath8b-bounded-intervals-with-many-primes-after-maynard/

8. Factorizar, de nuevoRomper el cifrado RSA se puede si uno tiene algoritmos efectivos para factor-

izacin en primos. En 2009 el nmero RSA-768 (1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413) fue factorizado.Los autores de esta factorizacin cuentan en su artculo de 22 pginas cmo lo-graron factorizarlo, qu algoritmos usaron, etc. (http://eprint.iacr.org/2010/006.pdf)

Los nmeros ms difciles de factorizar son los de la formaN = pq, producto dedos primos. SiN es un nmero grande, los primos p y q pueden ser muy grandestambin, y los algoritmos publicados hasta ahora funcionan hasta poco ms de100 dgitos - aparentemente, lo mejor hasta la fecha (publicado) es el algoritmoGNFS (great number eld sieve - o gran criba del campo de nmeros), de tiempode ejecucin O(e( 649 b)

13 (log b)

23 ).

La bsqueda, si el nmero es impar, recorre en principio hastaN nmeros

(criba). Es increblemente lento el procedimiento: si N tiene 100 dgitos y es pro-ducto de dos nmeros de 50 dgitos, hay que hacer aproximadamente 1050 pasospara la criba antes de encontrar la factorizacin. Si cada paso toma 1010 segun-dos, hay que esperar 1040 segundos (o sea, aproximadamente 1032 aos) antes deencontrar el factor primo.

8.1. Cumpleaos, y dePollard. Recuerde el famoso problema del cumpleaos:si hay por los menos 23 personas en un saln, la probabilidad de que dos de esaspersonas cumplan el mismo da es 50%. Veamos por qu.


Piense en el problema inverso: dadasN personas, calcule la probabilidad P(N)de que ningn par de ellas cumplan el mismo da. As, por ejemplo, P(1) = 1,P(2) = 364

365(pues dado el cumpleaos del primero, quedan 364 fechas para el

segundo si queremos que tenga cumpleaos distinto), P(3) = 364365 363365

, etc. Engeneral,

P(N) =365 364 (365N+ 1)

365N.

Claramente, esto es decreciente. SiN = 23, la probabilidad P(N) ya es menor que0, 5. Por lo tanto, si hay 23 personas en un saln, la probabilidad de que dos deellas compartan cumpleaos es ya ms que 50%. Si hay 50 personas, dos compartencumpleaos con probabilidad 97%.

Abstrayendo, la idea es hacer muestreo con reemplazo de un espacio muestraldeN objetos. El nmero promedio de muestras antes de que ocurra una repeticinse puede calcular como el valor medio de una variable estocstica. Cuando N esgrande, ese valor es cercano a

piN

2.

8.1.1. El algoritmo de Pollard. Pollard mejora la velocidad, con su algoritmo (llamado as por la forma de la repeticin de nmeros que aparecen).

Suponga que p es un primo que divide aN y nos dan dos nmeros 0 a, b < Ncon a b mod p. Entonces 1 < mcd(a b,N) N y si a 6= b, mcd(a b,N)es un factor no trivial de N.

Suponga que generamos enteros aleatorios X1, X2, con 0 Xi < N. Porideas anlogas al problema del cumpleaos, vemos en promedio

piN2

nmerosaleatorios antes de que se repita alguno. Para efectos de factorizacin, es sucientecon tener una repeticin mdulo p, donde p es el mnimo primo que divide a N:si Xi Xj mod p, entonces 1 < mcd(Xi Xj, N) N. El conteo se reduceentonces a enteros aleatorios X1, X2, mdulo p. Vemos entonces en promedio

pip2

nmeros aleatorios antes de que se repita alguno.La funcin siguiente aproximams o menos decentemente el problema de generar

nmeros verdaderamente aleatorios.7

f : Z/N Z/N : X 7 [X2 + 1]N.Arranque con X0 := 0 y dena Xi+1 := f(Xi).Lema 8.1. Si f :MM es una funcin conM nito, sea x0 M y genera la suce-sin x0, x1, x2, con xi+1 = f(xi) para i 0. Entonces existen i, j N tales quei 6= j y xi = xj. Adems, existe n > 0 tal que xn = x2n. La sucesin y0, y1, y2, dada por y0 = x0 y yi+1 = f(f(yi)) es igual a la sucesin x0, x2, x4, .

7Como hemos discutido en clase, el problema de generar nmeros verdaderamente aleatorios esmuy difcil. Ver una discusin muy reciente, e interesante, de John Baez, sobre el tema, aqu:https://plus.google.com/117663015413546257905/posts/9HeN1sSQztA.


Armamos ahora s el algoritmo basndonos en reconocer repeticin m-dulo p. Lo clave es que tenemos repeticin mdulo p de la forma Xn X2n mod p (por el lema). Sean X0 = Y0 = 0. Iteramos Xi+1 = f((Xi) y Yi+1 = f(f((Yi)), usando la

funcin f(X) = [X2 + 1]N. Calculamos d = mcd(Yi+1 Xi+1, N) usando el algoritmo de Euclides. Sid = 1 o d = N, repetimos el proceso. Si no, d tiene que ser un factor notrivial de N y acabamos.

Este algoritmo de Pollard requiere en promedio 4N pasos para factorizar un

entero N... bastante menos que losN pasos de la criba usual.

9. Ejercicios(1) Sea n N \ {0}, con factorizacin prima

n = pe11 pemm ,con pi 6= pj si i 6= j. Sean d(n) = |div(n)| y

(n) =

ddiv(n)d

respectivamente el nmero de divisores de n y la suma de los divisores ded.(a) Demuestre que d(n) = (e1 + 1) (em + 1).(b) Demuestre que

(n) =pe1+11 1

p1 1 p

em+1m 1

pm 1.

(2) Un nmero n es perfecto si (n) = 2n... es decir, si es igual a la suma desus divisores menos l mismo. Demuestre que si 2n+11 es primo, entonces2n(2n+1 1) es perfecto.

(3) Use GIMPS (http://mersenne.org/) y su computador para encontrar un nmeroperfecto con ms de un milln de dgitos.

(4) Demuestre que el quinto nmero de Fermat F5 = 232 + 1 es compuesto(Euler, 1739) usando las siguientes pistas: 54 + 24 = 1+ 27 5 F5 = (54 + 24)(27)4 54(27)4 + 1.

(5) Suponga queN = pq es producto de dos primos distintos p y q. Demuestreque p y q son soluciones de la ecuacin

X2 + ((N) N 1)X+N = 0.

Concluya que (dadoN = pq), factorizarN es exactamente igual de difcila encontrar (N).


(6) Este ejercicio (difcil) muestra por qu hay que cambiar N en RSA conmucha frecuencia.Suponga que le dan e, d,N en el contexto de RSA. Vamos a deducir de estostres datos la factorizacin prima de N = pq.(a) Demuestre que la congruencia x2 1 mod N tiene cuatro soluciones

mdulo N (o sea, hay dos fuera de las triviales x = 1).(b) Demuestre que una de estas soluciones satisface x 1 mod p y

x 1 mod p. Cmo se puede usar sto para encontrar p de man-era efectiva?

(c) Usando que (N) es par, deduzca un algoritmo probabilstico efectivopara encontrar p y q dados e, d,N (usted ya sabe que (N) | ed 1 yque a(N) 1 mod N si (a,N) = 1).

(d) Concluya que no es seguro usar el mismo N para gente distinta en elsistema RSA.

(7) Demuestre que 899 es compuesto usando exclusivamente el pequeo teo-rema de Fermat.

(8) Demuestre que 15 no es pseudoprimo fuerte con respecto a 11.(9) Demuestre que 25 es pseudoprimo fuerte con respecto a 7.

(10) Sea n = p1 pr producto de primos distintos. Suponga que pi | n 1,para i = 1, , r.(a) Demuestre que an1 1 mod n si (a, n) = 1.(b) Demuestre que 561 es un nmero de Carmichael.

(11) Use el algoritmo de Pollard para factorizar N = 143. Use el algoritmo de Pollard para factorizar N = 10403.

References1. Niels Lauritzen - Concrete Abstract Algebra. From Numbers to Grbner Bases. Cambridge University Press. 2003.2. Fernando Zalamea - Fundamentos de Matemticas - Universidad Nacional. 2008.

1. Las bases1.1. Construccin1.2. Congruencias1.3. Cuadrados repetidos

2. RSA (1)3. Euclides, Bzout4. El teorema chino del residuo5. El teorema de Euler5.1. La funcin de Euler5.2. Ms propiedades de los primos5.3. Factorizacin nica

6. De vuelta a RSA 6.1. Entender RSA ahora s

7. Primos grandes7.1. El pequeo teorema de Fermat, pseudoprimos7.2. Ms filtros de primalidad - Teorema de Rabin7.3. La distribucin de los primos

8. Factorizar, de nuevo8.1. Cumpleaos, y de Pollard

9. EjerciciosReferences

Documents

notasaritmmod