Algorisme de Shor: diferència entre les revisions
Contingut suprimit Contingut afegit
m |thumb|right -> |miniatura |
m neteja Etiquetes: Edita des de mòbil Edició web per a mòbils |
||
Línia 1:
L''''algorisme de Shor''' és un [[algorisme]] [[Computació quàntica|quàntic]] per [[Factorització|descompondre en factors]] un nombre ''N'' en temps [[Cota superior asimptòtica|O]]
Moltes [[Criptografia asimètrica|criptografies de clau pública]], com ara [[RSA]], arribarien a ser obsoletes si l'algorisme de Shor és implementat alguna vegada en un [[Computació quàntica|ordinador quàntic]] pràctic. Un missatge xifrat amb RSA pot ser desxifrat descomponent en factors la clau pública ''N'', que és el producte de dos nombres primers. Els algorismes clàssics coneguts no poden fer-ho en temps O((log''N'')<sup>''k''</sup>) per a cap ''k'', de manera que arriben a ser ràpidament poc pràctics a mesura que s'augmenta''N''. Per contra, l'algorisme de Shor pot [[Problemes RSA|trencar RSA]] en [[temps polinòmic]]. També s'ha ampliat per atacar moltes altres criptografies de clau pública.
| |||