Viquipèdia

Aritmètica modular

operacions algebraiques aplicades als residus resultants de dividir nombres enters entre un altre fix i positiu
Aquest article tracta sobre el concepte d'aritmètica modular; la principal eina de l'aritmètica modular és la congruència sobre els enters.

En matemàtiques, i més concretament en teoria de nombres algebraics, l'aritmètica modular és un conjunt de mètodes que permeten la resolució de problemes sobre els nombres enters. Aquests mètodes sorgeixen de l'estudi del residu obtingut per una divisió.

Coberta de l'edició original de les Disquisitiones arithmeticae de Gauss, llibre fundador de l'aritmètica modular.

La idea de base de l'aritmètica modular és de treballar no sobre els nombres mateixos, sinó sobre els residus de la seva divisió per alguna cosa. Quan es fa, per exemple, la prova del nou, s'efectua una operació d'aritmètica modular sense saber-ho: el divisor és el valor 9.

Tot i que els seus orígens es remunten a l'antiguitat, generalment, els historiadors associen el seu naixement l'any 1801, data de la publicació del llibre Disquisitiones arithmeticae[1] de Carl Friedrich Gauss (1777 - 1855). El seu nou enfocament permet elucidar cèlebres conjectures[2] i simplifica les demostracions d'importants resultats[3] gràcies a una major abstracció. Si bé l'àmbit natural d'aquests mètodes és la teoria dels nombres, les conseqüències de les idees de Gauss es troben també en altres camps de les matemàtiques, com l'àlgebra o la geometria.

El segle xx modifica l'estatut de l'aritmètica modular. D'una banda, es necessiten altres mètodes per progressar en la teoria dels nombres. D'altra banda, el desenvolupament de nombroses aplicacions industrials imposa la posada a punt d'algorismes procedents de les tècniques modulars. Resolen essencialment qüestions sorgides en la teoria de la informació, una branca considerada actualment, sobretot, com matemàtiques aplicades.

Usos modifica

En matemàtiques pures, s'utilitza molt poc aquest terme. El vocable proper més freqüent és la teoria algebraica dels nombres,[4] que designa un àmbit més ample que conté, per exemple, les nocions d'enters algebraics i de la teoria de Galois.[5]

En matemàtiques aplicades, aquesta expressió es fa servir freqüentment per descriure les bases matemàtiques de diferents àmbits de la teoria de la informació: criptografia, teoria de la codificació i informàtica. En aquest camp d'estudi hi entren nombroses eines i algorismes. S'hi troben els tests de primalitat, la Factorització,[6] la utilització dels caràcters de Dirichlet, per exemple, per la transformada Discreta de Fourier[7] o, fins i tot, l'estudi d'altres quocients diferents del dels enters, com el dels polinomis.[8]

Segons els diferents autors i en funció l'àmbit d'aplicació, aquestes extensions es consideren, o bé com una part integrant de l'aritmètica modular,[9] o bé com aplicacions que, fins i tot, arriben a no ser citades. Sota la seva forma senzilla, pren de vegades el nom d'aritmètica del rellotge.[10] El terme sistema modular es fa servir[11] per designar una aritmètica modular sobre altres conjunts diferents del dels enters.

Història modifica

Orígens modifica

 
Coberta de l'edició de 1621 d'Aritmètica de Diofant, traduïda al llatí per Claude-Gaspard Bachet de Méziriac.

Al segle III aC, Euclides formalitzà, al seu llibre els Elements, els fonaments de l'aritmètica. S'hi troba el lema que porta el seu nom, una versió del teorema fonamental de l'aritmètica i un estudi sobre els nombres perfectes[12] en la proposició 36 del seu llibre IX.[13] Diofant d'Alexandria, cap al 250,[14] escrigué Arithmetica que conté 130 equacions. Tracta essencialment de problemes que tenen una única solució numèrica si els valors permesos només són fraccionaris o enters. S'hi troba el fet que els nombres suma de dos quadrats perfectes no són mai de la forma 4 n + 3. Les equacions, amb coeficients sencers i de les quals les solucions que es busquen són senceres avui en dia i prenen el nom d'equacions diofàntiques.

La Xina desenvolupà paral·lelament una aritmètica modular. Sun Zi va escriure cap a l'any 300 un tractat de matemàtiques[15] en el qual el problema número 26 del capítol 3 és el següent:

« Siguin uns objectes dels quals s'ignora el nombre. Comptant-los de 3 en 3 en queden 2, comptant-los de 5 en 5, en queden 3 i comptant-los de 7 en 7, en queden 2. Quants objectes hi ha? »
— Sun Zi, Manual de matemàtiques[16]

Qin Jiushao (1202 – 1261) desenvolupà el teorema xinès del residu.[17] El seu llibre, tracta d'un sistema d'equacions lineals de congruències en el cas on els mòduls no són primers entre ells, dos a dos. Els seus treballs sobre els sistemes de congruències superen en sofisticació els de Leonhard Euler (1707 – 1783). George Sarton afirma que:

« Qin Jiushao era un dels majors matemàtics de raça xinesa, del seu temps i a dir veritat de tots els temps »
— George Sarton.[18]

El segle xiv va veure un declivi progressiu, i posteriorment un oblit, d'aquests resultats; el fet de saber de Qin Jiushao no depassà les fronteres xineses fins a l'arribada del segle xx, quan va ser redescobert pels treballs de l'historiador de les ciències Joseph Needham. Per contra, les nombroses similituds entre les notacions àrabs i xineses fan pensar en què devien existir contactes entre ambdues cultures durant els períodes precedents.[19]

L'Índia té també una forta tradició en aritmètica. Âryabhata (476 – 550) recercà de manera sistemàtica[20] les solucions senceres de l'equació lineal de dues incògnites amb coeficients sencers. Per aconseguir-ho, utilitzà un algorisme anomenat «Kuttaka» que publicà en el seu llibre[21] titulat Aryabhatiya. Brahmagupta (598 – 668) estudià les equacions diofàntiques de grau dos amb l'ajuda del mètode chakravala.[22]

La civilització islàmica jugà un doble paper en aritmètica: vehiculà el saber dels grecs, indis, xinesos i europeus,[23] i aportà coneixements nous[24] sobretot en relació a l'estudi de les propietats de certs conjunts d'enters, com els nombres primers], perfectes, amics o figures.[25] En aquest context, Qusta ibn Lûqâ realitzà una traducció parcial de l'Arithmetica de Diofant d'Alexandria[25] a finals del segle ix i, a la mateixa època, Al-Hajjaj traduí els Elements d'Euclides.[26] El seu col·lega al-Khuwrizm (783 – 850) va escriure un llibre sobre la numeració índia; tot i que el llibre s'ha perdut, es coneix per una traducció llatina existent, Algoritmi de numero Indorum,[27] Thābit (836 – 901) estudià els nombres amics i els nombres perfectes.[28] Finalment, Alhazen (965 – 1039) continuà els treballs anteriors sobre els nombres perfectes i descobrí el teorema de Wilson.[29]

Aparició a Europa modifica

 
Pierre de Fermat realitzà grans aportacions a l'aritmètica. Les propietats de la divisió euclidiana, fonament de l'aritmètica modular, són molt utilitzades per aquest matemàtic.

El 1621, Claude-Gaspard Bachet de Méziriac (1581 – 1638) traduí el llibre de Diofant al llatí; les qüestions que presenta interessen els matemàtics de l'època, particularment als francesos. Pierre de Fermat (1601 – 1665) proposà un gran nombre d'enunciats, dels quals els tres més cèlebres són probablement: el seu últim teorema, el teorema de la suma de dos quadrats i el petit teorema. La comunitat científica es llançà als desafiaments en aquest tipus de qüestions, i així Fermat demanà: «Un nombre quadrat que, afegit a la suma de les seves parts alíquotes (és a dir els seus divisors), faci un cub.» Per concloure: «Espero la solució d'aquestes qüestions; si no la subministra ni Anglaterra, ni la Bèlgica Gala o Celta, ho farà la Narbona.[30] Marin Mersenne (1588 – 1648) investigà els nombres primers particulars. Fermat li escrigué: «Si jo pogués una vegada tenir raó fonamental en què 3, 5, 7, 17, 257, 65537…, són nombres primers, em sembla que trobaria moltes coses boniques en aquesta matèria, ja que ja he trobat coses meravelloses de les quals el faré part».[31] Aquests nombres ara s'anomenen nombres de Fermat i la seva frase ha resultat ser l'única conjectura falsa proposada per l'autor. René Descartes (1596 – 1650) intentà, sense aconseguir-ho, demostrar que si la divisió per vuit d'un nombre primer dona per residu un o tres, aquest nombre es pot escriure de la forma x² + 2y².

Sobre aquest tipus de problemes, hi ha dos elements a destacar:

  • Les equacions diofàntiques fascinen, i el títol d'un dels llibres de Bachet de Méziriac és evocador: Problemes agradables i delectables que es fan pels nombres. Es pot citar encara l'observació de Fermat a propòsit del seu gran teorema: «He trobat una solució meravellosa … »[32]
  • Els problemes plantejats són difícils. Malgrat alguns èxits com la identitat de Bézout, deguda probablement a Bachet de Méziriac, l'essència les qüestions es queden sense resposta, com és el cas del teorema dels dos quadrats de Fermat, o amb respostes almenys poc convincents, com la de Fermat en relació al seu gran teorema: «… però em manca lloc aquí per desenvolupar-lo»; la primera prova reconeguda apareixerà el 1994, 1995.[33]) Ben sovint, Fermat acaba els seus teoremes amb comentaris reconeixent el seu fracàs: «Li reconec clarament (igual que adverteixo per endavant que no sóc capaç d'atribuir-me més del que sé, també dic amb la mateixa franquesa el que no sé) que encara no he pogut demostrar… aquesta bella proposició que li he enviat… ».[34]

Mètodes utilitzats modifica

 
Leonhard Euler, teòric dels nombres del segle xviii, resolgué diverses equacions diofàntiques.

El segle següent va assistir a la resolució d'algunes d'aquestes qüestions, sovint per Leonhard Euler que contradigué Fermat tot demostrant que els seus nombres no són sempre primers, i provà el teorema de la suma dels dos quadrats.[35] També cometé errors; la seva temptativa de demostrar l'últim teorema de Fermat per n igual a tres va ser un fracàs.[36] També tractà altres qüestions, com ara la llei de reciprocitat quadràtica el 1782.

Fins als inicis del segle xix, els mètodes utilitzats, si bé denoten una gran astúcia en les habilitats dels matemàtics, són poc nombrosos i de principis senzills. L'exemple següent, extret del problema dels dos quadrats, ho il·lustra:

Existeix un nombre del qual la divisió per quatre dona residu tres i que és suma de dos quadrats? a² i b² són aquests dos quadrats. Sols un és parell ja que si no la seva suma seria parell i la seva divisió per 4 tindria o bé 0 o bé 2 com residu. Se suposa a parell i b senar. Si a és parell llavors el seu quadrat és un múltiple de 4. L'enter b és senar; per tant, es pot escriure com 2c + 1, el seu quadrat és igual a 4c² + 4c + 1, la divisió de b² entre quatre dona de residu 1, i la suma dels dos quadrats dona també de residu 1.
  • La primera eina utilitzada és la dels nombres primers, aquest raonament és exacte, ja que 2 és un nombre primer.
  • La segona és la transformació algebraica, es transforma b en 2c + 1. Utilitzat amb virtuositat, permet als matemàtics de l'època resoldre certes equacions diofàntiques. Tota l'astúcia resideix a escollir amb habilitat les transformacions adequades.
  • La tercera és la divisió euclidiana, els quadrats i la seva suma es divideixen sistemàticament entre 4.
  • El quart no s'il·lustra en l'exemple, ja que correspon al descens infinit utilitzat en la demostració d'Euler del teorema de la suma dels dos quadrats. Consisteix a trobar a partir d'una solució sencera una altra solució sencera positiva i estrictament més petita. La successió de solucions baixa de manera infinita en sencers positius, i això no és possible. Aquest mètode ja va ser utilitzat per Fermat per demostrar el seu darrer teorema pel cas en què n és igual a 4.

El caràcter rústic de les eines es tradueix en demostracions llargues i tècniques, com per exemple la demostració d'Euler del teorema de la suma dels dos quadrats. A més, i malgrat més d'un segle d'esforços, l'essència de les equacions diofàntiques resisteixen a aquest tipus d'enfocament.

L'aportació de Carl Friedrich Gauss modifica

 
Carl Friedrich Gauss és el fundador de la branca de la matemàtica que avui s'anomena aritmètica modular.

A l'edat de 17 anys, Carl Friedrich Gauss (1777-1855) demostrà la llei de reciprocitat quadràtica. Un any més tard, el 30 de març de 1796, prengué consciència que els seus càlculs aritmètics permetien construir amb el regle i el compàs l'heptadecàgon, és a dir, el polígon regular amb disset costats, problema que continuava sense resoldre des de l'antiguitat. Finalment, el 1801, publicà Disquisitiones arithmeticae (Recerques aritmètiques) i rebé el sobrenom de príncep dels matemàtics.[37]

Aquests dos grans descobriments procedeixen d'un mateix avenç, la posada a punt d'eines més sofisticades que aquelles de les quals disposaven Fermat o Euler, simplificant les demostracions al preu d'una abstracció més gran. Amb els seus avenços fundà l'aritmètica modular.

Aquesta s'aplica en principi als nombres enters, després als polinomis, i després a un nou conjunt d'enters que ara s'anomenen enters de Gauss. Dirichlet (1805 – 1859) descobrí un conjunt anàleg, el dels enters de Dirichlet, amb els quals va iniciar la demostració del teorema de Fermat per n= 5, recerca que envià a l'Acadèmia Francesa de les Ciències el 1825. Fou analitzada per Legendre, que hi dedica alguns mesos per portar-la a bon fi.[38]

Totes les equacions diofàntiques de Fermat es resolen ara a excepció del seu últim teorema. Tot i així, apareixen noves conjectures; per exemple, si a i b són primers entre ells, la progressió aritmètica de valor inicial a i de raó b, quants nombres primers conté? Gauss i altres matemàtics com Legendre van imaginar que en conté una infinitat però no aconseguiren demostrar-ho. Igualment, la llei de reciprocitat quadràtica ha de posseir equivalents per ordres superiors.

L'aritmètica modular s'anà enriquint. Dirichlet, un alumne de Gauss troba una demostració[39] del teorema de les progressions aritmètiques desenvolupant el concepte dels caràcters i formalitzant les bases de la teoria analítica dels nombres. El seu raonament és una meravella de l'aritmètica modular; Carl Gustav Jacob Jacobi (1804 – 1851) deixà escrit en una carta al seu germà: «Aplicant les sèries de Fourier a la teoria dels nombres, Dirichlet ha trobat recentment resultats que assoleixen els cims de la perspicàcia humana.»[40] Dirichlet no va ser el primer a utilitzar eines que són ara qualificades de conseqüència de l'aplicació de l'anàlisi harmònica sobre un grup abelià finit. Legendre, per intentar demostrar la llei de reciprocitat quadràtica, va desenvolupar càlculs similars[41] sobre els reals, formalitzant el que ara es diu el símbol de Legendre. Finalment, Gauss, en el seu llibre de 1801, generalitzà aquest enfocament als nombres complexos. Els seus càlculs porten el nom de sumatori de Gauss i període de Gauss.

Al segle xix, aquestes matemàtiques es denominen aritmètica transcendent.[42] Si bé el terme d'aritmètica continuà sent usat a bastament, el 1830, Legendre considerà aquesta branca com prou desenvolupada per merèixer el terme de teoria dels nombres.[43] L'aparició de noves tècniques, diferents de les de Gauss, introduí una subdivisió en la teoria algebraica dels nombres i la teoria analítica dels nombres. El terme d'aritmètica transcendent quedà llavors en desús amb l'aparició dels nombres transcendents.

Segle XX modifica

Criptografia modifica

 
Auguste Kerckhoffs enuncià un principi fundador de la criptografia moderna.
 
La màquina criptogràfica Enigma, una màquina de xifratge utilitzada durant la Segona Guerra Mundial, sistema desxifrat per un matemàtic: Marian Rejewski.

Amb el pas del temps, allunyant-se de l'àmbit de les matemàtiques pures, determinades aplicacions industrials fan cada vegada més ús de les nocions matemàtiques desenvolupades per Gauss; aquestes es concreten en la ciència dels codis secrets anomenada criptografia. El 1883, Auguste Kerckhoffs (1835 – 1903) enuncià que: «La seguretat d'un sistema de criptografia no ha de descansar sobre el secret de l'algorisme. La seguretat no es basa més que en el secret de la clau».[44]

Al començament de la dècada del 1930, l'oficina de xifratge polonesa demanà ajuda al matemàtic Marian Rejewski (1905 – 1980) perquè desxifrés el codi del sistema Enigma, utilitzat pels alemanys. Els antics codis, com el xifratge de Cèsar, es reinterpretaven com una transformació matemàtica en aritmètica modular de Gauss sobre els nombres enters. Per descriure aquestes tècniques es fa servir el terme d'«aritmètica modular».[45] Durant la dècada del 1970, Horst Feistel (1915 – 1990) desenvolupà un sistema de criptografia simètrica de clau privada, el Data Encryption Standard, o DES, que esdevingué l'estàndard de les aplicacions no classificades.[46] Les criptoanàlisis de DES i, més generalment, dels xifratges simètrics, utilitzen matemàtiques procedents dels treballs de Dirichlet sobre els caràcters, en el marc d'un espai vectorial sobre un cos finit amb dos elements.

El 1976 es descobrí una nova família de sistemes de xifratge,[47] basats en una clau pública. Ràpidament es desenvoluparen productes industrials, dels quals el més cèlebre és l'anomenat RSA. Es basa en els treballs de Fermat i d'Euler.[48] El terme «aritmètica modular» és, en aquest context, utilitzat per descriure[49] no només l'estructura dels mòduls sobre els enters, sinó també els teoremes que tracten dels nombres primers com la descomposició en producte de factors primers, el teorema dels residus xinesos, el petit teorema de Fermat i la seva generalització per Euler.

L'aritmètica modular és un àmbit d'investigació actiu al començament del segle xxi. Una implementació eficaç requereix la utilització d'operacions sobre grans conjunts de mòduls. L'enfocament de Gauss és utilitzat sobre polinomis de coeficients en un cos finit. L'aritmètica modular es generalitza a altres conjunts diferents dels quocients d'enters,[50] per exemple, per la criptoanàlisi.

Teoria de la informació modifica

Article principal: Teoria de la informació
 
Un Processador Pentium conté una unitat aritmètica i lògica basada en l'aritmètica modular.

La criptografia no és l'únic àmbit que utilitza el vocable «aritmètica modular». La fi de la Segona Guerra Mundial va presenciar l'aparició d'una nova ciència: la teoria de la informació. El 1948, sota l'impuls de Claude Elwood Shannon (1916 – 2001), aquesta esdevé[51] una branca de les matemàtiques aplicades.

Si bé la confidencialitat és un dels assumptes tractats, la fiabilitat també és un tema principal. Richard Hamming (1915 – 1998), el 1950, proposà un primer algorisme;[52] Els mòduls sobre els enters es fan servir per a una de les tècniques més senzilles de codificació: les sumes de verificació. El 1960, es desenvoluparen nous codis més potents,[53] sobre la base de polinomis amb coeficients en un cos finit; l'aritmètica utilitzada pren sovint el nom de «modular»[54]

A començaments de la dècada del 1960, la informàtica esdevé un subjecte d'estudi universitari.[55] Les restriccions inherents a l'estructura dels processadors imposen la representació dels nombres en forma d'una successió finita de xifres, justificant la utilització dels mòduls. El terme «aritmètica modular» apareix sovint[56] i s'hi troben, per exemple, fins i tot, els enters de Gauss o els polinomis per càlculs sobre grans enters.

Les tècniques desenvolupades per la criptografia, la teoria dels codis i l'aritmètica informàtica descansen sobre els mateixos conceptes, oferint una relativa unitat a les matemàtiques utilitzades en la teoria de la informació.

Eines de l'aritmètica modular modifica

Congruència i els enters modifica

Article principal: Congruència sobre els enters

L'exemple històric de la «aritmètica modular» descansa sobre els nombres enters. Donat un enter n, el càlcul mòdul n consisteix a identificar tots els enters amb el seu residu en la divisió euclidiana entre n; això es pot il·lustrar amb l'exemple de la «aritmètica del rellotge», que correspon a n=12: l'agulla petita es troba en la mateixa posició en dos moments separats per dotze hores i s'identifica, per exemple, les 13 a la 1. Per obtenir un càlcul sobre un conjunt com aquest, es verifica que l'addició i la multiplicació són compatibles amb les identificacions. Aquesta formalització[57] és obra de Legendre, que dona el nom de residu als diferents elements.

L'aportació de Gauss consisteix a analitzar l'estructura d'aquest conjunt, ara qualificat amb el nom d'anell de congruències, i amb la notació Z/nZ. Es comença per l'estudi de l'addició, que defineix un grup cíclic de generador 1; després, pel de la multiplicació, que depèn de les propietats del mòdul; si aquest és primer, s'obté un cos. Aquest enfocament simplifica les demostracions aritmètiques. Els dos exemples històrics del llibre Disquisitiones arithmeticae són el teorema de Wilson[58] i el petit teorema de Fermat[59]

El càlcul modular, en el cas on el mòdul no és primer, és més complex. El teorema dels residus xinesos permet elucidar-ne l'estructura; l'anell no és íntegre, existeixen divisors de zero, i són nombres que, multiplicats per un cert altre nombre no nul, donen com a resultat zero. El nombre d'elements invertibles ve donat per la funció Fi d'Euler. Aquesta funció permet, per exemple, generalitzar el petit teorema de Fermat.

Residu i polinomi modifica

Article principal: Polinomi ciclotòmic
 
Figura construcció amb regle i compàs de l'heptadecàgon, un polígon regular de 17 costats, obtingut amb les tècniques de l'aritmètica modular.

Gauss observà que en el conjunt dels polinomis de coeficients racionals es pot aplicar la lògica del càlcul modular, ja que disposa d'una addició, d'una multiplicació i d'una divisió euclidiana. Les congruències són els residus de la divisió euclidiana dels polinomis per un polinomi donat.

A continuació, Gauss aplicà aquest tipus d'enfocament al polinomi Xn - 1, que pren el nom de polinomi ciclotòmic, i troba la seva descomposició en producte de factors irreductibles. Gauss utilitzà aquests resultats per trobar una construcció amb regle i compàs de l'heptadecàgon, el polígon regular amb 17 costats.

El matemàtic alemany dubtà en el moment de situar aquests treballs dins l'aritmètica. Escrigué:

«La teoria de la divisió del cercle, o dels polígons regulars…, no pertany "per se" ni tan sols a l'Aritmètica, sinó els seus "principis" no poden ser extrets més que de l'Aritmètica transcendent.[60]

El terme aritmètica «transcendent» de Gauss és ara reemplaçat pel d'aritmètica «modular». La lògica d'aquest argument és un tema que sempre està d'actualitat.

Enter algebraic modifica

Article principal: Enter de Gauss

El cas dels polinomis de coeficients sencers difereix: la propietat de divisió no funciona més que per polinomis dels quals el major coeficient és igual a més o menys un. Si es considera el cas dels mòduls del polinomi X² + 1, l'estructura modular obtinguda és encara la d'un anell, que es pot identificar amb el conjunt dels nombres de la forma α + i.β, on α i β són enters i "i" designa el nombre imaginari, corresponent al monomi X. Aquest conjunt és el dels enters de Gauss.

 
Il·lustració de la divisió euclidiana entre els enters de Gauss
 
Il·lustració de la demostració del teorema de la suma dels dos quadrats pels enters de Gauss

Es pot dotar aquest conjunt d'una norma. A l'enter de Gauss a = α + i.β se li associa la norma α² + β², que prové del mòdul dels nombres complexos. Aquesta norma permet definir una divisió euclidiana, com la il·lustra la figura de la dreta. Els enters es representen amb les interseccions de la quadrícula. El valor a/b existeix si b és diferent de zero; tanmateix aquest valor no és necessàriament un enter de Gauss. La divisió es representa amb el punt negre de la figura. Dir que una divisió euclidiana existeix, significa dir que existeix un enter de Gauss amb una norma estrictament inferior a un d'aquests punts negres. La il·lustració mostra que, en el cas present, existeixen almenys tres candidats. En el cas general, n'existeixen entre un i quatre i, en aquest context, només l'existència compta.

Aquest resultat de divisió euclidiana implica propietats sobre aquest anell d'enters: la identitat de Bézout, l'existència de nombres primers de Gauss i un equivalent del teorema fonamental de l'aritmètica. Aquests nombres primers permeten a Richard Dedekind (1831-1916) proposar una resolució senzilla del teorema de la suma dels dos quadrats. La il·lustració geomètrica es dona a la figura de l'esquerra. Un nombre primer p s'expressa com la suma de dos quadrats si el cercle de radi de l'arrel de p creua, almenys, un enter de Gauss.

Ferdinand Eisenstein (1823 1852), que l'any 1844 es trobà amb Gauss,[61] descobrí un nou anell d'enters;[62] l'aritmètica sobre aquest anell ofereix una demostració rigorosa de l'últim teorema de Fermat per n igual a tres, justificant així, la necessitat teòrica d'aquesta generalització de l'aritmètica modular.

Caràcter de Dirichlet modifica

Article principal: Caràcter de Dirichlet
 
Peter Dirichlet desenvolupà l'essència de la teoria en el marc de l'anell Z/nZ.

Dirichlet s'interessà pels nombres primers de la forma n + λ.m, on n i m són dos enters primers entre ells, i λ és una variable que descriu el conjunt dels enters positius. Aquest matemàtic desitjà, en efecte, demostrar que existeix una infinitat de nombres primers d'aquesta naturalesa. L'aritmètica modular representa una bona eina per aquest tipus de problemàtica, que és equivalent a trobar el cardinal del conjunt dels nombres primers en una classe de mòdul.

Dirichlet considerà el grup dels elements inversibles mòdul m, i estudià el conjunt de les funcions del grup en els nombres complexos no nuls que verifiquen:

si a i b són dos residus, llavors f(a.b) = f(a).f(b).

Aquestes funcions s'anomenen caràcters de Dirichlet. SI existeix φ(n), el producte de dos caràcters és també un caràcter, i la seva taula de multiplicació és exactament la mateixa que la del grup dels elements inversibles estudiat.

Els càlculs sobre aquestes funcions són formalment anàlegs a aquells que va realitzar anteriorment Joseph Fourier (1768 – 1830).[63] Tot i així, caldrà esperar fins al segle xx per veure aparèixer una teoria que unifiqui els dos enfocaments; aquesta teoria se l'anomena anàlisi harmònica o anàlisi de Fourier.

Desenvolupaments teòrics modifica

Sovint conceptes matemàtics, desenvolupats en un context, són reutilitzats en altres àmbits. Així la teoria dels grups s'aplica a l'aritmètica i a la geometria. Això també passa amb les eines desenvolupades per l'aritmètica modular, de les quals s'alimenten vastos camps de les matemàtiques pures, com l'àlgebra o la teoria de Galois. Aquestes teories, tot i així, no es consideren casos particulars de l'aritmètica modular, ja que també fan ús de molts altres conceptes.

Estructura quocient modifica

Article principal: Relació d'equivalència

En llenguatge modern, l'aritmètica modular es formalitza per la noció de quocient d'anells euclidians. El concepte de relació d'equivalència permet generalitzar aquest concepte a les principals estructures algebraiques. Per exemple, el quocient d'un grup per un subgrup normal és, a través del teorema de Jordan-Hölder, una eina bàsica de la classificació dels grups finits. Els grups quocients també es fan servir en topologia algebraica per classificar les varietats diferenciables.

En la teoria d'anells, la noció d'ideal té un paper anàleg al de la noció de subgrup normal en teoria de grups. Permet construir anells quocients en un context més general que el de l'aritmètica modular. El teorema dels zeros de Hilbert, base de la relació entre l'àlgebra commutativa i la geometria algebraica, s'expressa en termes d'ideal. Malgrat tot, els termes de congruència i de mòdul es reserven pels quocients sobre un anell euclidià.

Residus de polinomis i teoria de Galois modifica

Article principal: Teoria de Galois
 
Évariste Galois és el creador de la teoria que porta el seu nom.

L'aritmètica modular s'aplica a l'anell dels polinomis amb coeficients en un cos. És el punt de partida de la teoria d'Évariste Galois (1811 – 1832)[64] i consisteix en l'estudi sistemàtic dels conjunts de mòdul dels polinomis irreductibles, l'equivalent en el cos dels polinomis als nombres primers en el cos dels enters. Aquests conjunts ara s'anomenen extensions algebraiques.

Aquestes extensions permeten l'anàlisi de la resolubilitat de les equacions polinòmiques. Si el polinomi és irreductible, el seu conjunt de mòdul és el cos més petit que conté, almenys, una arrel; s'anomena cos de ruptura. Reiterant aquest procés, es construeix un cos que conté totes les arrels, el cos de descomposició. La lògica modular del quocient subministra a l'estructura algebraica adequada per resoldre aquesta problemàtica.

La teoria de Galois es relaciona també amb altres nocions. L'estudi de la resolubilitat de l'equació és possible per via de l'estudi del grup dels automorfismes del cos, que és anomenat grup de Galois, gràcies a la correspondència de Galois entre subcossos i subgrups. Més enllà de l'estudi de la resolubilitat de les equacions algebraiques, la teoria de Galois s'ha convertit en un marc natural per la resolució de nombrosos problemes en aritmètica, geometria aritmètica o geometria algebraica, i permet, sobretot, formular nous problemes més generals en tots aquests àmbits.

Tot i que aquesta teoria utilitza el concepte de quocient d'un anell euclidià, la varietat d'eines específiques en fa un camp propi, ben diferent del subjecte d'aquest article. S'ha de notar que un dels fruits d'aquesta teoria, els cossos finits, encara ara denominats cossos de Galois, subministren un marc natural a nombroses aplicacions en aritmètica modular.

Enter algebraic i teoria algebraica dels nombres modifica

Article principal: Teoria de nombres algebraics
 
Ernst Kummer demostrà l'últim teorema de Fermat per nombrosos valors de n i creà la teoria algebraica dels nombres.

L'aritmètica modular ofereix un bon marc conceptual per la resolució del gran teorema de Fermat. Tanmateix, si n és més gran que deu, els anells d'enters algebraics, construïts segons el mètode de Gauss, presenten el que Dirichlet en diu una obstrucció. Mostra que el grup dels invertibles d'aquest anell, és a dir, el dels elements que tenen un invers per la multiplicació, ja no és un grup cíclic o un abelià finit com els que estudiava Gauss. Conté també còpies de l'anell dels enters i és, per tant, infinit. Aquest resultat s'anomena teorema de les unitats de Dirichlet. L'obstrucció prové d'aquesta nova configuració; impedeix l'aplicació de les tècniques modulars utilitzades pels enters de Gauss, ja que l'anell associat ja no és euclidià.

Ernst Kummer (1810 – 1893) utilitzà una eina que està relacionada amb la generalització del quocient, ara formalitzat pels ideals; amb aquesta eina, es reemplacen els nombres primers absents. Llavors, la teoria algebraica dels nombres, amb tècniques diferents, en pren el relleu. L'eina de base és un anell del qual els elements es diuen enters algebraics i té una estructura anomenada anell de Dedekind. Kummer aconsegueix així demostrar[65] l'últim teorema de Fermat per certs valors de n primer, és a dir, pels nombres primers regulars. Els únics valors inferiors a 100 no tractats són el 37, el 59 i el 67.

Han aparegut altres eines i objectes d'estudi, com l'anell adèlic, els de la teoria de Galois, les corbes el·líptiques, les sèries L de Dirichlet o les formes modulars. Alguns provenen de conseqüències gairebé directes de l'aritmètica modular, com els cossos finits, utilitzats de manera intensiva durant el segle xx. La teoria algebraica dels nombres és molt més vasta que el marc de l'aritmètica modular, tot descansant in fine sobre tècniques, de vegades, similars.

Caràcter de Dirichlet i teoria analítica dels nombres modifica

Article principal: Teoria analítica dels nombres
 
Representació del valor absolut de la funció zeta de Riemann.
 
Bernhard Riemann expressà la hipòtesi de localització de les arrels de la funció ζ (zeta).

El descobriment per Euler d'un producte infinit, construït amb l'ajuda de nombres primers i igual al sisè del quadrat de la superfície d'un cercle de radi 1, obrí la via a un enfocament diferent per la comprensió dels nombres. Dirichlet l'utilitzà per demostrar que cadascun dels mòduls d'enters del grup de les unitats conté una infinitat de nombres primers. Aquest resultat porta actualment el nom de teorema de la progressió aritmètica.

Per dur a terme la seva demostració, Dirichlet desenvolupà una eina específica, les sèries L de Dirichlet. Una de les seves sèries correspon a una cèlebre funció que va adoptar el nom de ζ (zeta) de Riemann. La seva dificultat més gran consistí a demostrar que les seves funcions no tenen arrel en el punt 1. Per aconseguir-ho, utilitzà l'anàlisi harmònica sobre el grup de les unitats d'una classe de mòdul.[66]

Malgrat tot, una vegada més, l'aritmètica modular és insuficient per abordar el teorema. Dirichlet utilitzà nombroses tècniques analítiques, com les sèries enteres i l'anàlisi complexa. El fruit d'aquests treballs dona llum a una nova branca de les matemàtiques: la teoria analítica dels nombres. Un dels punts crucials d'aquesta teoria prové de l'únic article de Bernhard Riemann (1826 – 1866) en la teoria dels nombres, titulat en català: Sobre el nombre de nombres primers inferiors a un nombre donat.[67] Ell arribà a expressar la conjectura d'una localització de les arrels de la seva funció. La investigació de la posició de les arrels, iniciada per Dirichlet, es convertí en una preocupació central, i actualment continua sent una de les conjectures més difícils de les matemàtiques de la nostra època.[68]

Criptografia modifica

Article principal: Criptografia
 
El phishing és una tècnica adreçada a obtenir informacions confidencials en internet amb l'objectiu de realitzar una estafa. En criptografia, la necessitat de comunicació d'informacions confidencials representa un perill.

L'objecte de la criptografia és d'assegurar seguretat en la transmissió dels missatges. La confidencialitat així com l'autentificació dels missatges són dos exemples del sentit que es dona al terme seguretat. Es poden citar dos exemples: la protecció dels missatges que utilitza un exèrcit per impedir una anticipació de l'enemic, o la targeta blava proposada pel sistema bancari que ofereix a l'usuari una bona seguretat.

En termes més matemàtics, l'operació de xifratge es consisteix en un algorisme, és a dir, una funció f que a un missatge clar m i a una clau k se'ls associa un missatge xifrat f(k, m). El coneixement del missatge xifrat i de l'algorisme de xifratge ha de ser insuficient per reconstituir el missatge clar sense una clau de desxiframent. En el cas de la criptografia tradicional, anomenada criptografia simètrica, la clau de desxiframent és idèntica a la clau de xifratge o se'n dedueix fàcilment. Llavors aquesta clau s'ha de mantenir en secret.

La criptografia asimètrica es basa en el fet que només la clau de desxiframent ha de romandre secreta, i ha de ser coneguda només pel receptor del missatge; no necessita ser comunicada als que li han d'enviar missatges. Per exemple, l'Alícia utilitza la clau de xifratge d'en Bob, (que aquest ha fet pública prèviament) per enviar-li un missatge. Només en Bob el pot desxifrar, fins i tot l'Alícia, si hagués perdut el missatge clar, en seria incapaç. En Bob ha de respondre utilitzant la clau de xifratge de l'Alícia.

L'objectiu és doncs definir una funció senzilla d'avaluar però difícil d'invertir sense el coneixement d'un secret. L'aritmètica modular ha estat la primera a oferir solucions i és, sempre, a la base de moltes solucions comercials. Per exemple, l'intercanvi de claus Diffie-Hellman, el primer exemple històric,[47] explota la dificultat pràctica per invertir l'exponenciació modular.

La criptografia asimètrica resol, en particular, el delicat problema de la distribució de les claus en criptografia simètrica. Si es comuniquen diversos corresponsals en criptografia simètrica, es necessita una clau diferent per cada parella, mentre que si es fa en criptografia asimètrica cada corresponsal disposa d'una clau que guarda secreta, i d'una clau que publica. Tanmateix no ha fet desaparèixer els codis simètrics, que ofereixen algorismes molt més eficaços. Per una seguretat equivalent, els codis simètrics presenten l'avantatge de necessitar claus clarament més petites, de 128 bits per la versió corrent d'AES, contra més d'un miler per al RSA; però, sobretot, tant el xifratge com el desxiframent són de cent a mil vegades més ràpids.[69] Els sistemes criptogràfics moderns, com els utilitzats en les targetes bancàries, o el protocol de comunicació codificada SSL/TLS molt utilitzat sobre Internet,[70] no utilitzen la criptografia asimètrica més que al començament de la comunicació, per intercanviar les claus d'un xifratge simètric que agafarà posteriorment el relleu.

Criptografia asimètrica modifica

Article principal: Criptografia asimètrica

El codi RSA és un exemple àmpliament estès de criptografia asimètrica. Es descriu, per exemple, de la manera següent: l'Alícia[71] desitja poder rebre missatges d'en Bob sense que l'Eva els pugui desxifrar. Alícia escull dos grans nombres primers, p i q, i un enter e, un nombre primer amb l'ordre g del grup de les unitats de Z/pqZ. Aquí, g és igual a (p - 1)(q - 1), sigui aquest el valor de la funció Fi d'Euler en n=pq; se suposa que els missatges són elements d'aquest anell. Si en Bob desitja transmetre el missatge m a l'Alícia, transmet el valor de me mòdul n. L'Alícia, prèviament, ha fet públics els valors de n = pq, e i, per tant, la funció f de xifratge, que és aquí igual a:

 

L'Eva ha pogut interceptar l'enviament de f, e i n, ja que aquestes informacions són, en efecte, públiques. Contràriament, no pot interceptar els valors de p i q que mai han estat comunicats. Per en Bob, la funció de xifratge és fàcil; es tracta d'una senzilla exponenciació modular. Per l'Alícia, la lectura ho és també; en té prou amb trobar una solució a la identitat de Bézout:

 

Si (x0, y0) és una solució, en aquest cas, el teorema d'Euler diu que:

 

D'altra banda, a priori, l'Eva no coneix la descomposició en factors primers de n. Ha de calcular el logaritme discret de f(m), cosa que constitueix un problema difícil. Dels coneguts, el mètode menys lent correspon a determinar els valors de p i q. Si n és gran, no existeix, avui en dia, cap algorisme prou eficaç per resoldre aquesta qüestió. La clau que permet el xifratge és la dada de e i n. La força d'un sistema com aquest rau en el fet que el coneixement d'aquesta clau no permet el desxiframent i, per tant, pot ser pública. Els valors de p i q constitueixen la clau de desxiframent.

Criptografia simètrica modifica

Article principal: Criptografia simètrica

La criptografia asimètrica no existiria sense els mètodes que procedeixen de l'aritmètica modular. Aquesta no té el mateix paper fundador en la criptografia simètrica, però tanmateix no n'és absenta del tot. Els xifratges simètrics es divideixen en dues grans famílies, de les quals una, el xifratge de flux, sovint utilitza les successions recurrents lineals sobre un cos finit (vegeu més avall) com component de base; l'altra, la família del xifratge per blocs comprèn, entre d'altres, el DES i, el seu successor, el AES o Advanced Encryption Standard. Aquests últims actuen sobre blocs de dades d'una longitud fixa quantificada en octets com, per exemple, vuit per al DES. Per codificar un bloc s'aplica una successió d'operacions primitives bastant senzilles. Un octet, o més generalment un bloc de n bits, pot ser vist com els coeficients d'un polinomi sobre els enters mòdul dos, de grau màxim n-1. Això ha conduït els criptòlegs a interessar-se per certes operacions sobre els cossos finits de característica 2. Així, s'ha vist que l'operació d'inversió sobre el cos finit F2n, composta amb una transformació afí, té bones propietats criptogràfiques per fer-ne una de les primitives dels xifratges en bloc.[72] Això ha estat explotat pels autors del xifratge Rijndael, que ha esdevingut l'AES. La publicació oficial d'aquest últim pel NIST, l'agència federal americana, per altra banda, conté alguns elements preliminars matemàtics sobre la qüestió.[73] Tanmateix, no cal cap algorisme sobre l'aritmètica o els cossos finits per la seva implementació: aquestes operacions es representen amb taules, com les operacions anàlogues del DES obtingudes, en aquest cas, de manera molt més heurística. Certs criptòlegs han vist una feblesa potencial en la caracterització massa algebraica de Rijndael, que el faria més accessible a la imaginació dels matemàtics,[74] això no ha impedit la seva adopció per l'AES.

Test de primalitat modifica

Article principal: Test de primalitat

Els codis RSA utilitzen com claus els nombres primers p i q del paràgraf precedent. L'estratègia, per trobar-los, consisteix a escollir un nombre gairebé a l'atzar, provar si és primer o no i, finalment, recomençar en el cas que no ho sigui.

El Sedàs d'Eratòstenes és un mètode ràpid pels nombres petits. Utilitzat de manera hàbil, n'hi ha prou per verificar la primalitat d'un nombre inferior a 39.000 fent 46 proves. Per contra, per una aplicació industrial que utilitzi nombres que s'escriuen amb diversos centenars de xifres, és ineficaç.

El test de primalitat de Solovay-Strassen i, sobretot, el test de primalitat de Miller-Rabin són dos exemples àmpliament utilitzats. Es fonamenten en una anàlisi més profunda del petit teorema de Fermat i no admeten equivalents als nombres de Carmichaël, la qual cosa elimina un dels problemes del test de Fermat. Aquests dos mètodes es poden emprar per construir una prova de primalitat per mitjà de verificar la propietat per un nombre determinat de valors de a que queda garantida una prova irrefutable. En aquest cas, el nombre de càlculs a efectuar és prohibitiu i, per tant, es conforma amb un test de primalitat; aquest consisteix a verificar la congruència sobre un conjunt de valors de a escollit per poder assegurar una probabilitat de primalitat superior a un valor donat, sovint igual a 1 - (1/2)100.[75]

Descomposició en producte de factors primers modifica

Article principal: Descomposició en producte de factors primers

La seguretat per la foscor no es fa servir per als codis RSA. És important, per tant, conèixer precisament l'estat de l'art de la descomposició dels enters en factors primers. Un concurs anomenat competició de factorització RSA va estar obert fins al maig de 2007, proposant un premi per qualsevol que fos capaç de factoritzar un nombre escollit en una llista feta pública.

D'altra banda, el garbell d'Erastòstenes és un test de primalitat que ofereix un mètode de descomposició; però no és aplicable per grans nombres, ja que és massa lent.[76] Els diferents mètodes que es fan servir actualment descansen sovint sobre els residus quadràtics.[77] Un divisor de zero és un residu quadràtic que conté com a representants, almenys, dos quadrats perfectes; l'objectiu és poder trobar aquests dos quadrats. Aquest tipus d'enfocament és el del garbell quadràtic i de l'algorisme de factorització pel garbell sobre el cos de nombres generalitzat, el més ràpid conegut fins al 2007.[78] També es pot citar l'Algorisme rho de Pollard que utilitza la paradoxa dels aniversaris.

Cos finit modifica

Article principal: Cos finit

Igual com succeeix a l'aritmètica de les matemàtiques pures són necessàries altres estructures per explotar les capacitats que ofereix l'aritmètica modular. En informàtica, els nombres es codifiquen sobre n bits, és a dir, corresponen a una successió de longitud n composta de zeros i d'uns. Una successió com aquesta pot ser considerada com un vector d'un espai vectorial de dimensió n sobre el cos finit F₂ de dos elements.

Aquesta estructura es considera sovint com l'espai dels polinomis amb coeficients en F₂. Per garantir l'estabilitat de la multiplicació s'aplica la lògica de Gauss i aquest espai es divideix per un polinomi irreductible, l'equivalent d'un nombre primer, de grau n; l'estructura obtinguda és el cos finit del cardinal 2n. Un nombre a mòdul 2 n, i un polinomi P[X] del sistema modular s'assemblen molt i, en efecte, s'expressen:

 

Un exemple del seu ús s'observa en la creació d'un generador de nombres pseudoaleatoris en F₂. Aquests generadors s'utilitzen, per exemple, per al xifratge de flux A5/1 utilitzat en el context d'una comunicació oral per telèfon mòbil.[79] Un element de l'algorisme és la constitució d'un registre a decalatge; donades dues successions finites d'elements de F₂ de longitud n, una successió de coeficients i una seqüència d'inicialització, tenim que:

  i   

Així, aquest registre subministra una successió pseudoaleatòria (uj) obtinguda mitjançant una recurrència lineal:

 

D'altra banda, la successió dels coeficients sovint és fixa i, d'aquesta manera, la clau és la seqüència d'inicialització, que pot ser representada amb un enter a mòdul 2n:

 

Finalment, la successió que s'obté és periòdica; però, tanmateix, si la successió dels coeficients està ben escollida, el període és molt llarg: 2n - 1. Aquesta situació es produeix quan el polinomi de retroacció R[X], és el polinomi mínim d'un element primitiu del grup cíclic F2n*, formulació que queda representada de la següent manera:

 

Anàlisi harmònica sobre un grup abelià finit modifica

Article principal: Anàlisi harmònica sobre un grup abelià finit

Les idees de Dirichlet s'apliquen al sistema modular del paràgraf precedent. Respecte a l'addició, l'espai vectorial V precedent és un grup abelià finit. Els caràcters d'aquest grup formen una base ortonormal del conjunt de les funcions de V en el grup dels nombres complexos. Cal destacar que el conjunt d'arribada escollit no és sempre el dels complexos sinó, de vegades, el cos F₂;[80] els resultats són estrictament idèntics. Aquesta estructura disposa d'una anàlisi harmònica; si el conjunt d'arribada s'escull amb un valor igual a F₂, la transformada de Fourier pren el nom de transformada de Walsh. Aquest tipus d'enfocament es fa servir per als sistemes DES, RSA i certs xifratges de flux.

Un registre a decalatge és massa fàcilment desxifrable. Per un registre de longitud n, l'algorisme de Berlekamp-Massey permet determinar-la gràcies al coneixement de 2n valors consecutius amb una complexitat quadràtica, fins i tot si la successió engendrada és de període 2n - 1. Així, si la clau té 128 bits, n'hi ha prou amb 128 x 128 k = 16 384 • k etapes per desxifrar-lo, on k és un valor prou «petit» perquè representi una seguretat insuficient. La solució adoptada consisteix a utilitzar diversos registres de diferència. Els diferents resultats són vistos com un element d'un nou espai vectorial sobre F₂. Una funció booleana associa a cada element d'aquest espai el valor 1 o 0. Si aquesta funció està ben escollida, el millor algorisme de desxiframent que es coneix necessita de l'ordre de 2n etapes per trobar el senyal. La determinació d'aquesta funció s'obté amb l'ajuda de les eines de l'anàlisi harmònica.

Al final del segle xx, per un codi RSA, sovint, la clau és un nombre superior a 10.308;[81] en aquest cas, és important disposar d'una multiplicació ràpida sobre els grans mòduls. La tècnica consisteix a identificar els mòduls amb els polinomis sobre un cos finit. La multiplicació de dos polinomis de grau n és una operació que, si és realitzada de manera ingènua, imposa una complexitat quadràtica. En ser els caràcters del grup additiu associats ortogonals, si es fa servir aquesta base, la complexitat es fa lineal. Un càlcul més ràpid consisteix a realitzar una transformada ràpida de Fourier, tot multiplicant els dos resultats i efectuant la transformada de Fourier inversa. La complexitat total és n log(n), on log designa aquí el logaritme de base dos.

Codi corrector modifica

Article principal: Codi corrector
 
Els CDs utilitzen com codi cíclic una variant del codi de Reed-Solomon anomenat codi C.I.R.C.

Un codi corrector no té la vocació d'assegurar la seguretat, sinó la fiabilitat de la transmissió d'un missatge; si durant la transmissió es produeix una pertorbació aleatòria i moderada, permet restituir el text original. El missatge codificat és transmès en una forma anomenada paraula del codi que conté, no només les informacions del missatge inicial, sinó també les redundàncies que permeten la validació d'una bona comunicació i, de vegades, la correcció automàtica d'eventuals errors.

Una paraula del codi està constituïda per una família de n caràcters triats en un alfabet, en general, binaris. El cas industrial més freqüent és el del codi lineal, on el valor n és constant per cada paraula del codi i s'anomena dimensió del codi. El conjunt de les paraules del codi té una estructura d'espai vectorial de dimensió n.

Els codis lineals utilitzen essencialment l'aritmètica modular com base matemàtica. Molts, enriqueixen l'estructura d'espai vectorial amb la d'un anell de polinomis sobre un cos finit. Aquest anell és, de vegades, l'anell binari i, sovint, un anell de cardinal una potència de dos. En aquest cas es parla d'un codi cíclic.

Els codis lineals són àmpliament presents a la indústria. Les telecomunicacions, els utilitzen per als telèfons mòbils o internet; la informàtica, principalment per la comunicació entre la memòria i el processador; els audiovisuals, pels discs compactes o d'altres formats d'igual naturalesa com els DVD.

Checksum modifica

Article principal: Checksum
 
Codi de longitud dos amb una suma de verificació

Una suma de verificació o checksum és un codi lineal particularment utilitzat. Correspon a un codi corrector del qual només la detecció és automatitzable; la correcció s'obté per una demanda de repetició del missatge.

Al missatge inicial se li afegeix una informació codificada, i la informació afegida s'escull d'una manera que faci possible que la congruència de la suma de les lletres de la paraula del codi sigui igual a un valor donat, sovint zero. En l'exemple il·lustrat sobre la figura de dreta el missatge inicial està format per dues lletres, i una paraula del codi en conté tres; si el missatge inicial és 00, la paraula del codi transmès és 000; si el missatge és 01, la paraula del codi és 011. Les quatre paraules possibles del codi s'il·lustren pels punts verds de la figura.

Si es produeix un únic error sobre qualsevol de les tres lletres de la paraula del codi, el missatge rebut correspon a un punt negre; en aquest cas, el receptor sap que ha de demanar la renovació de la transmissió. Aquesta configuració és anàloga, sigui quina sigui la longitud de la paraula del codi. Sovint, la que es fa servir és una longitud igual a vuit, i això permet la transmissió d'un missatge de set lletres. El resultat és idèntic; cada paraula lícita del codi no té al seu costat més que paraules existents fora del codi i, d'aquesta manera, es pot detectar un únic error durant la transmissió. En el cas contrari, sistemàticament, una doble anomalia passa sense ser detectada.

Codi cíclic modifica

Article principal: Codi cíclic
 
Il·lustració d'un codi perfecte

Existeixen certes situacions on la petició de repetició no és possible; per exemple, en un DVD, quan la pols emmascara una determinada informació. En aquest cas, és necessari imaginar codis correctors que no només detecten sinó que, automàticament, també corregeixen els errors.

El mètode que es fa servir consisteix a allunyar les paraules del codi a una distància suficient per localitzar el missatge original bo. La distància entre dos punts correspon al nombre de caràcters a modificar per passar de l'un a l'altre; el gràfic de l'esquerra il·lustra aquesta situació. Els punts verds corresponen a les paraules del codi que, per definició, no presenten cap error; els punts blaus, a les paraules obtingudes quan un únic caràcter és alterat en la transmissió; i els punts vermells, corresponen a dos caràcters que són modificats. En l'esquema, es veu que cada punt blau conté un únic punt verd a una distància d'1, i a cada punt vermell li correspon un únic punt verd situat a una distància de 2; si s'han produït un o dos errors, l'únic punt verd més proper correspon necessàriament al missatge inicial. Un codi com aquest és capaç de protegir fins a dos errors.

L'aritmètica modular subministra solucions òptimes per construir la geometria d'un codi lineal corrector. Com que un espai vectorial no constitueix una estructura suficient per definir un mòdul, s'enriqueix amb una estructura d'anell de polinomis dividits per Xn - 1, on n designa la dimensió de l'espai vectorial. En aquest espai de mòdul, el monomi Xn s'identifica amb el polinomi constant 1. Si la cadena (a0, a1, …, an) és una paraula del codi, llavors ho és igualment de la sèrie (an, a0, a1, …, an-1); per aquest motiu, es parla d'un codi cíclic. La lògica és la mateixa que la d'un codi corrector; existeix la diferència en què la congruència no es defineix sobre un enter sinó sobre un polinomi ciclotòmic amb coeficients en un cos finit.

L'exemple més senzill correspon al codi de Hamming en el que els missatges a transmetre impliquen quatre caràcters, i tres caràcters suplementaris descriuen les redundàncies.

Identitat de Mac Williams modifica

Article principal: Identitat de Mac Williams

El context d'un codi lineal és anàleg al de la criptografia; s'hi troben també espais vectorials de dimensió n sobre un cos finit i un sistema de mòdul de polinomis el polinomi escollit que, sovint, és: Xn + 1.[82] Els caràcters del grup es fan servir, tal com en l'anàlisi harmònica associada.

La identitat de Mac Williams és un exemple arquetípic.[83] Permet la determinació del polinomi enumerador dels pesos del codi dual o, fins i tot, l'estudi de les característiques del codi de Hamming i, amb l'ajuda d'un producte de convolució, s'obté gràcies a l'anàlisi harmònica.

Referències i notes modifica

  1. ↑ Carl Friedrich Gauss. Recherches arithmétiques, 1801 Traducció al francés de M. Poullet-Delisle Éd. Courcier 1807
  2. ↑ Pes exemple la llei de reciprocitat quadràtica a la pàgina 96, o la construcció amb regle i compàs de l'heptadecàgon a les pàgines 429-489 de les Recherches arithmétiques
  3. ↑ Es pot citar el teorema de Wilson (p. 56), o el petit teorema de Fermat (p. 50) de les Recherches arithmétiques
  4. ↑ Pierre Samuel. Théorie algébrique des nombres, Hermann, collection Méthodes, París, 1967. ISBN 2-7056-5589-1
  5. ↑ A. Fröhlich. Galois Module structure of Algebraic integers, Springer-Verlag, Berlín, 1983.
  6. ↑ Chantal David. Cryptographie à clé publique et factorisation Arxivat 2006-12-07 a Wayback Machine., Université Concordia Quebec pàg. 11-17. PDF
  7. ↑ J-M Muller; J-C Bajard. Calcul arithmétique des ordinateurs, Traité Hermes CNRS 2004 «PDF»., pàg. 142-150 i pàg. 181-201. PDF
  8. ↑ Pascal Giorgi. Arithmétique modulaire entière en base polynomiale, Séminaire de l'université de Perpignan 2005 «PDF». Arxivat de l'original el 2007-09-26. [Consulta: 13 juliol 2008].. PDF
  9. ↑ Thomas Plantard. L'arithmétique modulaire pour la cryptographie, Université de Montpelier, 2005 «PDF». Arxivat de l'original el 2012-11-05. [Consulta: 13 juliol 2008].. PDF
  10. ↑ Simon Singh. Histoire des codes secrets, pàg. 324-329
  11. ↑ Pascal Paillier. "Low-cost double-size modular exponentiation or how to stretch your cryptoprocessor", GEMPLUS, ENST Lecture notes in computer science Springer, Berlín, 1973
  12. ↑ T. L. Heath. "The thirteen books of Euclid's Elements", The Mathematical Gazette, Vol. 6, num. 92, pàg. 98-101, maig de 1911.
  13. ↑ Euclides. Eléments Livre IX, Proposition 36
  14. ↑ Les dates del naixement i de la mort de Diofant no es coneixen bé cf Norbert Schappacher (2005). Diophantus of Alexandria: a Text and its History Arxivat 2008-04-25 a Wayback Machine.. PDF
  15. ↑ Sun Zi. Sunzi suanjing. Un manual de matemàtiques vers l'any 300
  16. ↑ J.-C. Martzloff. Histoire des mathématiques chinoises, pàg. 129 Masson, 1987
  17. ↑ Qin Jiushao Shushu Jiuzhang. Traité de mathématique en neuf chapitres, 1247
  18. ↑ Ho Peng Yoke. Li, Qi, and Shu An Introduction to Science and Civilization in China, pàg. 89, Hong Kong University Press, 1985
  19. ↑ K. Chemla. Similarities between chineese and arabic mathematical writings: (I) root extraction, Arabic science and Philosophy, 4, núm. 2, pàg. 207-266, 1994.
  20. ↑ H-J Ilgauds. "Aryabhata I", a H. Wussing i W. Arnold: Biographien bedeutender Mathematiker, Berlín, 1983.
  21. ↑ A. Keller. Un commentaire indien du VIIe siècle, tesi de la Université de Paris VII «PDF».. PDF
  22. ↑ S. S. Prakash Sarasvati. A critical study of Brahmagupta and his works, Delhi, 1986.
  23. ↑ S. Pines. Studies in Arabic versions of Greek texts and in Medieval science, Leiden, 1986.
  24. ↑ R Rashed. Entre arithmétique et algèbre: Recherches sur l'histoire des mathématiques arabes, París, 1984.
  25. ↑ 25,0 25,1 L'âge d'or des sciences arabes, pàg. 69.
  26. ↑ J. L. Berggren. Episodes in the Mathematics of Medieval Islam, pàg. 70-71, Springer, 1986.
  27. ↑ J. N. Crossley i A. S. Henry. "Thus spake al-Khwarizmi: a translation of the text of Cambridge University Library", Historia Math. 17 (2), pàg. 103-131, 1990.
  28. ↑ F. J. Carmody. Thabit b. Qurra, Four Astronomical Tracts in Latin, Berkeley, 1941.
  29. ↑ R. Rashed. bn al-haytham et le théorème de Wilson, Archive for History of Exact Sciences, Springer, Berlín, Vol 22, núm. 4, pàg. 305-321, desembre de 1980.
  30. ↑ Pierre de Fermat. Correspondance, 3 de gener de 1657.
  31. ↑ Pierre de Fermat. Correspondance a Marin de Mersenne, 25 de desembre de 1640.
  32. ↑ Pierre de Fermat. Remarques sur Diophante, per Pierre Samuel, fill de Fermat, 1670.
  33. ↑ Andrew Wiles (1995). "Modular elliptic curves and Fermat's last theorem Arxivat 2011-05-10 a Wayback Machine.," Annals of Mathematics, 141 (3), pàg. 443-551.  PDF
  34. ↑ Pierre de Fermat. Correspondance à Frénicle de Bessy, 18 d'octubre de 1640.
  35. ↑ Leonhard Euler. Correspondance (a Goldbach), 12 d'abril de 1749.
  36. ↑ Leonhard Euler. Algèbre, 1770.
  37. ↑ Patrice Naudin; Claude Quitté. Algorithmique algébrique, Masson, 1992.
  38. ↑ Johann Peter Gustav Lejeune Dirichlet. Démonstration du théorème de Fermat et de Wilson ("Compte-rendu par Cournot de quelques mémoires d'Abel, Jacobi et Lejeune-Dirichlet", a Journ. der Mathemat., de M. Crelle, vol 3, núm. 4), 1829, vol 11, pàg. 153-157.
  39. ↑ Johann Peter Gustav Lejeune Dirichlet. "Recherches de diverses applications de l'analyse infinitésimale à la théorie des nombres", J. Reine Angew math., (19) 1839, ibid (21) 1840.
  40. ↑ W. Ahrens. "Briefwechsel zwischen C. G. J. Jacobi und M. H. Jacobi", The Mathematical Gazette, vol. 4, núm. 71, pàg. 269-270, 1908.
  41. ↑ Adrien-Marie Legendre. Essai sur la théorie des nombres, Duprat, París, 1798.
  42. ↑ Ferdinand Eisenstein. "Application de l'Algèbre à l'Arithmétique transcendante", Journal de Crelle. Berlín 1845.
  43. ↑ Adrien-Marie Legendre. Théorie des nombres, Firmin Didot 3a edició, 1830.
  44. ↑ Auguste Kerckhoffs. "La cryptographie militaire", Journal des sciences militaires, vol. IX, pàg. 5–83 i pàg. 161–191, 1883.«Enllaç».
  45. ↑ Alain Tap. Cryptographie, Laboratoire d'informatique théorique et quantique Université de Montréal «PDF». Arxivat de l'original el 2004-12-07. [Consulta: 13 juliol 2008].. PDF
  46. ↑ Don Coppersmith (1994). "The data encryption standard (DES) and its strength against attacks", IBM Journal of Research and Development; 38 (3), pàg. 243–250 «PDF».. PDF
  47. ↑ 47,0 47,1 Whitfield Diffie; Martin Hellman (1976). "New directions in cryptography", IEEE Trans. Inform. Theory, IT-22, 6, pàg. 644-654, accessible en línia «PDF». PDF
  48. ↑ Ron Rivest, Adi Shamir, Len Adleman. "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" Arxivat 2007-01-27 a Wayback Machine., Communications of the ACM, Vol. 21 (2), pàg.120–126., 1978.  PDF
  49. ↑ Laurent Bloch. Les systèmes d'exploitation des ordinateurs. Histoire, fonctionnement, enjeux, Vuibert, 2003, ISBN 2-7117-5322-0
  50. ↑ Thomas Plantard. Arithmétique modulaire pour la cryptologie, Tesi de la Université de Montpellier II, 2005 «PDF». Arxivat de l'original el 2007-09-30. [Consulta: 13 juliol 2008]. PDF
  51. ↑ Claude Shannon. "A Mathematical Theory of Communications", Bell System Technical Journal, vol. 27, pàg. 379-423, 623-656 1948
  52. ↑ Richard Hamming. "Error Detecting and Correcting Codes", Bell System Tech. Jour., 29, 150-163, 1950.
  53. ↑ R. C. Bose i D. K. Ray-Chaudhuri. "On a class of error-correcting. binary group codes", Inform. Control, vol. 3, pàg. 68-79, 1960.
  54. ↑ J. Velu. Méthodes mathématiques pour l'informatique, Dunod informatique, 1987.
  55. ↑ Denning, P.J. «Computer Science: The Discipline». Encyclopedia of Computer Science, 2000. Arxivat de l'original el 2006-05-25 [Consulta: 13 juliol 2008]. PDF
  56. ↑ Jean Berstel; Jean-Éric Pin; Michel Pocchiola. Mathématiques et informatique: exercices résolus, vol. 2 McGraw-Hill France, 1991.
  57. ↑ Adrien-Marie Legendre. "Recherches d'Analyse Indéterminée", Hist Acad Roy des Sciences (1785/1788)
  58. ↑ Carl Friedrich Gauss. Recherches arithmétiques, 1801, Traducció de M. Poullet-Delisle, Ed. Courcier, pàg. 56, 1807.
  59. ↑ Carl Friedrich Gauss. Recherches arithmétiques, 1801, Ed. Courcier, pàg. 34, 1807.
  60. ↑ Carl Friedrich Gauss. Recherches arithmétiques, 1801, traducció de M. Poullet-Delisle, Ed. Courcier, pàg. XV, 1807
  61. ↑ Vegeu, per exemple, la biografia d'Eisenstein a St. Andrew
  62. ↑ André Weil. Elliptic Functions according to Eisenstein and Kronecker, Springer, 1999 ISBN 978-3-540-65036-2
  63. ↑ Joseph Fourier. "Mémoire sur la propagation de la Chaleur dans les corps solides", Nouveau Bulletin des sciences par la Société philomathique de Paris, núm. 6, pàg. 112-116, 1807.
  64. ↑ Évariste Galois. "Sur les conditions de résolubilité des équations algébriques", Journal de Liouville, 1846.
  65. ↑ Ernst Kummer. "Sur la théorie des nombres complexes", Comptes Rendus des Séances de l'Académie des Sciences, París, 1847.
  66. ↑ A. Shields. "Lejeune Dirichlet and the birth of analytic number theory: 1837-1839", The Mathematical Intelligencer núm. 11, 1989, p 7-11.
  67. ↑ Bernhard Riemann. "Über die Anzahl der Primzahlen unter einer gegebenen Grösse", Rapports mensuels de l'Académie de Berlin, 1859.
  68. ↑ Jean-Paul Delahaye. Merveilleux nombres premiers, Pour la Science 2000, pàg. 222-224 ISBN 2-84245-017-5
  69. ↑ Christine Bachoc. Cours de cryptographie symétrique pàg. 3, Université de Bordeaux I. PDF
  70. ↑ Wagner, David; Schneier, Bruce (novembre de 1996). "Analysis of the SSL 3.0 Protocol". The Second USENIX Workshop on Electronic Commerce Proceedings, USENIX Press  PDF
  71. ↑ La tria dels noms segueix una tradició.
  72. ↑ Kaisa Nyberg. "Differentially uniform mappings for cryptography", a Advances in Cryptology - EUROCRYPT'93, vol. 765, Lecture Notes in Computer Science. Springer-Verlag, 1994. «PDF». PDF
  73. ↑ «FIPS 197, Advanced Encryption Standard (AES)». Arxivat de l'original el 2015-04-07. [Consulta: 26 octubre 2012]., pàg. 10-12.  PDF
  74. ↑ Niels Ferguson, Richard Schroeppel, Doug Whiting. "A simple algebraic representation of Rijndael". Proceedings of Selected Areas in Cryptography, 2001, Lecture Notes in Computer Science, pàg. 103–111, «Enllaç». Arxivat de l'original el 2016-01-16. [Consulta: 13 juliol 2008].
  75. ↑ Philippe Bayart Comment fabriquer de grands nombres premiers?,a Bibmath.net
  76. ↑ Jean-Paul Delahaye. "Merveilleux nombres premiers", a Pour la Science 2000, pàg. 215 ISBN 2-84245-017-5
  77. ↑ Jean-Paul Delahaye. "Merveilleux nombres premiers", a Pour la Science 2000, pàg. 302 ISBN 2-84245-017-5
  78. ↑ Carl Pomerance. "A Tale of Two Sieves", Notices of the AMS Vol. 43, 1996, pàg. 1473-1485.«PDF». PDF
  79. ↑ Vegeu, per exemple, els articles sobre "le chiffrement à flot" d'Anne Canteaut, extrets de la Encyclopedia of Cryptography and Security, H. van Tilborg ed., Springer, 2005, accessible a «PDF». PDF
  80. ↑ D. Stinson. Cryptographie théorique et pratique, Int. Thomson Pub. France, 1996.
  81. ↑ Simon Singh. Histoire des codes secrets, Poche pàg. 345, 1999
  82. ↑ M. Klemm. "Etablissement de l'identité de Mac Williams pour les codes linéaires sur l'anneau des entiers modulo m, avec une fonction poids sous forme de polynôme homogène", Archiv der Mathematik, vol. 49, núm. 5, pàg. 400-406, 1987.
  83. ↑ F. J. Mac Williams i J. J. A. Sloane. The theory of error correcting codes, North-Holland, 1977.

Bibliografia modifica

  • J-C Martzloff. Histoire des mathématiques chinoises, Masson 1988 (ISBN 2-225-81265-9)
  • T. Hayashi. The Blackwell Companion to Hinduism, Basil Blackwell 2005 (ISBN 978-1-4051-3251-0)
  • R Rashed. Entre arithmétique et algèbre: Recherches sur l'histoire des mathématiques arabes Les Belles Lettres, París 1984 (ISBN 2-251-35531-6)
  • A. Djebbar; D Savoie; D. Jacquart; M. El Faïz. L'Âge d'or des sciences arabes, Actes Sud / Institut du monde arabe, oct. 2005 (ISBN 2-7427-5672-8)
  • M. S. Mahoney. The mathematical career of Pierre de Fermat, 1601 - 1665, Princeton Univ. Press 1994 (ISBN 0-691-03666-7)
  • Simon Singh. Le Dernier Théorème de Fermat, Hachette Littérature 1999 (ISBN 978-2-7096-1854-0)
  • G. W. Dunnington. Carl Friedrich Gauss: Titan of Science, The Mathematical Association of America 2003 (ISBN 0-88385-547-X)
  • Simon Singh. Histoire des codes secrets, Lattes 1999 (ISBN 978-2-7096-2048-2)
  • Zemor Gilles. Cours de cryptographie, Cassini 2000 (ISBN 978-2-84225-020-1)
  • Michel Demazure. Cours d'algèbre. Primalité Divisibilité Codes, Cassini 1997 (ISBN 978-2-84225-000-3)

Enllaços externs modifica

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Aritmètica modular


Obtingut de «https://ca.wikipedia.org/w/index.php?title=Aritmètica_modular&oldid=32557971»