Interior Alg Comp III

download Interior Alg Comp III

of 192

  • date post

    31-Dec-2015
  • Category

    Documents

  • view

    50
  • download

    0

Embed Size (px)

description

math

Transcript of Interior Alg Comp III

  • Horvth Alexandru

    Introducere

    n algebra computationala

    EDITURA DIDACTIC I PEDAGOGIC, R.A.

    aplicatii n teoria numerelor, criptografie, singularitati

  • DaneTypewritten TextISBN 978-973-30-3372-1

  • Memoriei prinilor mei

  • Prefa

    C cartea de fa se nscrie n seria celor dou volume aprute an-terior la aceast editur sub acelai titlu principal: "Introduc-ere n algebra computaional". Diferena este reprezentat desubtitlul volumului, de aceast dat ind alese alte trei capitole

    nsemnate ale matematicii spre a subiectul unei abordri computaionale:teoria numerelor, teoria ecuaiilor difereniale i teoria singularitilor. Simplaenumerare a acestor trei capitole vaste ale matematicii arat c n dimensi-unea restrns a prezentului volum nu poate vorba dect de o prezentarecu caracter introductiv. Cu toate acestea autorul are sperana c modul deabordare cu accentele computaionale aduse n prim plan, care merg pn laprezentarea unor aplicaii concrete relevante, este n msur s confere att ojusticare a prezentrii materialului sub aceast form, ct i s ofere cititoru-lui o perspectiv modern i atrgtoare. Aceste idei au o dezvoltare sucientde larg n capitolul introductiv.

    n cadrul acestei scurte prefee n conformitate cu tradiia deja nceten-it autorul gsete potrivit s reia textual cteva din ideile principale dinprefaa celor dou volume anterioare. Acestea exprim punctul de vedere alautorului i spiritul n care se abordeaz coninutul volumului de fa.

    Termenul "computaional" acoper n percepia autorului nu att calculnumeric, ct mai degrab simbolizeaz strdania de a face efective rezultateleclasice sau noi ale ntregii matematici. Cititorul este invitat a se gndi de dataaceasta spre exemplu la problema calculului factorilor unui numr natural cumulte cifre, la calculul formulei funciei care constituie soluia unei ecuaiidifereniale n opoziie cu valorile numerice ale acestei funcii ntr-un set depuncte ale domeniului su de deniie, sau la "calculul" structurii topologicedeci ale unor invariani asociai unor obiecte geometrice complicate cum suntsingularitile izolate ale unor hipersuprafee complexe.

    Strdania de a face construciile ideatice ale matematicii ct mai ope-raionale este favorizat cu succes de mijloacele de calcul din ce n ce maiperformante de care dispunem astzi. Aceste mijloace ne permit, pe de o

    5

  • 6parte, implementarea unor algoritmi din ce n ce mai sosticai, pe de altparte, lrgesc esenial aria experimentrilor n cercetarea fundamental mate-matic. Autorul s-a strduit ca acest impact al calculelor efective s constituieo caracteristic dominant i a prezentului volum.

    Algebra computaional reprezint un capitol relativ nou al matematicii,dar sintagma simbolizeaz o direcie de dezvoltare recent deosebit de vigu-roas a ntregii matematici. n clasicarea capitolelor matematicii, promovatde AMS, Societatea de Matematic American, se poate constata c n recentaversiune a clasicrii MSC2010 apare deja de peste 40 de ori sintagma "com-putaional", n legtur cu, practic, toate capitolele majore ale matematicii,sugernd o amploare deosebit a studiului aspectelor computaionale. Sin-tagma "algebr computaional" se extinde generic, ntr-o oarecare msur,asupra tuturor acestora, fapt care justic apariia n paginile unui aceluiaivolum a diversitilor de aplicaii, aa cum se ntmpl i n cazul volumuluide fa.

    Cartea conine, n afara unui capitol introductiv, trei capitole majore de-dicate cte unui domeniu de aplicaie a algebrei computaionale.

    Primul capitol, este o incursiune n teoria computaional a numerelor. Seprezint mai nti conceptele de baz conceptele de baz ale teoriei clasice alenumerelor, cteva noiuni i rezultate importante legate de numere prime, di-vizibilitate, congruene i resturi ptratice. Exemplele concrete sunt calculaten mediul oferit de un sistem de calcul simbolic consacrat. Aplicaiile rele-vante destul de numeroase includ teste de primalitate att probabilistice cti deterministe factorizarea numerelor ntregi, ecuaii diofantice particulare,calculul logaritmului discret.

    Al doilea capitol se ocup de criptograe. Criptograa studiaz metodede codicare a informaiei cu scopul de a o proteja, de a o face neinteligibil,indescifrabil pentru toi cei pentru care nu i se adreseaz.

    Prezentm n acest capitol metoda de criptare simetric cu chei publiceRSA. Ne limitm la prezentarea principiilor i algoritmilor matematici. Im-plementrile cocrete, standardele utilizate n practic DES, AES etc. pot conoscute din documentaiile existente publice de pe internet. Aplicaii alemetodelor de criptarea cu chei publice, sunt vitale n asigurarea securitiinformaei n format electronic.

    Al treilea capitol este dedicat unui domeniu dicil: teoria singularitilor.Acesta se a la intersecia unor domenii clasice i vaste care includ geome-tria i topologia algebric, analiza complex multidimensional, geometrie itopologie diferenial, pentru a aminti cteva dintre acestea. Singularitileizolate ale hipersuprafeelor complexe sunt descrise de spaii topologice com-plicate, caracterizate de invariani topologici i analitici. Aceti invarianisunt reprezentai n grafurile de rezoluie. Scopul acestui capitol este de a

  • 7prezenta acest subiect pn la nelegerea a ctorva calculelor efective posibilen pachetul dezvoltat special pentru acest domeniu, pachetul Singular.

    Capitolele i ale acestui volum sunt relativ independente. Puntea de leg-tur ntre ele i caracteristica general a ntegului text este prezena n ecarecapitol a aplicaiilor computaionale. Exemplele concrete sunt numeroase, eleind realizate n pachetele de programe care sunt dintre cele mai potrivite pen-tru problema respectiv. n felul acesta cititorul este invitat implicit ca n locs se lase prad unor prejudeci care se formeaz involuntar prin ctigareaunei dexteriti n utilizarea confortabil dar exhaustiv a unui mediu de pro-gramare anume, s i pstreze curiozitatea deschis spre alegerea soluiei celmai performante pentru problema respectiv. Cartea nu conine nici de dataaceasta iniiere n utilizarea acestor programe, documentaiile care nsoescaceste pachete sunt oricum accesibile de pe internet. Capitolele sunt nsoitede un numr mic de probleme propuse, care au fost compuse cu un ochi sprerezolvarea lor sprijinit de aceste programe.

    n ncheierea acestei scurte prefee, voi repeta i aici mrturisirea fcutn prefaa primului volum: cartea de fa nu se nate neaprat i exclusiv dinimperativul de a comunica experiene acumulate, ci i din propria nevoie aautorului de a nva. Autorul mprtete ideea c ncercarea de a-i nvape alii este o cale de aprofundare a cunotinelor proprii. Consider aadarecare cititor al acestor pagini drept un partener, care m nsoete n cltoria sper fascinant pe care o propun prin rndurile de fa.

    Autorul

  • Cuprins

    Introducere 11

    1 Teoria numerelor 131.1 Fundamente teoretice . . . . . . . . . . . . . . . . . . . . . . . 13

    1.1.1 Cel mai mare divizor comun. Algoritmul lui Euclid extins 161.1.2 Numere prime. Teorema fundamental a aritmeticii . . 221.1.3 Inelul ntregilor lui Gauss . . . . . . . . . . . . . . . . . 281.1.4 iruri recurente. Numerele lui Fibonacci . . . . . . . . . 341.1.5 Congruene. Teorema chinezeasc a resturilor . . . . . . 381.1.6 Teorema lui Fermat, Wilson, i Euler . . . . . . . . . . . 461.1.7 Resturi ptratice . . . . . . . . . . . . . . . . . . . . . . 621.1.8 Curbe eliptice . . . . . . . . . . . . . . . . . . . . . . . . 74

    1.2 Teste de primalitate . . . . . . . . . . . . . . . . . . . . . . . . 911.2.1 Testul Fermat . . . . . . . . . . . . . . . . . . . . . . . . 911.2.2 Testul Miller-Rabin . . . . . . . . . . . . . . . . . . . . 1011.2.3 Testul Agrawal-Kayal-Saxena . . . . . . . . . . . . . . . 1031.2.4 Teste bazate pe curbe eliptice . . . . . . . . . . . . . . . 105

    1.3 Factorizarea numerelor . . . . . . . . . . . . . . . . . . . . . . . 1071.3.1 Metoda a lui Pollard . . . . . . . . . . . . . . . . . . . 1071.3.2 Metoda p 1 a lui Pollard . . . . . . . . . . . . . . . . . 1101.3.3 Algoritmul ECM al lui Lenstra . . . . . . . . . . . . . . 112

    1.4 Probleme propuse . . . . . . . . . . . . . . . . . . . . . . . . . . 122

    2 Criptograe 1232.1 Criptare RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1242.2 Criptare ElGamal . . . . . . . . . . . . . . . . . . . . . . . . . . 1282.3 Probleme propuse . . . . . . . . . . . . . . . . . . . . . . . . . . 129

    3 Teoria singularitilor 1313.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1323.2 Topologia lui (X,x) . . . . . . . . . . . . . . . . . . . . . . . . 134

    9

  • 10 CUPRINS

    3.2.1 Nodul lui (X,x) . . . . . . . . . . . . . . . . . . . . . . 1343.2.2 Clasicarea topologic a brrilor de drepte complexe

    peste suprafee compacte Riemanniene . . . . . . . . . . 1363.2.3 Preliminarii analitice . . . . . . . . . . . . . . . . . . . . 138

    3.3 Singulariti complexe . . . . . . . . . . . . . . . . . . . . . . . 1403.3.1 Singulariti ct . . . . . . . . . . . . . . . . . . . . . . 143

    3.4 Rezoluia singularitilor . . . . . . . . . . . . . . . . . . . . . . 1453.4.1 Graful de rezoluie . . . . . . . . . . . . . . . . . . . . . 147

    3.5 Rezoluia lui f : (X,x) (C, 0) . . . . . . . . . . . . . . . . . . 1483.5.1 Graful de rezoluie scufundat al f : (X,x) (C, 0) . . 1493.5.2 Proprietile topologice ale lui Y . . . . . . . . . . . . . 150

    3.6 Comentarii i exemple . . . . . . . . . . . . . . . . . . . . . . . 1533.7 Matricea de intersecie . . . . . . . . . . . . . . . . . . . . . . . 1563.8 Singulariti ale curbelor . . . . . . . . . . . . . . . . . . . . . . 1573.9 Construcia tubular . . . . . . . . . . . . . . . . . . . . . . . . 158

    3.9.1 Fibratul de disc tubular . . . . . . . . . . . . . . . . . . 1583.9.2 Invariani topologici ai lui LX via graful de rezoluie . . 1603.9.3 Exemple . . . . . . . . . . . . .