ALTE DOCUMENTE
|
|||||||||
Aspecte matematice si computationale
Vom discuta aici cateva articole ce trateaza complexitatea computationala a criptografiei cu chei publice.
Baza securitatii acestor sisteme este data de imposibilitatea computationala a criptoanalizei in contradictie cu relativa lor usurinta in codare/decodare.Vom analiza cateva probleme ce se regasesc in acest context.
De altfel au fost incluse aici ca fundal aspecte teoretice legate de stiinta computerelor necesare tratarii problemelor legate de complexitatile computationale ale criptologiei si ale criptoanalizei,precum si testele
"zero-knowledge" si schemele relationale aferente.
Aceste discutii pot folosi la intelegerea bazelor securitatii criptografiei cu chei publice.
De asemenea,aceste discutii pot arunca o lumina asupra aspectelor practice ale alegerii dimensiunilor cheilor,asupra alegerii numarului de biti ale componentelor publice si private.
Complexitate computationala si criptocomplexitate
Un sistem criptic ideal va trebui sa aiba proprietatea de a fi cifrat si descifrat usor ,dar criptanaliza sa nu poata fi realizata computational.In practica,aceasta se reduce de obicei la considerarea ca operatia de codare/decodare va trebui executata in timp polinomial,in timp ce un sistem de criptare ideal se va executa in timp exponential.
Detaliat aceasta se reduce la considerarea timpului criptianalitic ca ofunctie exponentiala ce are ca valori timpii de codare/decodare.
Din pacate,este dificil de determinat cand acest criteriu tine de practica.Aceasta deoarece este in general dificil de precizat limita inferioara nepolinomiala a timpuluinecesar criptoanalizei (sau calcului in general) chiar in cazul in care acest proces se reduce la o problema simpla sau bine cunoscuta.
In unele cazuri aceste din urma probleme au fost studiatede secole,dar complexitatea lor computationala e inca necunoscuta.
De fapt,oricand vom incerca sa determinam complexitatea relativa a unei criptoanalize vom intalni problema determinarii cu precizie a limitei inferioare in calcule.
De altfel, o analiza a securitatii si eficientei sistemelor cu chei publice vom lua la socoteala nu numai timpui necesar codarii/decodarii contra timpului prevazut pentru criptoanaliza,dar si alti parametrii precum marimea cheii,timpul de generare a unei chei sau intinderea datelor.
Dezvoltarea teoriei ce caracterizeaza impreuna securitatea si capacitateade punere in practica pare foarte provocatoare.
Teoria clasica a complexitatii
Vom face aici o scurta prezentare a unor notiuni din teoria complexitatii calculului (calculul computational ).In sectiunea C unele notiuni vor fi tratate in detaliu.
O incercare de formalizare a studiului unor probleme dificile este teoria NP-intregita.
Clasa P este definita ca fiind clasa de decizii a problemelor rezolvate in timp polinomial printr-un algoritm determinist.Acesteia din urma ii este necesara un algoritm executabil pe o masina de calcul secvential.Un algoritm nedeterminist este un concept efemer:acesta este in esenta executabilprin intermediul unei masini cu paralelism nelimitat.Aceasta se traduce prin posibilitatea explorarii in paralel a unui numar nelimitat de posibilitati.Spre exemplificare vom presupune un set de n articole ce vor fi sortate pentru a se gasi un anumit articol dat.Cel mai rau caz de complexitate deterministica este n,numarul de operatii necesare unei masini secventiale pentru a verifica toate cele n articole.
In contrast 1 este cazul cel mai simplu de complexitate nedeterministica,in timp ce o masina cu paralelism nelimitat poate verifica toate cele n articole in paralel indiferent de numarul n ales.
Clasa NP este clasa de decizii de rezolvare a problemelor in timp 22222v2116w polinomial prin intermediul unui algoritm nedeterminist.
Poate singura principala problema in teoria calcului computational este de a decide daca P=NP.Problemele din NP-complete sunt cele mai dificile subclase din NP,avand proprietatea ca daca in cazul in care o subclasa apartine P atunci P=NP.Multe probleme de cautare combinatorie clasica pot avea o formulare in NP-complete.Calatoria vanzatorului sau problema rucsacului sunt exemple dintr-o lunga lista.
Clasa problemelor dificile NP sunt de acelasi gen cu cele de mai sus uneori chiar mai dificile decat acestea.Unele din acestea sunt atat de dificile incat nici un algoritm nu le poate solutiona,fiind deci indecidabile.
Unele probleme nu pot apartine clasei NP.Un exemplu este problema opririlor.O tratare formala mai detailata necesita o baza de calcul specializata precum o masina Turing.
Folosirea clasei de probleme NP-complete pentru a genera chei publice pentru criptosisteme a fost sugerata in [DIFF 76b].Mai tarziu aceasta abordare a fost materializata sub forma capcanei rucsacilor.Se cunoaste,totusi,ca principalele capcane au fost depasite,ciuda continuitatii dificultatii de integrare a problemelor in clasa NP-complete.doua explicatii separate pentru acest fenomen.Inainte de toate,in principalele cazuri nu a fost dovedit ca securitatea sistemelor cu chei publice este echivalenta cu dificultatea integrarii problemei.
In al doilea caz,e important de retinut ca teoria clasica a complexitatii computationale se regaseste in jurul punctului reprezentat de cazurile problema ale complexitatii.
Rabin [RABI 76] precizeaza ca aceste masuri au o relevanta limitata in analiza complexitatii criptanalizei,intrucat un criptosistem trebuie sa fie imun la penetrare in orice imprejurare.
Incercari de formalizare a notiunii de "aproape-peste-tot-tare" au fost facute(e.g.[GRCL 88]).O prima caracterizare a fost sugerata de Shomir care a cuantificat aceasta notiune definind o masura complexa C(n,a),pentru algoritmi,astfel:C(n,a) este o masura pentru un algoritm daca cel putin o parte "a" a problemei in cazul n dimensional poate fi rezolvata de algoritm in timpul C(n,a).
De exemplu,un algoritm de cautare a unui factor al numarului n va putea avea complexitatea C(n,1/2)=o(1),intrucat n are 50% sanse sa fie egal cu 1.Totusi,unele cercetari au deocamdata unele neajunsuri,neputand deci alcatui un cadru de intelegere a problemelor,desi acestea pot fi folositoare in anumite cazuri particulare.
Alte exemple simple arata diferenta intre cazurile dificile si cele de complexitate medie:algoritmii de sortare a n articole sunt deseori date presupunand ca articolele sunt aranjate intamplator, toate cele n! aranjamente au probabilitate egala.
Daca fisierul are un cuvant-origine real este un caz fericit decat daca fisierul este deja sortat in particular.Un algoritm optim poate anticipa aceste situatii si poate folosi o strategie adaptata.
In practica,un criptosistem a carui analiza criptografica are o complexitate polinomiala medie este in general putin dificil,lucrul fiind adevarat atata timp cat orice fractie masurabila in orice conditii permite o criptoanaliza in timp polinomial.Astfel nu exista nici o legatura predeterminata intre spargerea unui sistem si dificultatea de a subordona o problema.
De exemplu,exista o.multitudine de tehnici heuristice ce incearca sa aproximeze solutiile problemelor clasei NP-complete.Asemenea tehnici nu pot converge in timp polinomial la solutii exacte,dar pot sparge criptosisteme similare.
In trecere remarcam ca unii autori au incercat folosindu-se de notiunile Diffie/Helman sa utilizeze problemele din clasa NP-complete pentru a construi sisteme.
E interesant de stiut daca asemenea sisteme pot fi facute practice.
A.4.Algoritmi probabilistici
O alta importanta distinctie dintre teoria clasica a complexitatii si criptosisteme este ca teoria clasica a algoritmilor nu cuprinde algoritmi probabilistici,si care pot da rapid solutii la probleme in multe cazuri dar nu pot rezolva probleme aflate in anumite conditii.De asemenea acestea pot da solutii probabile,dar nu neaparat corecte.
Asemenea algoritmi sunt improprii in multiple situatii precum cazul alegerii unui timp de control real,caz in care raspunsul trebuie garantat intr-o perioada fixata de timp sau unde este necesar ca solutiile sa fie verificate.Totusi,acestea sunt unelte puternice atat in criptografie,cat si in criptanaliza.
Asa cum gasim in [RABI 76],algoritmii probabilistici nu pot fi masurati prin criterii clasice,care se aplica in cazurile dificile de functionare [runtime].In schimb,algoritmii probabilistici pot implica o ................ [tradeoff] intre timpul de executie si incredere(securitate).
Spre exemplificare,principalele numere au toate factori mici.Daca un algoritm foloseste acest factor el poate termina rapid cele mai multe date de intrare,dar ii va lua un timp exponential cand .
Modelul clasic al masinilor Turing a fost extins folosindu-se modelele probabilistice Gill.
Acestea s-au dovedit valabile in analiza sistemelor criptografice.
Gill a modelat sistemele computationale probabilistice prin extinderea modelului clasic al masinilor Turing la masini Turing probabilistice.Acesta s-a dovedit valabil in analiza sistemelor criptografice si a schemelor probabilistice de incifrare.
A.5.Statutul unor probleme specifice
Securitatea multor criptosisteme importante mentionate in aceste articole depinde de dificultatea unor probleme a caror caracter complex le fac nerezolvabile.Aceste probleme includ numere factoriale si logaritmi discreti.
Importanta problemelor din subclasele NP-complete se poate vedea din urmatorul caz :daca se stie ca o problema apartine NP-ului,dar nu se stie daca apartine lui NP-complete,o solutie a problemei in timp polinomial (plasand problema in P) nu va implica ca problemele din categoria 'vanzatorului ambulant' apartin clasei P.
O a doua clasa de prima importanta este co-NP,clasa problemelor complementare NP-ului.De exemplu,complementul deciziei cand n este prim este decizia daca n este compus.De fapt numerele prime si numerele compuse se gasesc in ambele clase NP si co-NP.Unii experti considera ca P este rezultatul intersectiei NP cu co-NP.De exemplu :programarea liniara se stia ca apartine ambelor clase cu mult inainte de a fi fost rezolvata problema ei,eventual s-a aratat ca este inclusa in P prin metoda elipsoidului.Acestea ilustreaza ca va fi desigur de dorit sa avem criptosisteme disponibile bazate pe probleme NP-complete.
O buna perspectiva a statutului multor probleme importante in securitatea sistemelor cu chei publice este data in [ADLE 86] si [POME 86].
Se da : L(n)=exp((1+o(1))(ln n+ln ln n)½)
Cand Adleman remarca faptul ca multi algoritmi pentru n factorial au un timp de executie probabilistic gasea pentru acest caz formula L(n[E1] [E2] )c(e.g. [SCHN 84] ).Totusi doar algoritmul lui Dixon a fost riguros analizat.In acelasi fel,o serie de algoritmi pentru logaritmi discreti mod p sunt considerati a tine un timp L(p).Aceste rezultate vor fi vazute fara prea mare incredere in teoria clasica datorita naturii lor probabilistice si a lipsei unor limite superioare a timpilor pentru cazurile dificile sau medii.
In teoria clasica aceste rezultate pot fi valabile,
dar vom remarca ca algoritmii probabilistici sunt mult mai eficienti si mai
putin complecsi, deci mai relevanti in aceasta situatie.Statutul problemelor
extragerii radacinii mod n, rezolvand ecuatia xe
c(mod n), depinde de parametrii (e.g.[SALO 85] ).Un algoritm
probabilistic in timp polinomial pentru aflarea lui x exista daca e, c si n
sunt fixati si n este prim.Daca n este compus din factori necunoscuti, nu
exista un algoritm polinomial, nici unul probabilistic.
Daca e=2 complexitatea este echivalenta cu n factorial (lem.N.3.2.).Daca e>2 statutul este mai putin clar, si ca o consecinta a acestuia este faptul ca echivalenta securitatii unui RSA cu factorialul este putin lamurita.
Brassard a aratat ca logaritmii discreti sunt asociati cu problema deciziei ce se afla la intersectia NP cu co-NP.
Astfel, daca oricare dintre un factorial sau un logaritm discret este NP-hard, se arata pornind de la definitia acestei clase ca problema deciziei asociata cazului apartine de Np si co-NP. Reciproc acestea vor implica NP= co-NP, ceea ce pare de necrezut.
Generalizat, o functie f este definita cu restrictie '' one-way''
daca f este usor computabila, 
nu este computabila,
si f este injectiva si marginita
polinomial. In [BRASS 83] se arata ca daca o functie f cu restrictie ''one-way'' poate exista atunci
P nu este rezultatul intersectiei lui NP cu co-NP cum multi ar crede, si daca f este restrictie ''one-way'' , iar f--1 apartine lui NP-hard atunci
NP=co-NP.
Logaritmul discret este totusi o functie cu restrictie ''one-way''.
Vom concluziona aici ca exista o mica speranta pentru a depasi intrebarile legate de sistemele cu chei publice bazate pe problemele NP-complete.Prospectele folosirii problemelor NP-hard se arata a fi greu de evaluat deocamdata.
Apendix B. Algoritmi si arhitecturi.
Vom face o scurta prezentare a principalelor motive care stau la baza determinarii tipurilor de sisteme soft si hard ce se reteaza la criptanaliza si care se asteapta sa vina de la creatorii de algoritmi si arhitecturi din viitor. Vom mentiona aici cateva exemple existente deja .Aceasta prezentare prezinta o calatorie in stiinta computationala de mare performanta fiind doar o parte din gama mare de aplicatii in criptografie.
In scopul evaluari metodelor de securitate sau descoperirii dimensiunilor cheilor, este necesar sa facem cateva supozitii privind dezvoltarea acestor domenii in viitorul apropiat.
B.1. Tehnologia
In prezent, computerele se bazeaza pe silicon.Deci toate performantele realizabile in domeniul tehnologiei computerelor sunt angrenate de acest material. Intrebarile care se nasc se refera la situatia in care noile tehnologii precum superconductivitatea sau conductivitatea optica vor face ca bazele tehnologiei siliconului sa fie invechite si peste cat timp acest lucru se va intampla.Deocamdata noi nu avem nici o idee, iar aici vom ignora problema.
Tehnologia bazata pe aliajul Ga-As este o alta chestiune. Aceasta tehnologie este deja integrata in unele supercomputere.
Vom prezenta aici cateva diferente intre Ga-As si silicon VLSI :
a) Partile Ga-As au o viteza de comutare mai mare
b) Procesorul de comunicare ''off-chip'' cu Ga-As plateste o pedeapsa relativ mai mare
c) Procesoarele Ga-As au o densitate mai mica.
Intarzierile partilor Ga-As pot fi mai mici de 50 pS, in comparatie cu cele de siliciu ce pot fi de 1 nanosecunda (NMOS).
Similar accesul la chipurile de memorie dureaza mai putin de 500 picosecunde, in timp ce la cele din silicon fenomenul se produce in mai putin de 10 nanosecunde.Caracteristicile indica faptul ca performantele computerelor a caror constructie se bazeaza pe materiale din Ga-As sunt de 20 de ori mai rapide decat cele mai rapide supercomputere bazate pe silicon.Totusi nivelul de integrare al Ga-As este in mod curent mai mic : aproximativ 50000 de tranzistori la un chip, fata de 1 milion la un chip de silicon.Aceasta datorita problemelor de disipare a puterii in circuitele Ga-As, de aici si limitarea de suprafata.Astfel, numarul de chip-uri necesare constructiei unui sistem in Ga-As este mai mare, iar minimizarea numarului de chip-uri este un aspect de prima importanta pentru marea performanta.Comunicarea cu chip-oft-uri in Ga-As este un alt factor al nivelului sistemului.Performantele de varf ale sistemelor computationale sunt limitate de latimea de banda a celui mai putin rapid subsistem.
Propagarea semnalului intre chip-urile unui computer are aceleasi caracteristici atat la sistemele pe baza de Ga-As cat si la cele pe baza de silicon, dar efectul lor relativ este diferit. Comunicarea off-chip este afectata mai mult de efectul gat de sticla in Ga-As.
Solutia folosirii siliconului pentru problemele legate de viteza-CPU contra altor subsisteme include ierarhii de memori ascunse si memorii multinivel nu pot exclude folosirea tehnologiilor bazate pe Ga-As.
Vom concluziona ca pentru moment, tehnologia Ga-As nu este in prezent o amenintare pentru stasndardele de performanta ale tehnologiei cu silicon.
B.2. Modele computationale
Clasic, schemele computationale au fost dominate de modelul Van Neumann, presupunand un singur procesor ce executa o schema unica de instructiuni cu un unic sir de date.Aceasta paradigma si-a atins apogeul prin intermediul computerelor din generatia Cray-1 CRAY 80] si CYBER 205 [CONT 80]. Totusi performantele unitatii cu un singur procesor sunt limitate de viteza sa de ceas. Acest lucru face ca durata unui ciclu sa nu poata fi realizata sub 1 nanosecunda prin intermediul tehnologiei bazata pe silicon. Mai mult decat atat, la aceasta viteza accesarea memoriei devine un ''battleneck''-gat de sticla, fara sa pomenim de I/0. Nu este de preferat ca un uniprocesor sa depaseasca 10 9operatiuni pe secunda, performante ce nu pot fi atinse decat prin intermediul celor mai noi tehnologii.
Exista doua alternative pentru modelul lui Van Neumann : model computational in paralel si cel distribuit.
Modelul paralel se refera la situatia amplasarii intr-o singura unitate a tuturor procesoarelor,pe cand cel distribuit are fiecare procesor in propria cutie.Computerele in sistem paralel pot fi divizate in unitati de memorie, ale caror procesoare au toate o adresa comuna, iar cele in sistem distribuit au adrese separate pentru fiecare procesor. Acest mod de lucru inlatura restrictiile privind numarul de instructiuni si / sau siruri de date ce pot fi procesate concomitent. In teorie aceasta metoda poate produce o putere de computatie nelimitata prin combinarea nodurilor de procesare si unitatilor de memorie intr-un sistem unificat. Totusi, exista trei limitari majore in aceasta privinta :
a) Costul efectiv
b) Reteaua de interconexiuni
c) Algoritmii paraleli.
Costul efectiv luat ca factor singular constituie o piedica pentru dezvoltarea sistemelor paralele. Denelcar HEP (e.g. [KOWA 85 ,Floating Paint T-Series [HAWK 87] si ETA-10 [STEI 87] sunt exemple de sisteme paralele care sau dovedit a nu avea succes comercial. De altfel Cray, un alt concern ce produce supercomputere, a fost sovaitor in politica de extindere a paralelismului pe scara larga, in parte datorita problemelor referitoare la cost. Acesta lucruri au creat o situatie interesanta din punctul de vedere al criptografiei : pot fi cazuri in care o putere computationala suficienta sa sparga un sistem poate fi construita in teorie.
Chiar daca computere cu 1000 sau mai multe procesoare sunt construite, intrebarea care se pune este cand o anumita configuratie poate atinge o putere computationala proportionala cu numarul procesoarelor, problema fiind cresterea liniara a vitezei. Modul de interconectare ale procesoarelor si a memoriei este esentiala. Daca se foloseste sistemul cu memorie divizata, cu procesoare grupate ce acceseaza o zona de memorie comuna formand impreuna module, interferentele produse in caile ce traverseaza retelele sau in incercarile de accesare simultana a modulelor poate cauza efectul ''gat de sticla '' daca se foloseste o latime de banda a retelei mica sau se tine prea mult seama de cost in detrimentul altor parametri.
Daca este folosita o latime mare de banda si o bara transversala '' crossbar '' cu posibilitatea transmiterii concurente a datelor dintre procesoare si module de memorie, numarul de unitati interconectate este limitat de pretul de cost, pret care creste odata cu patratul numarului de procesoare. Acestea par sa arate limitele inerente oricarui sistem de a putea fi extins, faptul implicand performantele uniprocesorului.
O alternativa este de a conecta perechi de procesoare/memorie folosind o retea in forma de hipercub.
Masini de acest gen ce incorporeaza peste 65 536 de elemente de procesare (the Conection Machine [HILL 85] ) cu putere redusa sau peste 1024 de procesoare puternice (the NCUBE/10 [HAYE 86] ) au fost construite, iar sisteme cu peste 32 000 gen Cray-1 au fost propuse. Exista discutii (chiar controverse ) in privinta vitezei de lucru ce poate fi atinsa pe masini cu memorie distribuita.
O alta consideratie se refera la costul efectiv al acestor masini, cost ce creste, dupa cum stim, aproape liniar cu cresterea vitezei.
De asemenea, costul interconectarilor in cazul sistemelor bazate pe modelul hipercubului cresc dupa legea O(n log n), unde n este numarul perechilor procesor/memorie.
O alta preocupare sunt algoritmii. Problema trebuie descompusa pana la nivelul care ii asigura siguranta apartenentei la sistemul paralel sau distribuit de computatie.
Mai mult decat atat, algoritmii pentru masini non-Van Neumann vor fi construiti cu arhitectura individuala pentru o acoperire mai mare. Mai mult decat atat, algoritmii pentru masini ce exclud masinile Van Neumann trebuie construiti pentru arhitecturi individuale mult mai extinse decat cele Van Neumann. Din cauza legaturii inerente dintre performanta si cost poate exista o reala diferenta intre puterea computationala ce poate fi atinsa in teorie si cea realizata in practica (pentru masini destinate pietii ). De zece ani este posibil ca masini ce executa 10 12 operatii pe secunda sa fie constuite cu tehnologia existenta, dar adevarata problema este cea a finantelor.
O alternativa pentru masinile existente este folosirea lor in retele cu distributie computationala completa. Clasa de probleme ce pot fi rezolvate prin intermediul retelelor este restransa, atata timp cat nodurile nu pot comunica in mod continuu (tipic, numai la inceputul si la sfarsitul computatiei ).
Cu toate acestea, in sectiune 4 este notat ca cele mai spectaculoase rezultate in sisteme criptice au fost obtinute prin intermediul retelelor. Aceasta este posibil deoarece multi algoritmi pentru sisteme criptice pot fi total descompusi in parti independente ce nu interactioneaza intre ele. Un exemplu este sita patratica.
Exista posibilitatea asamblarii unor componente de calcul in retea si a crearii unei puteri computationale mai mari decat in orice alt computer nelegat la retele. Inca odata constrangerile sunt foarte realiste.
Proiectantii criptosistemelor trebuie sa incerce sa anticipeze nu numai dezvoltarile algoritmilor si ale arhitecturilor, dar si la marirea puterii computationale, cea care sa poata reasliza eficient sarcini cat mai diverse.
B.3. Cativa algoritmi independenti si implementarea lor
Cea mai mare parte din algoritmii pentru calculul factorial si cel logaritmic sunt de data recenta. O parte importanta dintre acestia nu a fost analizata la functionare. Fara indoiala, unele aspecte ale problemei abia se intrevad. Dele mai optimiste presupuneri pot doar anticipa implicatiile algoritmilor din prezent.
B.3.1. Sita patratica-algoritm factorial
Sita patratica reprezinta o alternativa la recentele metode cu algoritmi avand factori fractii continue. [DAVI 83b] noteaza ca rezultatele fractiilor continue folosesc o precizie considerabila. Sita patratica lucreaza cu reziduuri substantiale, dar implica o extragere de mare precizie. Atat fractiile continue cat si sita patratica au timpii de functionare de ordinul exp(sqrt(c ln n ln n)) cu c=2 pentru fractii continue si c=9/8 pentru sita patratica.
In [DAVI 84] rezultatele implementarii pe masini CRAY X-MP sunt amplu redate. Factorialul unui numar cu 80 de cifre se obtine dupa o ora, iar al unui numar cu 100 de cifre dupa un an. Cheia pentru aceasta partida ar fi utilizarea in conditiile unor anumiti algoritmi si a unei si ale unei arhitecturi date tip masina CRAY a unor vectori specializati.
O alta alternativa este folosirea coputerelor distribuite : Silverman [SILV 87] foloseste sita patrastica implementata prin retea (9 SUN), trei unitati de lucru extragand un factor dintrun numar cu peste 80 de cifre in opt saptamani. Recent, o alta retea lucreaza cu numere ce cuprind 160 de cifre.
Este de retinut ca rezultatele obtinute prin intermediul metodei sitei patratice sunt relevante din punct de vedere criptanalitic. Integrarea unor numere cu peste 155 de cifre, cu forme speciale, se poate face factorial sau prin retea SIAM 90] ). Totusi, aceste rezultate sunt relevante numai indirect pentru sisteme tip RSA, asumarea modulului fiind aleasa corespunzator.
B.3.2. Computabilitatea in campuri finite
Acest subiect a fost exploarat in [BART 63] dar nu vom trece in revista acest demers.
Multiplicarea elementelor in GF(m) afost implementata la nivelul circuitelor prin folosirea unui '' feetback '' liniar de schimbare a registrelor. Totusi, LAWS [LAWS 1] noteaza posibilitatea folosirii matricilor celulare [arrays]. O arhitectura '' pipeline '' pentru multiplicare si inversare este propusa in [WANG 85].
O clasa de algoritmi prezentand un interes particular este cea pentru logaritmi discreti in GP(pn). Cazul n=2 a fost explorat in mod considerabil in BLAK 84],[BLAK 84b],[COPP 84] ).
Logaritmii finiti sunt usor computabili in GF(m) daca m este un factor mic [POHL 78], iar n va trebui ales astfel incat 2n-1 este prim, n=521 (e.g.).
Odlyzko [ODLY 84b] noteaza ca urmatoarea generatie de supercomputere vor putea rezolva cazul n=521.
O tinta speciala este atacarea cazului n=700 prin rezolvarea lui intr-un an. Odlyko remarca in privinta dimensiunilor cheilor cu limite similare, ca GF(p) va fi preferat in locul lui GF(2n), n=2000 fiind echivalent cu p avand aproximativ 750 de biti.
B.3.3. Alti algoritmi
Multe din principalele operatii referitoare la astfel de probleme par sa fie caracterizate printr-o secventialitate inerenta. Un exemplu este acela al caslculului exponential, calculul puterilor n va avea loc in log n pasi fara a se tine seama de numarul de procesoare disponibile. Un alt exemplu clasic este acela al celui mai mare divizor comun. Desi unele rezultate partiale sunt consemnate in [ADLE 86], majoritatea implicastiilor algoritmului lui Euclid nu sunt asteptaste fara a se tine seama de dezvoltarea arhitecturii calculatoarelor.
Multi dintre algoritmii factoriali pot fi tratati in modul paralel. Principala cerinta este existenta unei arhitecturi compatibile.
B.4. Aplicatiile specifice arhitecturilor
Arhitecturi cu destinatie generala ( nespecializata ) precum cele din gama Cray prezinta interes in acest cadru datorita disponibilitatii lor immediate.La o alta extrema se situeaza arhitecturile strans legate de algoritmii ce urmeaza a fi folositi, dar natura lor superspecializata le face greu penetrabile pe piata.
Intre acestea se gaseste clasa de arhitecturi cu succes pe piata, dar cu o natura nespecializata.
Apendix C.
Teoria clasica a computatiei
In sectiunea A un numar de notiuni provenite din teoria clasica a computatiei au fost mentionate.Aici vom face unele precizari privind aceste notiuni din teoria clasica a computatiei.
Un alfabet este un set finit de simboluri.Un sir este o secventa de simboluri din alfabet. Un limbaj este un set de siruri dintr-un alfabet.
Daca S este un alfabet, S* este multimea tuturor sirurilor din S, inclusiv sirurile vide. Concatenarea sirurilor a si b se va scrie ab.Daca A si B sunt submultimi din S*, AB este un set de siruri format prin concatenarea elementelor din A si B.
C.1. Masini Turing
O masina Turing este o cvadrubla (K,S,D,s) unde :
a) S este un alfabet care contine un blank ''= #'', dar nu contine simbolurile L sau R care sunt rezervate miscarii benzilor la stanga sau la dreapta.
b) K este un set de stari ce nu include starea opririlor = h al carei semnal semnifica sfarsitul calculului.
c) Starea initiala = s,apartinand lui K.
d) D : KxS-> (K+)x(S+), unde + semnifica adunarea.
O masina Turing =M poate fi considerata din punc de vedere fizic ca fiind constituita dintr-o unitate de control si o banda.
La un anumit timp, M se poate gasi intr-o anumita stare, iar capul de citire/scriere se va gasi deasupra unui anumit simbol de pe banda.
Daca D(q,a)=(p,b) dupa ce initial capul de citire/scriere a scanat simbolul a, iar M se gaseste in starea q, urmatoarea mutare va initializa starea p.Daca b se gaseste in S capul va seta a :=b fara sa se mute ; altfel daca b=L sau R, in acest caz, capul se va deplasa spre stanga sau spre dreapta. M se opreste cand starea h este activata. Banda nu are, deci, limita la dreapta. Intrarile lui M sunt constituite din siruri. Initial capul este pozitionat peste #, care marcheaza capatul din dreapta al intrarilor. M este, deci, in starea s, prima miscare fiind D(s ).
La un timp anume dat, M se afla in urmatoarea configuratie (q,w,a,u), unde :
a) q=starea (element din K+)
b) w=portiune din banda aflata in stanga capului (element din S*)
c) a=simbolul de sub cap (element din S)
d) u=portiunea din banda aflata in dreapta capului.
O extensie a modelului de baza este model bazat pe o unitate de control a mai multor benzi. Deci, un limbaj acceptat de o masina Turing cu benzi multiple este acceptat din start de o masina Turing cu o singura banda, benzile aditionale nu pot insa mari puterea computationala in aceeasi masura in care se vor mari clasele de limbaje acceptate.
C.2.Masini Turing nedeterministe
Masinile Turing precedente au fost masini deterministe, astfel D fiind o functie :daca D(q,a)=(p,b) atunci urmatoarea stare p si simbolul b erau unic determinate de starea prezenta q si simbolul a.
O masina nedeterminista Turing este definita similar cu exceptia functiei D care acum va fi in urmatoarea relatie :
(KxS)x((K+)x(S+))
D va avea acum mai multe valori,iar o urmatoare configuratie nu va mai putea fi determinata unic,ca pana acum.In consecinta,o data de intrare va avea mai multe iesiri.O secventa de pasi ce pornesc de la un set de intrari date definesc o computatie ;in general mai multe computatii sunt posibile pornind de la o singura data de intrare.
O masina nedeterminista se defineste daca accepta o data de intrare si daca exista o locatie computationala pentru aceasta.Daca ''e'' reprezinta sirul fara nici un element, ''u'' in (d) trebuie sa fie un element din (S*),iar (S-)+ pentru fiecare u=e,insemnand ca banda are toate #'S in dreapta capului de citire/scriere sau ultimul simbol din ''u'',este ultimul simbol,cu exceptia ''blank'',de pe banda aflat in dreapta pozitiei capului de citire/scriere.Acestea dau configuratiei o descriere unica.In particular,daca data de intrare pentru M este w atunci configuratia initiala a lui M este (s,#w,#,e).
M se spune ca se opreste la data de intrare w daca starea h este atinsa din configuratia (s w,#,e) intr-un numar finit de etape.Daca Mse opreste la w,M se numeste ca accepta w.Limbajul acceptat de M este un set de siruri w acceptabile pentru M.
Un limbaj se numeste Turing acceptat,daca poate fi acceptat de o masina Turing.Presupunem ca S este un alfabet ce nu contine #,Y,sau N,L este un limbaj in A* si X este o functie caracteristica .X(w)=Y daca w se gaseste in L,X(w)= N in caz contrar.Daca X este computat prin intermediul unei masini Turing M atunci M se numeste ca va decide (sau recunoaste ) L.
Daca X este o functie caracteristica pentru limbajull L,iar X este computabila Turing,exista o masina Turing ce se va baza pe X,iar L se va numi Turing-decidabila.
Un limbaj acceptat este un set de siruri ce poate fi acceptat de o masina .Uzual se poate spune ca orice limbaj ce poate fi acceptat de o masina nedeterminista va putea fi acceptat de o masina determinista,si vor fi numai cazuri speciale dintr-o multime de cazuri generale.
C.3.Complexitate computationala
Complexitatea timpilor de functionare a masinilor Turing este masurata prin numarul de pasi necesari pentru procesul computational.
Daca T este o functie de numere intregi nenegative,o masina Turing va avea timpul de decizie al unui limbaj L sub forma functiei T(n),indiferent daca w se afla sau nu in L,unde w este lungimea lui u.Daca T este o functie polinomiala atunci L se va numi decidabil in timp polinomial.Daca un limbaj este decidabil in timp polinimial pentru o masina Turing determinista multi-banda atunci el va fi decidabil in timp polinomial pentru o masina Turing cu o singura banda.
Cllasa de limbaje decidabile in timp polinomial ce poate fi utilizata pe masini Turing este notata cu P.Clasa de limbaje acceptabile in timpi polinomiali pe anumite masini Turig este notata NP.
Appendix D.
Teoria probabilistica a computerelor
Algoritmii probabilistici sunt folositi in domenii auxiliare ale sistemelor criptice cum ar fi cautarea numerelor prime.Pot de altfel produce virtual algoritmi practici pentru calculul factorial si al logaritmilor discreti.Aici vom trece in revista o extensie a teoriei clasice a computatiei care incorporeaza calculul probabilistic.O masina Turing obisnuita (determinista) bazata pe mai multe benzi poate fi considerata ca avand o banda de intrari,o banda de iesiri si benzi de citire/scriere.
O modificare a modelului clasic este modelul masinii probabilistice Turing.Aceasta are stari distincte,numite stari ''coin-tossing'' care permit masinii sa ia decizii aleatoare.In termeni recunoscuti de limbaj,acestea au o putere situata la acelasi nivel cu puterea decizionala a masinilor deterministe.
Totusi,consideratiile in privinta timpului sunt mult mai subtile.In particular,notiunea de ''timp de functionare probabilistic'' este necesara,mai mult decat notiunea de timp maxim de functionare ,folosita pentru masinille obisnuite.O masina Turing probabilista opereaza in mod determinist exceptie facand cazul starilor ''coin-tossing''.In asemenea stari ale unei masini pot intra alte doua posibile stari.
Secventa de aruncari ale ''monedei'' poate fi considerata ca fiind continuta pe o banda auxiliara accesibila numai pentru citire,o banda de tip secventa intamplatoare,ce contine un sir binar.Astfel,computatia pe masini probabilistice este o functie cu doua variabile (o banda obisnuita de intrari si o banda cu intrari intamplatoare).Daca aceasta din urma nu este specificata,rezultatul unui calcul al unei masini probabilistice M,M(x),este o variabila intamplatoare.M va produce iesirea y cu probabilitatea Pr.Pentru o intrare data x,poate exista y astfel incat Pr>1/2.Daca y exista aceasta va fi in mod clar unica,in acest caz noi putem scrie q(x)=y.Aceasta defineste o functie partiala q,nedefinita daca nici un y nu poate exista.Functia q se dovedeste astfel a fi utilizabila de catre M.Deci,setul de valori acceptate de M va fi domeniul lui q.
Fie x o intrare acceptata de M,sa luam de exemplu e(x)=Prrelatie dedusa direct din :e(x)<1/2.Sa presupunem ca exista o constanta c<1/2 astfel incat e(x)<=c pentru toate valorile x din e.Deci,putem spune ca M are o limita probabilista a erorii (probabilitatea de ''eroare'' este marginita superior de ½),un alt concept important in cadrul modelului de verificare a puterilor lui 0.
Pr in timpul u este probabilitatea ca masinile probabilistice Turing cu x intrari date sa aiba y iesiri in anumite calcule cu cel mult u pasi.Timpul de functionare T(x) a lui M este definit a fi infinit daca x nu este acceptat de M,daca x nu apartine domeniului functiei partiale q.Daca x este un domeniu al lui q,T(x) este cea mai mica valoare a lui u astfel incat Pr(in timpul u)>1/2.O functie este computabila probabilistic daca aceasta este computata de o masina Turing probabilista.Exista o multitudine de exemple de functii care sunt probabilistic computabile in timp de lucru polinomial probabilistic si cu o eroare limitata probabilistic,dar nu poate fi precizat faptul daca poate fi computabila in timp polinomial determinat,in P.Un exemplu este functia caracteristica a unui set de numere prime.
Fie BPP o clasa de limbaje recunoscute de masini Turing probabiliste cu eroare limitata probabilistic.Convenind ca semnul < sa simbolizeze incluziunea,vom deduce usor ca P<BPP<NP.
|
