| dbpprop:abstract
|
- Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm for integer factorization discovered in 1994. Informally it solves the following problem: Given an integer <math>N</math>, find its factors. On a quantum computer, to factor an integer <math>N</math>, Shor's algorithm runs in polynomial time (in <math>\log{N}</math>); specifically it takes time <math>O(^3)</math>, demonstrating that integer factorization is in the complexity class BQP. This is exponentially faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time -- about <math>O \left(e^{ ^{1/3} ^{2/3} } \right) Shor's algorithm is important because it can, in theory, be used to "break" the widely used public-key cryptography scheme known as RSA. RSA is based on the assumption that factoring large numbers is computationally infeasible. So far as is known, this assumption is valid for classical computers; no classical algorithm is known that can factor in polynomial time. However, Shor's algorithm shows that factoring is efficient on a quantum computer, so an appropriately large quantum computer can "break" RSA. It was also a powerful motivator for the design and construction of quantum computers and for the study of new quantum computer algorithms. In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored 15 into 3 × 5, using an NMR implementation of a quantum computer with 7 qubits.
- Der Shor-Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie, der sich Mitteln der Quanteninformatik bedient. Er berechnet auf einem Quantencomputer einen nichttrivialen Teiler einer zusammengesetzten Zahl und zählt somit zur Klasse der Faktorisierungsverfahren. Für praktisch relevante Aufgabenstellungen ist der Shor-Algorithmus noch nicht anwendbar, da er starken technischen Einschränkungen unterliegt. Für eine Zahl <math>n</math> benötigt man einen Quantencomputer mit mindestens <math>\log (n)</math> Qubits. Eine Forschungsgruppe der IBM hat beispielsweise im Jahr 2001 einen Quantencomputer mit sieben Qubits eingesetzt, um die Zahl 15 in die Faktoren 5 und 3 zu zerlegen. Der Shor-Algorithmus ist für die Kryptographie so bedeutend, da er einen nichttrivialen Teiler essenziell schneller findet als klassische Algorithmen. Während diese subexponentielle, jedoch deutlich höher als polynomiale Laufzeit benötigen, hat der Shor-Algorithmus nur polynomiale Laufzeit. Dies stellt beispielsweise eine Gefahr für die häufig zur verschlüsselten Datenübertragung verwendeten RSA-Kryptosysteme dar, deren Sicherheit gerade auf der Annahme beruht, dass kein Faktorisierungsverfahren mit polynomialer Laufzeit existiert. Der Algorithmus wurde 1994 von Peter W. Shor veröffentlicht, der damals bei den AT&T Bell Laboratories beschäftigt war. Die Arbeit trägt den Titel Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. Darin wird auch noch ein zweiter Algorithmus zur Berechnung des diskreten Logarithmus beschrieben, der ebenfalls als Shor-Algorithmus bezeichnet wird. Im Allgemeinen wird diese Bezeichnung jedoch für das Faktorisierungsverfahren verwendet.
- El algoritmo de Shor es un algoritmo cuántico para descomponer en factores un número N en tiempo O y espacio O(logN), así nombrado por Peter Shor. Muchas criptografías de clave pública, tales como RSA, llegarían a ser obsoletas si el algoritmo de Shor es implementado alguna vez en una computadora cuántica práctica. Un mensaje cifrado con RSA puede ser descifrado descomponiendo en factores la llave pública N, que es el producto de dos números primos. Los algoritmos clásicos conocidos no pueden hacer esto en tiempo O para ningún k, así que llegan a ser rápidamente imprácticos a medida que se aumenta N. Por el contrario, el algoritmo de Shor puede romper RSA en tiempo polinómico. También se ha ampliado para atacar muchas otras criptografías públicas. Como todos los algoritmos de computación cuántica, el algoritmo de Shor es probabilístico: da la respuesta correcta con alta probabilidad, y la probabilidad de fallo puede ser disminuida repitiendo el algoritmo. El algoritmo de Shor fue demostrado en 2001 por un grupo en IBM, que descompuso 15 en sus factores 3 y 5, usando una computadora cuántica con 7 qubits.
- En arithmétique modulaire, l’algorithme de Shor est un algorithme quantique pour factoriser un nombre N en temps O<math>(^3) et en espace <math>O(log N), nommé en l'honneur de Peter Shor. Beaucoup de cryptosystèmes à clé publique, tels que le RSA, deviendraient cassables par un tiers si l'algorithme de Shor était un jour programmé dans un calculateur quantique pratique. Un message chiffré avec RSA peut être déchiffré par factorisation de sa clé publique N, qui est le produit de deux nombres premiers. En l'état actuel des connaissances, il n'existe pas d'algorithme classique capable de faire cela en temps <math>O(^k) pour n'importe quel k, donc, les algorithmes classiques connus deviennent rapidement impraticables quand N augmente, à la différence de l'algorithme de Shor qui peut casser le RSA en temps polynomial. Il a été aussi étendu pour attaquer beaucoup d'autres cryptosystèmes à clé publique. Comme tous les algorithmes pour calculateur quantique, l'algorithme de Shor est probabiliste : il donne la réponse correcte avec une haute probabilité et la probabilité d'échec peut être diminuée en répétant l'algorithme. L'algorithme de Shor fut utilisé en 2001 par un groupe d'IBM, qui factorisa 15 en 3 et 5, en utilisant un calculateur quantique de 7 qubits.
- L'algoritmo di fattorizzazione di Shor è un algoritmo ideato da Peter Shor nel 1994 per risolvere il problema della fattorizzazione dei numeri interi in numeri primi. Su un computer quantistico questo algoritmo ha una complessità computazionale polinomiale.
- Kwantowy algorytm Shora – algorytm kwantowy umożliwiający rozkład na czynniki pierwsze liczby naturalnej N w czasie O i pamięci O(log N), przy wykorzystaniu komputera kwantowego. Algorytm ten stanowi teoretyczne zagrożenie dla powszechnie używanego w internecie kryptosystemu RSA. Klucz publiczny w RSA jest iloczynem dwóch dużych liczb pierwszych. Możliwość efektywnego odtworzenia tych liczb na podstawie klucza publicznego pozwalałaby poznać klucz prywatny i tym samym złamać cały szyfr. Jak większość algorytmów kwantowych, algorytm Shora jest algorytmem probabilistycznym: zwraca poprawną odpowiedź jedynie z pewnym prawdopodobieństwem. Ponieważ jednak odpowiedź może być szybko sprawdzona, powtarzanie algorytmu umożliwia uzyskanie poprawnej odpowiedzi w sposób efektywny z dowolnie dużym prawdopodobieństwem. Algorytm ten opublikował Peter Shor w 1994 roku. W 2001 roku grupa informatyków z firmy IBM i Uniwersytetu Stanford zademonstrowała jego działanie na 7-kubitowym komputerze kwantowym opartym o jądrowy rezonans magnetyczny. Dokonano wtedy rozkładu liczby <math>15\ =\ 3\cdot 5</math>. Do tej pory jest to największe znane obliczenie kwantowe.
- Алгоритм Шора — это квантовый алгоритм факторизации (разложения числа на простые множители), позволяющий разложить число N за время O, затратив O(log N) места. Значимость алгоритма заключается в том, что при использовании достаточно мощного квантового компьютера, он сделает возможным взлом криптографических систем с открытым ключом. К примеру, RSA использует открытый ключ N, являющийся произведением двух больших простых чисел. Один из способов взломать шифр RSA — найти множители N. При достаточно большом N это практически невозможно сделать, используя известные классические алгоритмы. Так как алгоритм Шора работает только на квантовом компьютере, в настоящее время не существует технических средств, позволяющих за полиномиальное время от длины числа разложить достаточно большое число на множители. Алгоритм Шора в свою очередь, используя возможности квантовых компьютеров, способен произвести факторизацию числа за полиномиальное время. Это может поставить под угрозу надёжность большинства криптосистем с открытым ключом, основанных на сложности проблемы факторизации чисел. Как и другие алгоритмы для квантовых компьютеров, алгоритм Шора вероятностный: он даёт верный ответ с высокой вероятностью. Вероятность ошибки может быть уменьшена при повторном использовании алгоритма. Тем не менее, так как возможна проверка предложенного результата (в частности простоты числа) в полиномиальное время, алгоритм может быть модифицирован так, что ответ, полученный в полиномиальное время, будет верным с единичной вероятностью. Алгоритм Шора был разработан Питером Шором в 1994 году. Семь лет спустя, в 2001 году, его работоспособность была продемонстрирована группой специалистов IBM. Число 15 было разложено на множители 3 и 5 при помощи квантового компьютера с 7 кубитами.
|
| rdfs:comment
|
- Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm for integer factorization discovered in 1994. Informally it solves the following problem: Given an integer <math>N</math>, find its factors.
- Der Shor-Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie, der sich Mitteln der Quanteninformatik bedient. Er berechnet auf einem Quantencomputer einen nichttrivialen Teiler einer zusammengesetzten Zahl und zählt somit zur Klasse der Faktorisierungsverfahren. Für praktisch relevante Aufgabenstellungen ist der Shor-Algorithmus noch nicht anwendbar, da er starken technischen Einschränkungen unterliegt.
- El algoritmo de Shor es un algoritmo cuántico para descomponer en factores un número N en tiempo O y espacio O(logN), así nombrado por Peter Shor. Muchas criptografías de clave pública, tales como RSA, llegarían a ser obsoletas si el algoritmo de Shor es implementado alguna vez en una computadora cuántica práctica. Un mensaje cifrado con RSA puede ser descifrado descomponiendo en factores la llave pública N, que es el producto de dos números primos.
- En arithmétique modulaire, l’algorithme de Shor est un algorithme quantique pour factoriser un nombre N en temps O<math>(^3) et en espace <math>O(log N), nommé en l'honneur de Peter Shor. Beaucoup de cryptosystèmes à clé publique, tels que le RSA, deviendraient cassables par un tiers si l'algorithme de Shor était un jour programmé dans un calculateur quantique pratique.
- L'algoritmo di fattorizzazione di Shor è un algoritmo ideato da Peter Shor nel 1994 per risolvere il problema della fattorizzazione dei numeri interi in numeri primi. Su un computer quantistico questo algoritmo ha una complessità computazionale polinomiale.
- Kwantowy algorytm Shora – algorytm kwantowy umożliwiający rozkład na czynniki pierwsze liczby naturalnej N w czasie O i pamięci O(log N), przy wykorzystaniu komputera kwantowego. Algorytm ten stanowi teoretyczne zagrożenie dla powszechnie używanego w internecie kryptosystemu RSA. Klucz publiczny w RSA jest iloczynem dwóch dużych liczb pierwszych.
- Алгоритм Шора — это квантовый алгоритм факторизации (разложения числа на простые множители), позволяющий разложить число N за время O, затратив O(log N) места.
|
![[RDF Data]](/statics/sw-cube.png)
