| dbpedia-owl:abstract
|
- Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm for integer factorization formulated in 1994. Informally it solves the following problem: Given an integer N, find its prime factors. On a quantum computer, to factor an integer N, Shor's algorithm runs in polynomial time (the time taken is polynomial in log N, which is the size of the input). Specifically it takes time O, demonstrating that the integer factorization problem can be efficiently solved on a quantum computer and is thus 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 O(e). The efficiency lies in the efficiency of the quantum Fourier transform, and modular exponentiation by squarings. Given a quantum computer with a sufficient number of qubits, Shor's algorithm can 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 (non-quantum) 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. It has also facilitated research on new cryptosystems that are secure from quantum computers, collectively called post-quantum cryptography. 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. However, some doubts have been raised as to whether IBM's experiment was a true demonstration of quantum computation, since no entanglement was observed. Since IBM's implementation, several other groups have implemented Shor's algorithm using photonic qubits, emphasizing that entanglement was observed.
- Der Shor-Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie, der Mittel der Quanteninformatik benutzt. 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 benötigt man einen Quantencomputer mit mindestens 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 sehr bedeutend, weil 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.
- En computación cuántica, 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.
- Shorin algoritmi on matemaatikko Peter Shorin mukaan nimetty kvanttialgoritmi kokonaislukujen tekijöihin jakoa varten. Se keksittiin vuonna 1994 AT&T-yhtiön Bell Labsissa New Jerseyssä. Shor osoitti, miten kvanttitietokone laskee erittäin suurten lukujen tekijät äärimmäisen nopeasti.
- 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 o, più correttamente, BQP (Bounded error Quantum Polynomial time): i fattori sono trovati con margine d'errore arbitrariamente piccolo in tempo polinomiale nella lunghezza dell'intero di input.
- 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 . Do tej pory jest to największe znane obliczenie kwantowe.
- Алгоритм Шора — это квантовый алгоритм факторизации (разложения числа на простые множители), позволяющий разложить число N за время, используя O(log N) логических кубитов. Значимость алгоритма заключается в том, что при использовании квантового компьютера с несколькими сотнями логических кубитов, он сделает возможным взлом криптографических систем с открытым ключом. К примеру, RSA использует открытый ключ N, являющийся произведением двух больших простых чисел. Один из способов взломать шифр RSA — найти множители N. При достаточно большом N это практически невозможно сделать, используя известные классические алгоритмы. Наилучший из известных классических алгоритмов факторизации требует времени порядка . Так как алгоритм Шора работает только на квантовом компьютере, в настоящее время не существует технических средств, позволяющих за полиномиальное время от длины числа разложить достаточно большое число на множители. Алгоритм Шора в свою очередь, используя возможности квантовых компьютеров, способен произвести факторизацию числа не просто за полиномиальное время, а за время, не намного превосходящее время умножения целых чисел (то есть практически так же быстро, как происходит само шифрование). Таким образом, реализация масштабируемого квантового компьютера в случае ее успеха поставила бы крест на большей части современной криптографической защиты. (Речь не только о схеме RSA, прямо опирающейся на сложности факторизации, но и о других сходных схемах, которые квантовый компьютер способен взломать аналогичным образом). Как и другие алгоритмы для квантовых компьютеров, алгоритм Шора вероятностный: он даёт верный ответ с высокой вероятностью. Вероятность ошибки может быть уменьшена при повторном использовании алгоритма. Тем не менее, так как возможна проверка предложенного результата (умножением) в квадратичное время, алгоритм может быть модифицирован так, что ответ будет верным с единичной вероятностью. Алгоритм Шора был разработан Питером Шором в 1994 году. Семь лет спустя, в 2001 году, его работоспособность была продемонстрирована группой специалистов IBM. Число 15 было разложено на множители 3 и 5 при помощи квантового компьютера с 7 кубитами.
- 秀爾演算法（Template:Lang算法），以數學家彼得·秀爾命名，是一個在1994年發現的，針對整數分解這題目的的量子演算法。比較不正式的說，它解決題目如下：給定一個整數N，找出他的質因數。 在一個量子計算機上面，要分解整數N, 秀爾演算法的運作需要多項式時間 (時間是log N的某個多項式這麼長,log N在這裡的意義是輸入的檔案長度)。 更精確的說，這個演算法花費O的時間，展示出質因數分解問題可以使用量子計算機以多項式時間解出，因此在複雜度類 BQP裡面。這比起傳統已知最快的因數分解演算法, 普通數域篩選法, 其花費次指數時間 -- 大約O(e)，還要快了一個指數的差異。 秀爾演算法非常重要，因為它代表使用量子計算機的話，我們可以用來破解已被廣泛使用的公開密鑰加密方法，也就是RSA加密演算法。RSA演算法的基礎在於假設了我們不能很有效率的分解一個已知的整數。就目前所知，這假設對傳統的(也就是非量子)電腦為真；沒有已知傳統的演算法可以在多項式時間內解決這個問題。然而，秀爾演算法展示了因數分解這問題在量子計算機上可以很有效率的解決，所以一個足夠大的量子計算機可以破解RSA。這對於鼓吹我們去建立量子計算機和去研究新的量子計算機演算法，是一個非常大的動力。 在2001年，IBM的一個小組展示了秀爾演算法的實做, 使用NMR實做的量子計算機，以及7個量子位元，將15分解成3 × 5。 然而，對IBM的實驗的是否是量子計算的真實展示，則有一些疑慮出現，因為沒有纏結現象被發現。 在IBM的實做之後，有其他的團隊以光學量子位元實做秀爾演算法，並強調其纏結現象可被觀察到。
- En arithmétique modulaire, l’algorithme de Shor est un algorithme quantique pour factoriser un nombre N en temps O et en espace, nommé en l'honneur de Peter Shor. Beaucoup de cryptosystèmes à clé publique, tels que le RSA, deviendraient vulnérables si l'algorithme de Shor était un jour implémenté 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 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.
|
| rdfs:comment
|
- Shorin algoritmi on matemaatikko Peter Shorin mukaan nimetty kvanttialgoritmi kokonaislukujen tekijöihin jakoa varten. Se keksittiin vuonna 1994 AT&T-yhtiön Bell Labsissa New Jerseyssä. Shor osoitti, miten kvanttitietokone laskee erittäin suurten lukujen tekijät äärimmäisen nopeasti.
- 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 o, più correttamente, BQP (Bounded error Quantum Polynomial time): i fattori sono trovati con margine d'errore arbitrariamente piccolo in tempo polinomiale nella lunghezza dell'intero di input.
- 秀爾演算法（Template:Lang算法），以數學家彼得·秀爾命名，是一個在1994年發現的，針對整數分解這題目的的量子演算法。比較不正式的說，它解決題目如下：給定一個整數N，找出他的質因數。 在一個量子計算機上面，要分解整數N, 秀爾演算法的運作需要多項式時間 (時間是log N的某個多項式這麼長,log N在這裡的意義是輸入的檔案長度)。 更精確的說，這個演算法花費O的時間，展示出質因數分解問題可以使用量子計算機以多項式時間解出，因此在複雜度類 BQP裡面。這比起傳統已知最快的因數分解演算法, 普通數域篩選法, 其花費次指數時間 -- 大約O(e)，還要快了一個指數的差異。 秀爾演算法非常重要，因為它代表使用量子計算機的話，我們可以用來破解已被廣泛使用的公開密鑰加密方法，也就是RSA加密演算法。RSA演算法的基礎在於假設了我們不能很有效率的分解一個已知的整數。就目前所知，這假設對傳統的(也就是非量子)電腦為真；沒有已知傳統的演算法可以在多項式時間內解決這個問題。然而，秀爾演算法展示了因數分解這問題在量子計算機上可以很有效率的解決，所以一個足夠大的量子計算機可以破解RSA。這對於鼓吹我們去建立量子計算機和去研究新的量子計算機演算法，是一個非常大的動力。 在2001年，IBM的一個小組展示了秀爾演算法的實做, 使用NMR實做的量子計算機，以及7個量子位元，將15分解成3 × 5。 然而，對IBM的實驗的是否是量子計算的真實展示，則有一些疑慮出現，因為沒有纏結現象被發現。 在IBM的實做之後，有其他的團隊以光學量子位元實做秀爾演算法，並強調其纏結現象可被觀察到。
- Der Shor-Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie, der Mittel der Quanteninformatik benutzt. 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.
- Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm for integer factorization formulated in 1994. Informally it solves the following problem: Given an integer N, find its prime factors. On a quantum computer, to factor an integer N, Shor's algorithm runs in polynomial time (the time taken is polynomial in log N, which is the size of the input).
- En computación cuántica, 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.
- 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.
- Алгоритм Шора — это квантовый алгоритм факторизации (разложения числа на простые множители), позволяющий разложить число N за время, используя O(log N) логических кубитов. Значимость алгоритма заключается в том, что при использовании квантового компьютера с несколькими сотнями логических кубитов, он сделает возможным взлом криптографических систем с открытым ключом. К примеру, RSA использует открытый ключ N, являющийся произведением двух больших простых чисел.
- En arithmétique modulaire, l’algorithme de Shor est un algorithme quantique pour factoriser un nombre N en temps O et en espace, nommé en l'honneur de Peter Shor. Beaucoup de cryptosystèmes à clé publique, tels que le RSA, deviendraient vulnérables si l'algorithme de Shor était un jour implémenté 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.
|
