Documente online.
Username / Parola inexistente
  Zona de administrare documente. Fisierele tale  
Am uitat parola x Creaza cont nou
  Home Exploreaza
Upload



















































Aspecte matematice si computationale

Matematica












ALTE DOCUMENTE

SIMULAREA TEZEI CU SUBIECT UNIC LA MATEMATICĂ
Test initial, clasa a IX a matematica
Spirala logaritmica
Paralelogramul
Elemente de trigonometrie, formule algebrice geometrice
Progresii
PROBLEME SIMPLE
Repartitia chi patrat
Evaluare sumativa clasa a VI-a

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.

A.3 Cheile publice si criptocomplexitatea

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 xec(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.

 [E1]

 [E2]













Document Info


Accesari: 2209
Apreciat:

Comenteaza documentul:

Nu esti inregistrat
Trebuie sa fii utilizator inregistrat pentru a putea comenta


Creaza cont nou

A fost util?

Daca documentul a fost util si crezi ca merita
sa adaugi un link catre el la tine in site

Copiaza codul
in pagina web a site-ului tau.




Coduri - Postale, caen, cor

Politica de confidentialitate

Copyright Contact (SCRIGROUP Int. 2019 )