criptografia
TRANSCRIPT
trllatemáticasdtscreüasnnmóru ESPTNoSAARMENTA
AAHaomega
68 II. TEoRiA DE NúMERos
e\r'
Teor€m*2.7 Sean a y b dos.entercs positivos, y sea d ]a conbinación linealpositiva mínima de a y b. Entohces d = mcd.(a, b).
Demosüasión Sea d = tzx + ¿y la co[üinación linea] positiva mínima dea y b . Por eI algorilmo de la division :
a = d q + r 9 o n 0 3 r < d '
Por lo tanto
r = a - dq = a - lax + by)q = (l - xq)a + (-qy)b
De aquÍ que r es una combinación lineü de a y b. No puede ser gue 0 < r, yague r < d, por Io tanto r = O con Io cual se concluye gue d divid€ a a. En formaanáIoga se puede ver que d drvlde a b, por lo tanto d es un diviso¡ común dea y ,. supóngase ahora que c es otro divisor común de a y á. Se obserya que
c divide a d (pues d es u¡a combinación lineal de 4 y r)' de ahí que c es menoro igual a d.
El siguiente teorema describe un procedimiento para determÍnar el máximo comúndivisor de dos enteros Poslt¡vos.
Teorena 2.8 (A¡goritmo de Eucl¡d6sl. Sean 4 y b dos entercs positivos
tales queq> b Se definen16=ay rt = b, y aplicando repetidamente el algo'ritmo de la división se obtiene
t 'o = rtQl' l rz
rt = rzq|+ 13
i,-r=,,--,n^-, * '^rn) = rnqn+ t
"+l
O < r 2 1 1 1
o < 7 < r z
Q < rn< rn-1
0 = rn+r
MArEMÁTrcAs D¡scRETAs - RAMóN EsrINosA ABMENTA
Entonces mcd(4, b) = rn, esto es, el riJtimo ¡esiduo es distinto de cero.
ATFAOMEGA
Eucl¡des(33G275 a.c)
L, t"-" a" Eucliales se clgbe a sumonumental obra Elell,le¡tos qu6 conBtade 13lib¡os gué contieaen ios fu¡dahen'tog y todo el sale¡ mai,smático hasta ésetieúpo. Apart€ de su coútonido, laestructu¡a lógica de esta obra ha ir¡lluido€n el pensamionto matemá¡ico y científi_co más clug ningur¡a otra.
Especiccamente el conteÑdo de losnementoa es el qiguiente: libros 1 a 4,geomeüia plana: Iib¡os 5 a 10, fazones yprcporcioDesi üb¡os 11 a 13, geom€t¡iade sólidos.
En relación con la teotia de número6,en eI libro 7 se uatan los teoas d€ divisjbilidad, ¡úrneros priúos, algo¡ltroode Euclides, máximo común divisor yminimo común mL tiplo, adeEás de guelas proposicior¡es 30 y 32 juntas son
esoncialmente equl-valentes ai teolemafundamental de Iaaritméhca; en el lrbroI se presenta el temads las proporc¡onésetr teoria da ml.Be'ros; i¡alúér¡ie etr ellibro 9 se deqtueslrala oxisténcia de iú-lidad de ¡il¡néros P!i-mos (proposicló¡ 20)y se ltrantea l,a cons-t¡ucc$D dé lc,s nút!e.ros pe¡fectos pat98(proposicióú 36).
2.5 MÁxrMo coMúN DrvrsoR
Demostración Pdmero se demuest¡a que
mcd(rj, ri+t) = mcd(rj+r'rj+2)
para todaj= 0, l, ..., n - 1. Sea c un divisor común de r¡ v ¡j + L Como
rj= rj+t4j+t * ri*z
se sigue que l+2 = rj - rj+gj+t, y de aquÍ que c divide a rj+z. por 10 tanto c esun divisor.común de r¡+t y rj+2.Análogamente, todo divisor común de r¡1 V,12 es un divÍsor común de rj y r,+r, con Io cual se concluye que /lcnf(r,, ru,) =ntcd(r¡*1, r¡+).Por Io tanto ncd(a, b) = ntcd(ro. r1) = mccl(r., r) = .., =tncd(t ,,. 0\ = r,1.
Ejemplo 2,16 Determinar el.máximo común divisor de 126v 78.
Solución Aplicando el algoritmo de Euclides se obtiene que
1 2 ó = 7 8 ( l ) + 4 87 8 = 4 8 ( l ) + 3 04 8 = 3 0 ( l ) + 1 8 .3 0 = 1 8 ( l ) + 1 21 8 = 1 2 ( l ) + 6tz= 6(2)
Por lo fanto mcd(12ó, 78) = 6.
El ¡lgoritmo de Euclidedtambien puede utilizarse para expresar el maxrmo comundilisor de dos números como combinación titeal de eüos, como se muestra en elsr!luiente ejemplo.
69
E 6mplo 2,17 Expresar el máximo común divisor de 126 y 78 como combinaciónlineal de dichos números.
Soluc¡ón A partir del ejempio a¡terior se tiene que
r M¡¡e¡¡¡rrc¡s DIscFETAs - RAMóN Esp¡NosA ARMENTA
tALFAOMEGA
70 II. Tsonre o¡ l,,rulu{snos
E¡emplo 2,la Mostrar que r¡?¿d(5 n+3,3n+ 2) = l,p¿ra cualquiórnumero natural ¡?.
Soluclón Aplicando el algoritmo de Euclides se tiene gue
5n + 3 = (3n + 2)(1) + (2n + ll3 n - 2 = ( 2 n + l x l r + ( r + l )
2 r + 1 = ( n + l X l ) + nr + l = r ( l ) + t
n = t(n)
Por lo tanto el m cd(5tt + 3,3tt + 7) = \,
Dados dos enteros positivos 4 y á, el propós¡to general del simula-dor
MAXIMO COMUN DIVISOR
es determ¡nar el nxcd de éstos uti l izando el algoritmo de Euclidesexpuesto en esta secc¡ón.
T€orema 2,9 Seana, b yc tes enteros. Simcd(a,b)= | ya]bc, entoncesa l r .
Demostración Si ncd(a, b) = I entonces existen x, ) enteros, tales que
a x + b ! = 1
de aquÍ que
a(xc)+(bc)J=c
Es decir, c es combinación linea.l de a y bc. Como a I a y a I lt. se sigue que ¿? ..
Dos ente¡os ¿r y ó se dice que son primos relativos si r,?cd(4, ü) - 1. g1 resultadoanterior es falso si a y á no son primos relativos, por ejemplo, 6 divide a 2(9) pero
n o a 2 , y 6 n o d i v Í d e a 9 .
En el siglo UI d. C., et matemático gdego Diofanto consideró el problema de obtenersoluciones entefas de ecuaciones con coeficientes enteros. Este tipo de ecuaclonesson conocidas en la actualidad como ecuaciones diofantinas. El signrienie teoremaesta.blece una condición necesada y suficiente para que una ecuación lineal dio'fa¡tina en dos variabies tenga soluciÓn.
MATEMÁTIcAs DIscBETAs - RAMóN EsPtNosA ARMENTAALFAOMEGA
Dlofanto(2O{}284)
f:rlln su obra,Ari¿,'r¡¡¡o¡rca {que const€bad€ 13 li¡ros de los cualeg só¡o se coúser-van 6), Diofa¡to expo¡o lás ü6madasecuacio¡ros auofa¡tLnas; eje@plos deéstas ¡on las sioulentes:
, ar].b!=l (ocuación liné¿.I dio-fantina)
. / '+l '=1 (paran=2 soti€re elteorema de Pitágo¡a¡rypa¡an>2elüt imoteoroma de Fetmat)
. ¡t - ¿y'= il (€cuac,ión ds Péü)
4 1 1 1. -= :+ :+ : ( l a con jenua d€ E r
n x Y z dós'straus establocegue para todo ente¡opositivo n > 2 eristsuna solución con¡, ),z lodos enrcro9 posr_[rvosJ
Un hecho sencillo y sin e¡¡bargo üáscen-dent€ es que en 1637 Fermat esc!üió snel ma¡gen de su copia de A'jtlrúeücalogue se conoce como el último teoreúa d€Fermat, qlre en térmi¡os modertroi dice
Si x es un número enie¡o mayor que2, entonc€s no existen números ente_
rosd ,áycd j s t i ¡ t osde 0 tales que cum-plan Ia igualdad
Etn esp€cial los esfuBr-zos por clemost'af sst6teorema eslütruaronel deEa¡tollo de Ia !60-rfa de los númeroF al-g€b¡aicos,
2.5 MÁxrMo coMúN DrvrsoR 7t
Teorema 2.lO Sean a y b d.os entercs no ambos cerc, y sea d = mcd.(a, b).\n::!y:
).a,lcuación qx + by = c tiene sotuciones entens siy sólo siilí.Aaemas st d. I c y x = xo, y = yo es una solución pafiicu)ar de la ecuacion, en_tonces todas las soluciones están dadas por
x = xo+ (btd)n y = yo_ @td)n
donde n es malquier número enterc,
Demostración Sean x, y dos enteros tales gue ax + by = c. eomo d I a yd lá, se signre que d I c. por Io tanto, para gue la ecuacién tenga solucronesenteras es necesario que d divida a c. Supóngase ahora que d I c, es decir,c = dq para algnrn entero q. Como d. = tncd(4, á), se sigxe dá rcorema 2.7 queexÍsten enteros s,, tales que d = as + át, de aquí que c = dq = asq + btq, porlo tanto r0 = sq y yo = t4 es una solución particular de lá ecuación. Seanx = xo + (bld)n, y = yo- @/d)n, donde n es un número entero. por lo tan¡o
ax + by = oco+ a(blün + by¡- b(ald)n = al!¡+. bys= ¿
Ahora se verá gue toda solución de la ecuación debe ser de la forma descfi-ta en el teorema. Sean r, y dos enteros tales gue 4.r + á) = c. Como tambiénaxo+ byo= c, se s¡gue gue
a(x -xú+b6 / -yd=0
y de aguí gue
(a/d)(x - xg = (b/d)(y¡ - y)
Qomo mcd(ald, b/d) = 1 1y6u"" problema 2.29), se sign¡e de Ia proposiciónantedor gue
rad)l\o - y)
por lo tanto existe u¡ entero ¿ tal que 0/0 -, = n(a/d),y de aqui se sigxe quey = yo- @ld)n. Sustituyendo en la ecuación se tiene que
(a/ d)(x. - xg = (b/ d)n(at d)
Por lo tanto (r -,r0) = (bld)n, es deci, x = xo+ (b/d)n.
E omFlo 2.19
toJx+ lAYy=99
MA?EMÁT¡CAS DIscRETAs - RA¡¡óN EspINosA ARMENTA ALFAOMEGA
72 I I . TEORTA DE NUMERoS
Soluclón.B;UClrües:
765 =.189(4) + 91 8 9 = 9 ( 2 1 ) + 0
Por 10 tanto d = m cd(765, 189) = 9. como d i 99, Ia ecuación tiene.solución. Además, como 765 - 4(189) = 9 se tiene que 765(11)'+189(-44) =99, de modo que;6 = 11, yo = -44 st una solución par-tisutar. Además, por el teorema arterior, todas las soluciones de laecuación son de la forma:
x = 1 1 + Z L n J = 4 4 - 8 5 n
En general, una ecuación diofantina es una ecuación de Ia forma
D ( x r , . . . , ¡ , , )
donde D es un polinomio con coeficientes enteros. En 1900 el matemático alemán
David Hilberi presentó una lista de 23 problemas que consideraba cruciales para
el desaüollo de las matemáticas deL siglo xx, en particular el problema 10 consistÍa
en diseñar un mélodo para determinar en un número flnito de pasos si una ecuación
diofantina tiene soluciones enteras o no. Finalmente, en 1970 se demosiró que tal
método no existe.
En la lectura adicional
LOS PFOBLEMAS DE HILBEFT
se describen algunos de los problemas propuestos por este célebrematemático en el Segundo Congreso Internacional de Matemáti-cos.
Por otro lado, es posible extender la definlción de máximo común divisor de la siguiente manera: si {a 1, 42. . . ., a,, } es un conjunto de enteros' donde ¡1 > 3, entonces
el máximo común divisor de a¡. a2, ..., .J,, se def,ne como
Por ejemplo:
mcd(a1, a2, . . . , an) = nlcd(at, mcd(u¡ ct2, . . . , a "))
mcd(6, 1. 12) = ncd(6, ¡ttcd(4, l2)) = n¡cd(6, 4) = 2
4 Tom M. Aposroti I¡t¡o(luc.tiotl to analytic numbe¡ rreo¡yi Springer Verlag, New York 1976i p. 306.
MATEMÁTrcAs D¡scRETAs - RAMóN ESPINoSA ABMENTA
Hllbert y la teor¡aoe numeros
T:T-Úl matematico alemán Davicl Hiliren11862"1943) es considerado uno de losmatemáticos más imponantes dg toalosIos tiempos debido aI descub¡imionto ydesarrollo de muchas ideas fundamenta-lss €n varias áreas de la ÍnataÍDátÍca, enparticular formuló la teola de los espa'cios de Hilbert (uno d6 los fuDdaúentosd6l análisis funcional), aceptó y dofendióco$ vehemencla la teoria de conjuntós ylos números iransff¡¡rtos de Geotg€ Cen-tor, y en el congEeso de úatemáticos d61900 presentó una colecció¡ da proble-mas que de6¡ió el cu¡so de Ia mayo¡ pat-te de la i¡westigación mat€úráticá dglslglo xx.
En la ieoia de números Hilbert uniñcóel campo de la teo¡ia de números álge_braicos con sn tÉtado Za nbeticht do 1897y resoirió el Ua¡rádo problema de Wa¡i¡rg.
''Problema de WaJing. Determi¡ar sipara ün entero positivo k, existe u¡l€nte.ro s (que dep€nda sólo de ¿) tal que la
tenga soluciones para cada, > L
El p¡oblema se co-noce con e] nom¡redel matemático rnglésE. Wañng qu€ esta'bleció en 17?0 (sindemosüación y conlimiiada evidencia nu-mérica) que cada ñ €sla suma de 4 cuadra-dos, d6 I cubos, de'19 cualtas pot€nclas,etcét€fa"4.
ALFAOMEGA
912 .11 PRoBLEMAS
. ; t : , i i
2.24 Resolver el problema anteior utilizando el simulador
2.26 Resoiver el problema anterior utilizando el simularior
MAXIMO COMI'N DIVISOR
2.27
Mere ¡ ¡ ¡ r r ns D tscn . r ¡ s lR rNaoN Esp rNosA ARMEN-A
::
ALIAOMEGA
92 IL TEoniA DE NúMERos
2.35 Resolver el problema anterior utilizando ei simulador
2:36 Determinár el máximo común diviso¡ de 156, 39, -104, :108.
2.37 Resolver el problema antedor utilizando el simulador
MAXIMO COMUN DTVISOR
ALFAOMEGA
2.11 PRoBTEMAs 93
2.45
2.46
2.4?
2.48
2.49
a\ 693
c't 1925
nxcm(q, b).
: : ' 1 "
s i ¿ = 2 s . 5 r ' 1 3 1ncn(a, b).
MAT¡riÁTrcAs DrscRETAs - RAMóN EsplNosA ARMENTA ALTAOMEGA
76 II. Tsonin DE NúMERos
donde p¡, p2,. . ., p, son primos distintos, y 0 < ai,0 < bipan toda.l = l,. .., ,r.Entonces
nlcd(a, b) = pi" p;' '. p':" . y n t (n t lo ,h \= p ' , ' p l ' . p ! '
donde r?; = mínimo {a¡ b) y M,= miy..üno Ioj, b) conj = 1, ..., /r. Por Io tanto
t , t ,d ra .b tn rcn t ta .h t= l p ; p p i ' f ! ¡ , "
= pú¡M p¡r.+M. ,, . pú¡,+M,
= pi.h' p:'+b' " p::-b'
= Pi" p';' " pi pi p';' " ' P'"'
2.1
En 1801 el matemático alemán Carl Gauss introdujo la noción de congruencia, lacual permitió obtener fácilmente resultados relacionados con la divisibilidad.
f
Por ejemplo, 3 = l3 (mód 5) porque 13 - 3 = 5(2). Considerando que n¿ es un enteropositivo arbitrario pero ñjo, a continuación se demuestran algunas propiedades delas congruencras.
Teorema 2.13 Si a. l, y ( son enteros, entonces
(j) ¡¡ = r¡ (uród i¡¡)
(jt sr a = b (mód ¡r) entonces 1, = ¿7 (rnód r?);
(i j i) sia =ó (nród r?!) y b = c (mód r¡) entonces ¿r = c (¡¡ód ¡r¡)
Demostración
(j) Como (a - a¡ = ¡16, se sigue que a = a (mód /fl).
(rl) Si a = 1., (mód ¡??) entonces (b - a) = aq para algún entero 4, y por Iotanta (a - b) = m(-q), de aqui que D = a (mód nr),
(j i i) Sin=ó (mód nt) y b=c (¡nód r?) entonces existen enteros qty q2talesque (b - a) = ¡1q t y (c - b) = tnqz, de aquí que (c - a) = u¡(q t + q2) y porl o t a n t o a = c ( m ó d m ) .
MATEMÁTIcAS DISoRETAS - RAMór'i EspNosA ARMEI'ITA
I€€c
Gauss y la teoríaue numeros
T'\J-,, e ongen alemán Ca¡l Fneüich Gausses considerado "el prjncipe de las ma!e-máiicas asi como "ei oatemá¡ico ¡¡rás€nand6 desde la a¡tigúedad". Ademásde ser un nÍño prodigio, Gauss hizo i¡¡-portantos cont¡jbucioDes en las ár€as d€la teoria de númelos, la estadístÍca, elaDálisis, la geom€t¡ia diferencial, la geo-desia, la geoflsica la electrostáiica, la
En relación con la leoria de números,en 1798 t€¡minó de escribü Disgutsitjo-nes A¡it¡me¡icáe que consolidó y definióIas lineas de desarrollo mode¡nas de estaá¡ea. En térmi¡os geDerales, en esta obraGauss ¡eú¡e y organiza los resultados dela teoria de números obtenidos por Fer-mai, Euler, Lagra¡ge y Legenüe, pre-senta la demostración del teo¡ema fun-damental de la aritmética, hace u¡a claraexposición de la arjtmetica modular y
expone la prrmerdemost¡ación de la leyde reciFocjdad cua-drática la cual esta-blec€ las conalicionespára la solución deecuaciones cuaüáti-cas módu.lo oúñeÍosPr¡mos. En partio¡a¡slguiendo esta Linea der.nvestigación, en un
ALFAOMEGA
2.7 CoNcRUENcrAs
El sign¡iente resultado muestra que las congm¡encias son compatüles con las ope-racÍones ds suna y multiplicac!ón en Z.
Teorema 2.74 Si a, b y c son enteros y a = b (mód m\, entonces
li], (4 + c) = (b + c) (mód ¿¡)
(ii) ac = ¡ (¡¡1(i n1¡.
Demostració¡ Por hipótesis se tiene que existe un entero ?, tal que( b - a ) = a q .
lÍ¡ (b + c) - (a + c) = (b - a) = mq, ps¡ lo tanto (a + c) = (á + c) (mód m).
(ií) bc - ac = clb - a) = m(cq\,es decü ac = Dc (mód m).
En general es falso que r¡na congruencÍa se preserve al dividú ambos lados po! unentero, por ejemplo, 9 = 15 (mód 6), pero 3 no es congruente con 5 módulo 6. Sinembargo, el siguiente resultado proporciona una condición sufrciente para que unacongruencia se preserve al dividir entre un er¡tero.
Teofema 2.15 Si ac = bc (m& m) y d = mcd(c,rn), ento¡ces
a= b (mód ¡nldl.
Demo¡trasión Se tiene que ac = bc (m6d. ¿?) impüca qle mq = cb - ca =c(á - a) pa¡a algrún entero 4, de aqui gue, diüdiendo entIe d = rncd(c,m) satiene gue
(mtd)q=1¿¡¿¡16-o¡
es dec:Lr, (nlÜ | G/d)(b - a). Qomo mcd(nld, c/d) = 1, s¿ sigve det teo¡ema 2.5qre (,nld\ | (á - a) y por lo tanto a = b (mód mtd).
Cotofarlo 2,1 Si ac = bc (mód m) y mcd.(c,m) = I, entonces
a=b(m6dm).
El siguiente resultado muestra que se pueden sumar o multiplicar congruencias.
Teoroma 2,1 6 Si a = á (mód m) y c = d. (m6d, n), antonces
(r) (a + c) = (b + A (m6d m)i
(t0 ac = bd 1¡¡16¿ ^¡.
77
I MATrMÁTtcAs DIscRETAs - RAMóN EsprNosA ARMENTA
LALF'AOMEGA
-.ll
78 II. TEoRiA DE NúMERos
Demostración Por hipótesis existen ente¡os ql y 42, tales que
(b-a)=¡nqt f @'-c)=v¡qt
(r) (b + t¡ - @ + c) = (b - a) + (d - c) = rnqt + mq2= m(q | + 42) y por lo ta¡to(a + c) = (b + d) (m6d m).
(¡t bd - ac = bd. - bc + bc - ac = b(d - c) + c(b - a) = [¡¡q, a ¿mqt = m(bqz +c4r) de aquÍ que 4c =bd (m6d m)'
leoréma 2.17 Si a = b (mód rn) entorzces a^ = b" (mód m) pan cualquierenterc Positivo n.
Demostración Si n = l, eI resultado es cierto por hipÓtesis.
Supóngase que la a-firmación es cierta para /¿, es decir' a" = b" (mód r|1)' comoambién a = á (mód m), entonces se sigme del teorema anterior ql¿e a"a= b"b(mód r¡) y de aguÍ gue annt = b"*t (m6d m).
En el siguiente eiemplo se muestra cómo calcular el residuo al dividir un lmelo
de la forma M", con n g[ande, entre un entero positivo m
Ahora bien
ALFAOMEGA
2.7 CoNGRUENctAs 79
Sea a un entero positivo, que en baEe diez se escribe como
a = a r l V + . . . + a 1 l 0 t + a ¡
Considerando gue l0 = I (mód 9), se sigue del teorema anterior que ld = i (mód 9)y de aguÍ gue arlO* = ar (mód 9) para iodo entero no negatÍvo t. por lo tanto, porel toorema 2.16 resulta que
a = (a.+ ... + a¡ + a6) (mód 9)
Es decir, todo entero positivo es congruente con la suma de sus dígitos módulo nue_ve. Por eiemplo, 4217 = 14 (mód 9) y 14 = 5 (mod 9), de aguÍ que 4217 = 5 (mríd 9).Esta observación permite establecer un procedimiento para verificar que la sumao el producto de dos enteros es cor¡ecta: sumaf los digitos de los números y efec-tuar la operación sobre la suma de los dÍgitos. Por ejemplo,
2153x3t4
676042
Si el productolos dígitos decoüecto.
2 + I + 5 + 3 = I l , 23 + l + 4 = 8 , x 8
6 + 7 + 6 + 0 + 4 + 2 = 2 5 , 2 + 5 = ' 1 , L 6 l + 6 = 7
de la suma de los dÍgdtos no es igual al produsto de la suma dela respuesta, entonces el resultado de la multiplicación no se¡á
a es diuisible enfe3, siy só\o siq,,+ ... .r a1* d¡ es divisihle entrc3.
a es divisible entre 2, si y só|o si aD es divisible entrc ¿.
a es divisible entre 5, si y sdo si ao= 0 o ao= 5.
a es üvisible enlde ll, siy só\o siao- at + ... + (-1), a" es divisible
En el siguiente teorema se pla¡tean vados resütados de divisibüdad.
Teorema 2.18 Sia=anlO' +... +a1l0r + ao entonces
l, a es üvisible enüe 9, si y sólo si an + ... + a.t + ao es divisible entre 9.
(x)
(ix)
(jv)
(rr)ent¡e l l.
Der¡ostració¡
(t) Se sigue del hecho de que a = (a, + ... + c1 + a¡) (mód 9).
MATEMÁT¡CAS D¡scRETAs - RAMóN EsptNosA ABMENTA ALFAOMEGA
80 II. TEoRiA DE NúMERos
(it Como 10 = I (mód 3), se sigue que l0* = I (mód 3) pa¡a todo entero nonsgativo ¿, de aguí que a = (a,r + ... + a¡ + a6) (mód 3).
(ji¡) Como l0 = 0 (mód 2), se sigme cnre ld = 0 (mód 2) para todo enteropositivo ¿, por lo tanto a= a¡ (mód?).
Como l0 = 0 (mód 5), se sigue gue ld = 0 (mód 5) para todo enteropositivo f, de aguÍ gue a = c¡ (rnód 5). Además ¿o = 0 (mód 5), si y sólos i a o = 0 o a o = 5 .
CoBo l0 = -1 (mód I l) se sigrue c¡uo lot = (-1)t (mód 1 1), por lo tantoa= (a¡- a l l . . .+ ( -1) 'a , ) (mód l1) .
Lama 2.3 Sean a y b dos enteros y m un anterc posiüvo' Si mcd(a, m) = |entonces la congzuencla linea)
ax=b(m6dm)
üene solución. Además, si xs es una solución particula4 entonces todas lagsoluciones están d.ad.as por x = xo+ mn, donde n es uJt enterc afuitario.
D€most¡acióD Sa tiene gue a¡ = á (mód r¿) 6i y 8ólo si b - ex = my para algúnentero y. Esta esuación es eguivaletrte a la eo¡aqiÓn lineal diofanti¡a
a x + m y = D
la qual por el teorema 2.10 tiene solución, ya q:e mcd(a, m) = 1. Además, porel mismo teorema, las soluciones son de la fofma r = xo+ tnn, y = yo * an,donde ¡ = )fo, y = )0 es una solución particular y n es sualgu¡er númelo entero.Los valores r = ¡0 + m¡r son las soluciones do la congruencia lineal.
MATEMÁüCAS D¡scRETAs - RA¡.4óN EsP¡NosA ARMENTA
(jv)
(v)
ALFAOMEGA
2.7 CoNcRUENciAs
r (moo /).
81
Sofucfón Coúo mcd(2,7).1, se sigue que la congruencia tiéiresolución. Una solución particular es.r0 = -3. Además cualquie¡ otrasolución es de Ia forma x = -3 + ?n, para algúh éntero n.
Ej€mplo 2¿6 Reso¡ver el sjstema de congruencias lineales:
x= I (mód 3)r = 3 ( m ó d 5 )
9oluclón Para rgsolver este sisteqra se observ4'pnmero gue 4es una solución particular de la primera congruencia, además porel lema anrcrior toda solución de la primera iongruencia lineal esde la forma
x = 4 + 3 k
donde t es un entero arbitrario. Sustituyendo en la segxnda con-gruencia lineal se obtiene gue
( 4 + 3 k ) = 3 ( m ó d 5 )
y de aquÍ gue
3e: -l (mód 5)
Una solución particular de Ia segunda congruencia es 3 y cualquierotra solución es de la forma t = 3 + 5n, donde 11 es cualquier ente.ro. Por lo tanto las soluciones del sistema de congruencias linea]esson de la forma n = 4 + 3(3 + 5¿) = 13+ l5¿.
E¡emp¡o 2,27 En ei siglb m d. C,, el matemático chino Sun Ziesqibió el libro Sun Tzu Suang Chlng (Manual de Matemáticas delMaestro Sun), en dor¡de se presenta¡ üfrersos problemas mate-máticos. En pa¡ticuler el problema 2q dice Io siguiente:
Tenemos un numero de cosás, pero no se sabe cuántasson exagtamente. Si las dividimos entre 3 nos sobran2. Si las dividimos entre 5 nos sobran 3. Si las dividimosentre 7 nos sobrsn 2, ¿Cuánta,6 cosas tenemos?
l\fATEMATrcAs DrscRETAs - FAMóN EsprNosA ARMEN?A AL¡'AOMEGA
82 II. TEoRÍA DE NúMERos
En los ejemplos anieriores cualesquiera dos módulos eran primos relativos, Comose verá, ésta es una condición sunciente para que un sistema de congruencias li-neales con coeñcientes unitarios tenga solución, además de que cualesqu¡era dossoluciones son congruentes módulo el producto de los módulos. Sin embargo, prr-
mero se reguiere demoslrar el signtiente lema.
Lema 2,4 Si my, m2, ..., m,. son entercs, y b es otrc enterc tal que
m c d ( m i , b ) = | P a r a t o d a i = 1 , 2 , . . ' r
entonces mcd(múr2 ... mt, b) = l.
MATEMATToAS DISCRETAS - RAMóN ESPINoSA
Üna solución partisular d€ esta congruencÍa,es 1, además de cualquier otra spluciÓnde la forma É = 1 + 5t. sustituyéndo en la tersera congruencia se obtiene que
Una so¡ución partiqular de esta congruencia es 1 y cualguieJ otra solucion d.e laforma, = 1+?tr . Por lo tanto¡= 8 + 15(1 +7n)=23 + 105n.
ALFAOMEGA ARMENTA
2.7 CoNGRUENCTAS
Demostrac¡ón Sea á un entero arbitrarjo, pero njo. ta demostración se hacepor inducción sobre el número de términos /.
PaIa r = | el resultado se cumple trivialmente. Supóngase ahora gue el re-sultado es verdadero para r, y sean rn l, tnz, ,.,, mú mr+t, enteros tales guemcd(mi, b) = I para ioda i = l, ..., ¡, r + l. Por hipótesis de i¡ducción se tieneqlJe mcd(m1m2... m,, b) = l, por lo tanto existen dos enteros l¡ y 12 talesque
) l1(m1m2 ... m,) + ^2b = |
Por otra parte, como mcd(nr,+|. b) = I entonces existen enteros pl y p2 talesque
I r f i r + t + l z b = l
Multiplicando las dos ecuaciones antedores se obtiene gue
(1,1(m1n2 ... n,.) + L2b)(¡4m,¡ + V2b) = |
n a . d , , i r a c , , l r r ñ , ó
¡t lu (m pt2 ... nt,. m,.* ) + Q¡m,* ],,2 + ),a(m p2 . . m,)¡t2 + 7,"2 ¡t2b) b = |
y, por lo tanto, ,rcd(m1m2 ... nr¡nr¡1, b) = I.
Teorema 2,19 lTeorema ch¡no det reaiduo). Sean nxr m2, ..., nr¡. en-tercs positivos tales que rncd(ntbnt) = | pan toda ¡ +.j. Entonces eJ sjstemade congrue cias lineales
r = á¡ (mód ri ¡)r = D2 (rnód ar2)
:
x = lt,. (m6d m1)
tiene solución única módulo M = mtm2 ,,. nr.
Demostfación Si r = I el resütado se sigue del lema 2.3. Supóngase ahoraque el resultado es cierto para sistemas consistentes de r congTuencias Ii-neales, y considérese un sistema de r+ I congruencÍas lineales. Por hipótesisde inducción, el subsÍstema formado por las primeras r congruencias tieneuna solución panicular i, además de gue cualquier otra solución es de la
MATEMÁTICAS D¡scRETAs - RAMoN Esp¡NosA ARMENTA
83
ALFAOMEGA
84 IL TBonIA DE NúMBRos
forma ¡ = i + ¿¿ doade n 6g u¡t entoro a¡bitra¡io y a = r¿lm2.,. m, Qomo xtaEbiéú debe satisfacer ¡a r tlma congruslcia, s6 ti6na gue
i + an a bn¡(mód a,*¡)
y tt6 aquf que
az = (á¿*¡ - i) (mód mn*¡)
Abora bien, por el lsua 2,4 se sabe qus mcd.(a, mn) - | pq lo que, por 61 lema2.3, osta co[gru€oda d€ne u¡a soludóo particu¡¿r 't0, además de gue cuelquierotfa 60lucióD es de la fottt¡a n = zo + rrN¡¡t¿. Por 10 tanto
x = i + a(no + m*tk) = (i + an¡) + amnlk
De aguí que todas las soluciones del sistema de congruencias soD de lia forma.r = ¡0 + Mk, do¡do M = mtnh ... ¡rrr+l y & es un eotero übitrario,
ED la aDtigÍua Roma sl calendario constaba origi¡alEsnte de diez meses :
o Martius: en bo¡or a Marte.
. Aprüs: dedicado a Venus (Apru oD etrusco).
. Maius: decllcádo a Maya, Eadre de Morcurio.
. fu¿iug: dedicado a Ju¡o.
o Quinülis:. el mes quinio.
r Sextüis: el mes sexto.
. Septamberi el Bas séptimo.
. Oc'tabef: el mes octavo.
. NoveúbeÍ, el meg noveoo.
. D66.emben e¡ me8 déaiso,I
Estos Eesss toDían etr total 304 dÍas, Pa¡a complota¡ el año solar habfa 61 dias d€i¡vier¡o. En el aúo 713 a. C. ol rey Numa Poúpilius aúadió dos nuevos mssas:
MATrUÁTtcA8 D¡scnETAs - RAUóN ESprNosA ARMBNTAALFAOMEGA
94 II. TEoRiA DE NúMERos
2.51 Demostrar qüe sip es primo yP Ia'', entonces p'Ia".
Congruencias
2.52 ¿PaIa qné
2¡53
Calcular el
b) l?.r = 14 (mód 2l)
MATEMÁT1oAs DIscRETAS - RAMoN ESPINoSA ARMENTA
2.50 Resolver el problema anierior utilizando el simulador
MÁXIMO COMUN DIVISOR
AI,FAOMEGA
2 .11 PRoBLEMAS 95
2.64 Resolver el siguie¡¡te sistema de congruencias iineales:
r=5 (módl l )
r = 4 ( m ó d 8 ) .
a)
b)
2.66
2.67
Calendario perpetuo
2.68 Calcular el dla de la semana del 30 de abril de 1777 (nacrrniento deGauss).
ALPAOMEGA
2.69 Resolver el problema anterior uti l izando el simulador
CALENDARIO PERPETUO
MATErrATrcAs DlscR¡TAs - RAMoN EsptNosA ARMENTA
4.8 APLTcACToN:cRtprocRAFiA
E¡emplo 4.39igma.les.
Demo¡t¡aciónobservar gue
Supóngase que se requiere envia¡ información confldencial a través de ciertocanal de comunicación. Ante el desgo de que la información que se envre seainterceptada por otra persona que pueda aprovecharse de ésta en nuesiro per-juicio, se han ideado métodos para t¡ansformar el mensaje original de modo quela información que se envíe esté oculta, y pueda ser encontrada solamentepor la persona a la que se quiere enviar el mensaje. La disciplina que estudiaestos métodos se llama criptografia (del gdego k¡yp¿os, escondido, y gnphein,escribir).
EI mensaje que se quiere enviar se llama texto común, y el mensaje transformadose ilama texto e¡criptado o cifrado. Tanto el texto común como el texto cifradoestán escdtos con símbolos de un alfabeto particular. Al proceso de pasar deltexto común al texto cifrado se Ie Uama encriptar o codiicar, y ai proceso de pasarde teÉo cifrado al texto original se le llama desencriptar o descifrar,
777
Como uno de los d.os p meros factóres es par¡ ss sigue gue n5 - ¿ = 0 (mód 2), porlo tanto n5 - ¡? = 0 (mód l0), lo cual prueba el resultado.
i ' ,t,.l
#.
tlBs,gB!,
F;F,
Ejenrplo 4.¡¡O En Ios mensajes que Julio César enviaba a sus tropas, cada ietradel alfabeto se reemplazaba por la letra que se encontraba tres posÍciones des-pués, suponiendo que éstas estaban en un cÍrculo, de modo que A sequia despuésde Ia Z. Por ejemplo, Ia palabra ATAOUEN se convertía en DWDTXHO. Si pensa-mos que a cada letra de} alfabeto le corresponde un número del I al 26, represen-tando su posición en el alfabeto, sÍ M es el texto común y C es el texto cürado,en¡onces
C=M+3(n6d26)
M¡r¡u¡t¡c¡¡ DlscngtAs - RAMoN EsprNosA ARMENTA ALFAOMEGA
778 IV, GRUPos, ANrrLos Y cAMPos
El receptor del mensaie puede descifrarlo usando la fórmula
M = C - 3 ( m ó d 2 6 )
En este caso el número 3 es Ia clave para enctiptar y desencdptar mensajes. Si dospersonas querÍan comunicarce usando este sistema, ambas debía¡ conocer la cla_ve y evitar que ésta fuera conocida poI terceros.
En un cr¡ptosistema de clavo privada, el emisor y el receptor de un mensaje co-nocen y utilizan Ia misma clave secreta para encdptar y desencdptar el mensaje,respectivamente. EI pdncipal reto consiste en mantener en secreto la clave, Io cuales difícil, especialmente en sistemas abiertos con múltiples usuarios. Por esa ¡azónen 1976 Whitfleld D¡fñe y Martin Hellman2 propusieron una idea radicalmenLenueva en criptogTafía. La idea es la siguiente, supóngase que se pudiera disenarun método de encriptamiento y desencriptamiento de datos, donde la clave deencriptamiento fuera dÍsii¡ta que la clave de desencriptamiento, y que el conoci-miento de una de esas claves no permitiera encontrar la otra. De esta manera, Lubanco, por ejemplo, podrÍa hacer pública la clave de enc¡iptamiento, para poderrecibt mensajes de sus clientes, manteniendo en secreto la clave de desenc¡ipta-miento, asegurándose de que ésta sea prácticamente imposible de descubrü, Unmétodo con estas caracteísticas es llamado un criptosistema de clave pública.En 1977, poco después de que esta idea fuera propuesta, tres jóvenes matemáticosdel MIT, Ronald Rivest, Adi shamir y Leonard Adleman3, dieron un ejemplo con-creto de cómo esta idea podÍa llevarse a Ia práctica. En honor a sus descubridores,el método se conoce como criptos¡stema RSA.
En Io que sigue se supone que cada letra del alfabeto es una pareja denúmeros enteros del 01 al 26. También se utiliza Ia pareja 00 para denotar un es-pacio. Por ejemplo, el mensaje BUENoS DIAS, se puede representar como02210514151900040901 19 .
El método RSA se inicia seleccionando dos números pdmos disti¡tos, p y 4, ambossuicientemente glandes. Sea n = pq, por lo lanlo (p(n) = (p - l)(q - l). Luego rjeellge un entero ¿ > 1 tal qne mcd(e, (p(e)) = 1 y se resuelve la congruencia lineal
ed= I fuódE(n) )
eligiendo d de modo que 0 < d < @(¡1). La pareja de enteros (¿, ,) es la clave pílbljiraque utilizará el emisor para encñplar mensaies y la pareja (d, ¡l ) es Ia clave pdva-
da que uti l izará el receptor para descifrar mensales.
MATEMATTCAS DlscRETAs - RAMo EsprN, sA ARMEI "A
dcd(
'z W Diffle v M. S. Hellma¡, New directions in crwiographf IEEE, Tránsactions i)n InfartDaüon Thea)y'22 tr9?6). 644-654.3 R. Rivest, A. Shami¡, L. Adleman. A úethod for obtaini¡g digital signa¡wes a¡tü public key cliptosys'rems. comm. of ¡he AcM, 21 (1978), 120-126
ALFAOMEGA
e
4.8 ApLrcAcróN:cRrpTocRAFÍA
También se supone que el mensaje que se guiere enviar es un número entre 0 y
Í - l, si no es asÍ el mensajs se puede dividü en blogues de números en ese rango.Si m es el mensaje original, entonces el mensaje cif¡ado C es el residuo obtenidoa.l dividir M" ent¡e n, eguivalentemento, C es la solución d,e la congruencra
W=C(m6dn)
.donde 0 S C < n. Para desciffar el mensajé el receptor calcula el residuo R obteni-do at dividü C entrs ¿, equivalentemente
C = R ( m ó d ¿ )
donde 0 < n < ¿. El siguiente teorema muestra que R = M.
Teolgt|¡a 4.22 Seanp y q dos primos üstintos, n= pq, y e, d enteÍos posíüvos tdes que ed = | (m6d rp(n)). Sio 3 M < n y
W=C(módn)
C = JR (mód n)
donde 0 < R < n entonces R = M.
Demostraclón Porhipótesis
¿d= I (mód (p - lXq - l))
po¡ Io tanto existe un entero positivo /r tal que
De aquÍ gue
e d = l + k ( p - l ) ( q - l )
R = C ( m ó d n )
= (M")d (mód z)
= M"o (mód n)
= Mt+k(t>t)(.t-t) (mód ¿)
. = MMk(F-t)(q-t) (mód ¿)
Como pln, se sigiue que
R _ MMktp_Dk)) (m6d p\
Se aflrma que I = M (mód p). Pa¡a probar esta anlmación se considelan loscasos plM y pI M
D¡scRETAs - I{AMóN EsprNosA ARMENTA
179
ALFAOMEGA
180 IV, Gnupos, ANrLLos Y cAMPos
Caso 1. Si plM entonces M = 0 (mód p), por Io tanto
Mlúktt '-t)\q-t) : 0: M (mód p)
Esdec i r ,R=M(módp) .
Caso 2. Si p ,f M, se sigue del pequeño teorema de Fermat que
M t - t = l ( m ó d , p )
Por lo ta¡to
Mt(r-t)(4-t) = 1k(s-r) = I (mód p)
De aqví MMk(t'-t)kt-r) = M (rnód p) y por 10 iario R = M (mód p). Como 4ln, unargumento similar muestra que R = M (mód 4). Por 10 tanto R es una solucróndel sistema de congruencias lineales
n = M @ 6 d p )
R = M ( m 6 d q )
Como p y 4 son pdmos distintos se iiene q|j.e ncd(p, q) = l, de aguÍ que, por
el teorema chino del residuo R = M (mód n), donde r = ¡:q. Como además0 < M < ¡ x e n t o n c e s R = M .
De acuerdo con lo expuesto en esta sección, el propósito g€neral de los simuladores
. GENERADOR DE CLAVES RSA
. CODIFICADOR FSA
. DECODIFICADOR FSA
respectivamente es gsnerar una clave pública y una privada, y codificar un mensaje ydecodif¡car el mismo usando las claves generadas,
ALTAOMEGA
Elomplo 4.41 Detetminar una pareja de claves en el sistema RSA, usando losP r i m o s P = 7 Y 4 = 1 1 .
Solucló¡ Enestecason=77 yg(n)-60. Un entero mayor que I y primo relativo. . .a 60 es e = 7, por lo que una clave pública es (€, n) = (7,'7?). Pdra determinü laclavep¡ivadacorrespondienteseconsideIalacongruencialineal.
7 d = l O n ó d 6 0 )
la cual tiene solución d = 43. Por Io tanto la.clave pdvada o s (d, n1:: ga,7l¡. l' :
:1, , , . : i : ; .
. , , . ; : ; .1 . ' , : ! i , . ; i t : l : ; . . ; l
MATEMÁT¡CAS DISCRETAS _ RAMÓN ESPINOSA ARMENTA
1814.8 ApLlcAcróN:cRrprocRAFÍA
E¡emplo 4,42 EncrÍptar el mensaje HOLA con ta clave pública(7. 77), usando el sistema RSA.
Soluclón En forma numérica se tiene que
HOI,A = O8151201
gue es un númeto mayor gue r¡ = 77, pór lo que se nécesita divid.irel mensaje en bbques de una letra:' t -
H = 0 8 = M r O = 1 5 = M z , L = 1 2 = M ¡ A = 0 1 = M ¿
Para cada uno de los submensajes Mi se necesita obtener Ci = M]módulo 77. Se puede verif,car fácilmente eue C1 = 57, C2=71,C3 = ll y Qu= l, por lo gue el mensaje encriptado es
C = 5 7 7 l l 2 0 1
E¡emplo 4,43 Descürar C = 5? usando la clave privada (43,7't).
Soluclón Se necesita calq¡lar 57o3 módulo 77, Con este fln se ob.serva cJue 43 = 25 + 23 + 2 + | = 32 + I + 2 + l. Por esto se iiene que
Ahora bien
5 7 4 3 - 5 7 3 2 . 5 i 8 . 5 7 2 . 5 i
5 7 t 6 = 3 6 2 = 6 4
5732=642=15
(mód 77)
(mód 77)
(m6d 77)
(m6d77)
(mód 77)
(m6d 77)
Por Io tanto
5'741 = 5'7 . 15 . 36. 15 = 8 (mód 7?)
Es decü, el mensaje nunérico es 08, gue cosesponde a la letra H.
MATEMÁTrcAs DrscRETAs - RAMóN EspiNosA ARMENTA ALFAOMEGA
tr
182 IV. Grupos, ANILLos v cAMPos
En la práctica los números p y q se eligen de modo gue tenga¡ alrededor de 100dÍgitos docimales, por lo gue n =pq tiens alIededor de 200 dfgitos. En la astualidadno existe un método que permita fadorizar un ntlms¡o tan gTrande en un üempssuflcientemente pagusño como pa¡a gue pueda ser utilizado para enconuar h' clavo pr¡vada d, por esta razón el sietema BSA puede consid€larse como un cipto.sistema de clave Pública.
4.8.1 MATLAB y el crlptosistema RSA
En este capÍhllo se presento la noción de opeÉciÓn binaria, luego se eLpuso el con"cepto de gnupo y los @nceptos de anillo y caopo, proba¡do sus propiedados en cadacaso. En partrcular se pressntó el anillo de los enteros módl¡lo m y cómo sé utiliza laa¡itú[itica modular en la criptogirafÍa moderna'
ED el slguiente capitulo se estudia un a¡üo particular: el anüo de los polinomioscon cosfsientes en un caripo arbiüario.
En la lectura adio¡onal
MATLAB Y EL CRIPTOSISTEMA RSA
s6 describe la forma en que se usa MATLAB para implementar simuladorss como Ge.norador de clavss BSA, Codlflcadot RSA y D€codlf¡cador RSA.
ALFAOMEEA MATEMÁTICAS DISCNTTA8 - RAMóN ESPINO8A A3MENTA
¡..10 PRoBLEMAS 'i.51,
4.56 Demostrar gue [] es ei eiáinento unitarÍo en 2,, lill,,' . . ,:" : ,' :
, ; l i i ; . , . . . i , : . . . i i ' ! r : : , ; ,
4.57 Demostrar Ia propiedad distribufiva en 2,,,,. I i '.
4.58 Escribir las tabias para la suma y el producco en Za.
Ztg
4.63 Utüzar el t€orema de Euler para determir¡ar ei inverso de [5] en Z59. . '
ara deferminar el inverso de l8l enZ31.
t l l v tp - 11 ,- 11 ,
4,67 Utüzar el sistema RSA para enciptar el mensaje AVEblica (5, 85).
4.69 Utilizar el sÍstema RSA para encíptar el mensaje UVA con Ia clave pú-blica (7, 9l).
M ¡ t r v r ¡ r r c , r ' D ! c R E f A t R A M o N f s f . N . , . A p r , ¡ , N - ^ ALFAOMEGA
4.68 Usardo los slmuladores
. GENERADOR DE CTAVES RSA
. CODIFICADOR RSA
. DECODIFICADOR RSA
rae^ lvÁr ó l ñ rñh lóñr .ñ rÁt i ^ i
ALFAOMEGA
GRUPos, ANELoS Y cAMPos
MATEr,rÁTrcAg D$CRETAS - RAMóN EspnlosA ARMENTA
4.7¡¡ UsaDdo ¡os simuiadoreÉ
. GENEnADOR DE CLITVES nSA
. CODItrICADOA NSA
. DECODIFIOADOR RSA
fesolver eI problema anterior.