64 matches
-
numărul de cifre. O altă abordare ineficientă este găsirea factorilor primi ai unuia sau ai ambelor numere. Așa cum se arată mai sus, CMMDC este egal cu produsul factorilor primi comuni ai celor două numere "a" și "b". Metodele actuale de factorizare sunt și ele ineficiente; multe alte sisteme criptografice se bazează tocmai pe această ineficiență. Algoritmul CMMDC binar este o alternativă eficientă care înlocuiește împărțirea cu operații mai rapide, exploatând reprezentările binare utilizate de calculatoare. Această alternativă, însă, scalează și ea
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
poate fi, însă, generalizat la numere reale, și la sisteme de numere mai exotice, cum ar fi polinoamele, întregii cuadratici și cuaternionii Hurwitz. În ultimele două cazuri, algoritmul lui Euclid este folosit pentru a demonstra proprietatea crucială de unicitate a factorizării, anume aceea că astfel de numere pot fi factorizate în mod unic în elemente ireductibile, structuri similare numerelor prime. Unicitatea factorizării este esențială în multe demonstrații din teoria numerelor. Algoritmul lui Euclid se poate aplica și numerelor reale, așa cum arată
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
cuaternionii Hurwitz. În ultimele două cazuri, algoritmul lui Euclid este folosit pentru a demonstra proprietatea crucială de unicitate a factorizării, anume aceea că astfel de numere pot fi factorizate în mod unic în elemente ireductibile, structuri similare numerelor prime. Unicitatea factorizării este esențială în multe demonstrații din teoria numerelor. Algoritmul lui Euclid se poate aplica și numerelor reale, așa cum arată Euclid în Cartea 10 din "Elementele". Scopul algoritmului este identificarea unui număr real "g" astfel încât două numere reale, "a" și "b
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
la "r"("x") rezultând restul "r"("x") = "x" + "x" + 2. Împărțind, apoi, "r"("x") la "r"("x") rezultă un rest nul, indicând că "r"("x") este cel mai mare divizor comun al lui "a"("x") și "b"("x"), consistent cu factorizarea acestora. Multe dintre aplicațiile descrise mai sus pentru numere întregi sunt valabile și pentru polinoame. Algoritmul lui Euclid se poate folosi pentru rezolvarea de ecuații liniare diofantice și de probleme chinezești ale resturilor pentru polinoame; se pot defini și fracții
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
Întregii gaussieni sunt numere complexe de forma α = "u" + "vi", unde "u" și "v" sunt numere întregi obișnuite și "i" este unitatea imaginară. Definind un algoritm analog celui al lui Euclid, se poate arăta că întregii gaussieni au fiecare o factorizare unică, conform demonstrației de mai sus. Unicitatea factorizării este utilă în mai multe aplicații, cum ar fi calculul tuturor tripletelor pitagoreice sau demonstrația Primei teoreme a lui Fermat a sumei a două pătrate. În general, algoritmul lui Euclid este unul
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
u" + "vi", unde "u" și "v" sunt numere întregi obișnuite și "i" este unitatea imaginară. Definind un algoritm analog celui al lui Euclid, se poate arăta că întregii gaussieni au fiecare o factorizare unică, conform demonstrației de mai sus. Unicitatea factorizării este utilă în mai multe aplicații, cum ar fi calculul tuturor tripletelor pitagoreice sau demonstrația Primei teoreme a lui Fermat a sumei a două pătrate. În general, algoritmul lui Euclid este unul convenabil în asemenea aplicații, dar nu este indispensabil
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
naturală și pe existența unui număr natural minim. Teorema fundamentală a aritmeticii se aplică pe orice inel euclidian: orice element dintr-un inel euclidian poate fi factorizat în mod unic în elemente ireductibile. Orice inel euclidian este un domeniu de factorizare unică, deși reciproca nu este adevărată întotdeauna. Inelele euclidiene sunt o submulțime a domeniilor CMMDC, domenii în care există întotdeauna un cel mai mic divizor comun al două elemente. Cu alte cuvinte, poate exista un cel mai mare divizor comun
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
găsit cu ajutorul algoritmului lui Euclid. Un inel euclidian este întotdeauna un domeniu de ideal principal, domeniu integral în care fiecare ideal este un ideal principal. Din nou, reciproca nu este adevărată: nu orice astfel de domeniu este inel euclidian. Unicitatea factorizării în inelele euclidiene este utilă în mai multe aplicații. De exemplu, unicitatea factorizării întregilor gaussieni este convenabilă la calculul formulelor pentru toate tripletele pitagoreice și la demonstrarea teoremei lui Fermat privind suma a două pătrate. Unicitatea factorizării este și element
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
ideal principal, domeniu integral în care fiecare ideal este un ideal principal. Din nou, reciproca nu este adevărată: nu orice astfel de domeniu este inel euclidian. Unicitatea factorizării în inelele euclidiene este utilă în mai multe aplicații. De exemplu, unicitatea factorizării întregilor gaussieni este convenabilă la calculul formulelor pentru toate tripletele pitagoreice și la demonstrarea teoremei lui Fermat privind suma a două pătrate. Unicitatea factorizării este și element cheie într-o tentativă de demonstrare a Ultimei teoreme a lui Fermat publicată
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
inel euclidian. Unicitatea factorizării în inelele euclidiene este utilă în mai multe aplicații. De exemplu, unicitatea factorizării întregilor gaussieni este convenabilă la calculul formulelor pentru toate tripletele pitagoreice și la demonstrarea teoremei lui Fermat privind suma a două pătrate. Unicitatea factorizării este și element cheie într-o tentativă de demonstrare a Ultimei teoreme a lui Fermat publicată în 1847 de Gabriel Lamé, același matematician care analizase eficiența algoritmului lui Euclid, pe baza unei sugestii a lui Joseph Liouville. Abordarea lui Lamé
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
element cheie într-o tentativă de demonstrare a Ultimei teoreme a lui Fermat publicată în 1847 de Gabriel Lamé, același matematician care analizase eficiența algoritmului lui Euclid, pe baza unei sugestii a lui Joseph Liouville. Abordarea lui Lamé impunea unicitatea factorizării numerelor de forma "x" + ω"y", unde ω = "e" este rădăcina de ordin "n" a lui 1, adică, ω = 1. Deși această abordare are succes pentru anumite valori ale lui "n" (cum ar fi "n"=3, întregii Eisenstein), în general
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
y", unde ω = "e" este rădăcina de ordin "n" a lui 1, adică, ω = 1. Deși această abordare are succes pentru anumite valori ale lui "n" (cum ar fi "n"=3, întregii Eisenstein), în general, asemenea numere "nu" au o factorizare unică. Această neunicitate a factorizărilor din unele corpuri ciclotomice l-a condus pe Ernst Kummer la conceptul de număr ideal și, mai apoi, pe Richard Dedekind la cel de ideal. Întregii cuadratici pot fi un exemplu de inel euclidian. Întregii
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
rădăcina de ordin "n" a lui 1, adică, ω = 1. Deși această abordare are succes pentru anumite valori ale lui "n" (cum ar fi "n"=3, întregii Eisenstein), în general, asemenea numere "nu" au o factorizare unică. Această neunicitate a factorizărilor din unele corpuri ciclotomice l-a condus pe Ernst Kummer la conceptul de număr ideal și, mai apoi, pe Richard Dedekind la cel de ideal. Întregii cuadratici pot fi un exemplu de inel euclidian. Întregii cuadratici sunt o generalizare a
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
cu "n" noduri. este problema calculului a unui număr întreg dat. Formulată ca o problemă de decizie, ea este problema de a decide dacă intrarea are un factor prim mai mic decât "k". Nu se cunoaște niciun algoritm eficient de factorizare a numerelor întregi, și acest fapt stă la baza celor mai multe sisteme criptografice moderne, cum ar fi algoritmul RSA. Problema factorizarea numerelor întregi problemă este în NP și în (și chiar în UP și co-UP). Dacă problema este NP-completă, ierarhia polinomială
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
de a decide dacă intrarea are un factor prim mai mic decât "k". Nu se cunoaște niciun algoritm eficient de factorizare a numerelor întregi, și acest fapt stă la baza celor mai multe sisteme criptografice moderne, cum ar fi algoritmul RSA. Problema factorizarea numerelor întregi problemă este în NP și în (și chiar în UP și co-UP). Dacă problema este NP-completă, ierarhia polinomială se va plia la primul nivel (de exemplu, NP = co-NP). Cel mai cunoscut algoritm pentru factorizarea numerelor întregi este , al
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
fi algoritmul RSA. Problema factorizarea numerelor întregi problemă este în NP și în (și chiar în UP și co-UP). Dacă problema este NP-completă, ierarhia polinomială se va plia la primul nivel (de exemplu, NP = co-NP). Cel mai cunoscut algoritm pentru factorizarea numerelor întregi este , al cărui timp de rulare este la factorizarea unui număr întreg pe" n "biți. Cu toate acestea, cel mai cunoscut pentru această problemă, , rulează în timp polinomial. Din păcate, acest fapt nu spune prea multe despre clasa
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
și în (și chiar în UP și co-UP). Dacă problema este NP-completă, ierarhia polinomială se va plia la primul nivel (de exemplu, NP = co-NP). Cel mai cunoscut algoritm pentru factorizarea numerelor întregi este , al cărui timp de rulare este la factorizarea unui număr întreg pe" n "biți. Cu toate acestea, cel mai cunoscut pentru această problemă, , rulează în timp polinomial. Din păcate, acest fapt nu spune prea multe despre clasa de problemă necuantică din care face parte factorizarea. Toată discuția de
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
rulare este la factorizarea unui număr întreg pe" n "biți. Cu toate acestea, cel mai cunoscut pentru această problemă, , rulează în timp polinomial. Din păcate, acest fapt nu spune prea multe despre clasa de problemă necuantică din care face parte factorizarea. Toată discuția de mai sus pornește de la presupunerea că P înseamnă „ușor” și „nu în P” înseamnă „greu”, o presupunere cunoscută sub numele de "". Este o ipoteză comună și de o acuratețe rezonabilă din teoria complexității; cu toate acestea, ea
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
semnătura electronică. Algoritmul a fost dezvoltat în 1977 și publicat în 1978 de Ron Rivest, Adi Shamir și Leonard Adleman la MIT și își trage numele de la inițialele numelor celor trei autori. Puterea sa criptografică se bazează pe dificultatea problemei factorizării numerelor întregi, problemă la care se reduce criptanaliza și pentru care toți algoritmii de rezolvare cunoscuți au complexitate exponențială. Există însă câteva metode de criptanaliză care ocolesc factorizarea efectivă, exploatând maniere eronate de implementare efectivă a schemei de criptare. RSA
RSA () [Corola-website/Science/311911_a_313240]
-
numelor celor trei autori. Puterea sa criptografică se bazează pe dificultatea problemei factorizării numerelor întregi, problemă la care se reduce criptanaliza și pentru care toți algoritmii de rezolvare cunoscuți au complexitate exponențială. Există însă câteva metode de criptanaliză care ocolesc factorizarea efectivă, exploatând maniere eronate de implementare efectivă a schemei de criptare. RSA este un algoritm de criptare pe blocuri. Aceasta înseamnă că atât textul clar cât și cel cifrat sunt numere între "0" și "n"-1, cu un "n" ales
RSA () [Corola-website/Science/311911_a_313240]
-
de a realiza aceasta este descompunerea în factori primi a lui "n", și obținerea astfel a cheii secrete "d" pe baza lui "e". Astfel, este demonstrat că dificultatea spargerii unui mesaj criptat cu RSA nu este mai dificilă decât problema factorizării. Nu a fost descoperită încă o altă soluție generală a problemei RSA, dar nici nu s-a demonstrat matematic că nu există o altă soluție. Factorizarea întregilor prin metodele comune ajută la găsirea soluțiilor în timp util doar pentru numere
RSA () [Corola-website/Science/311911_a_313240]
-
că dificultatea spargerii unui mesaj criptat cu RSA nu este mai dificilă decât problema factorizării. Nu a fost descoperită încă o altă soluție generală a problemei RSA, dar nici nu s-a demonstrat matematic că nu există o altă soluție. Factorizarea întregilor prin metodele comune ajută la găsirea soluțiilor în timp util doar pentru numere mici. Pentru numere mari, algoritmii de factorizare, cu complexitate exponențială, dau soluția după foarte mult timp. Cea mai rapidă metodă de factorizare a întregilor, algoritmul general
RSA () [Corola-website/Science/311911_a_313240]
-
altă soluție generală a problemei RSA, dar nici nu s-a demonstrat matematic că nu există o altă soluție. Factorizarea întregilor prin metodele comune ajută la găsirea soluțiilor în timp util doar pentru numere mici. Pentru numere mari, algoritmii de factorizare, cu complexitate exponențială, dau soluția după foarte mult timp. Cea mai rapidă metodă de factorizare a întregilor, algoritmul general al ciurului câmpurilor de numere, are o complexitate de formula 20 Aici, "c" este un număr ce ia valori în jur de
RSA () [Corola-website/Science/311911_a_313240]
-
există o altă soluție. Factorizarea întregilor prin metodele comune ajută la găsirea soluțiilor în timp util doar pentru numere mici. Pentru numere mari, algoritmii de factorizare, cu complexitate exponențială, dau soluția după foarte mult timp. Cea mai rapidă metodă de factorizare a întregilor, algoritmul general al ciurului câmpurilor de numere, are o complexitate de formula 20 Aici, "c" este un număr ce ia valori în jur de 1,9 pentru numere de tipul lui "n", adică numere cu doi factori primi. Cel
RSA () [Corola-website/Science/311911_a_313240]
-
binară a factorilor primi obținuți ocupă 663 de biți. Cheile de criptare RSA cele mai sigure au lungimi de peste 1024 de biți. Atacul RSA prin metoda forței brute, adică încercarea fiecărei chei secrete posibile, consumă chiar mai mult timp decât factorizarea. Deși securitatea algoritmului RSA constă în legătura dintre acesta și factorizarea întregilor, el trebuie folosit cu grijă în implementări, deoarece, în caz de folosire eronată, sistemele bazate pe RSA pot fi atacate în anumite maniere care ocolesc factorizarea efectivă a
RSA () [Corola-website/Science/311911_a_313240]