Shor's algorithm (original) (raw)
خوارزمية شوور (بالإنجليزية: Shor's algorithm) هي خوارزمية لتفكيك عدد طبيعي N في زمن ((log N)3) وفي مساحة (O(log N. تحمل هاته الخوارزمية اسم بيتر شور.
| Property | Value |
|---|---|
| dbo:abstract | خوارزمية شوور (بالإنجليزية: Shor's algorithm) هي خوارزمية لتفكيك عدد طبيعي N في زمن ((log N)3) وفي مساحة (O(log N. تحمل هاته الخوارزمية اسم بيتر شور. (ar) L'algorisme de Shor és un algorisme quàntic per descompondre en factors un nombre N en temps O ((log N)3) i espai O(log N), així nomenat per Peter Shor. Moltes criptografies de clau pública, com ara RSA, arribarien a ser obsoletes si l'algorisme de Shor és implementat alguna vegada en un 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((logN)k) per a cap k, de manera que arriben a ser ràpidament poc pràctics a mesura que s'augmentaN. Per contra, l'algorisme de Shor pot en temps polinòmic. També s'ha ampliat per atacar moltes altres criptografies de clau pública. Com tots els algorismes de computació quàntica, l'algorisme de Shor és probabilístic: dona la resposta correcta amb alta probabilitat, i la probabilitat d'error pot ser disminuïda repetint l'algorisme. L'algorisme de Shor va ser demostrat en 2001 per un grup d'IBM, que va descompondre 15 en els seus factors 3 i 5, utilitzant un ordinador quàntic amb 7 qubits. (ca) 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 bisher (Stand 2020) keine hinreichend großen und fehlerarmen Quantencomputer zur Verfügung stehen. Um eine Zahl mit Binärstellen (d. h., ) zu faktorisieren, benötigt ein Quantencomputer ein Quantenregister, dessen Größe mindestens linear mit der Zahl der Binärstellen wächst. Der ursprüngliche Algorithmus von Shor benötigt 3N Qubits, die beste bekannte Variante kommt mit 2N+3 Qubits aus. Diese Zahlen gelten für einen idealen (fehlerfreien) Quantencomputer. In der Praxis ist es nötig, Quantenfehlerkorrekturverfahren zu verwenden. Dann werden um einen (großen, aber in N konstanten) Faktor M mehr physische Qubits benötigt, wobei M sehr stark von der Fehlerrate und dem verwendeten Fehlerkorrekturcode abhängt. Man schätzt, dass für eine 2048-bit-Zahl 10 bis 100 Millionen Qubits benötigt werden (im fehlerfreien Fall wären es nur einige tausend). Eine Forschungsgruppe des US-amerikanischen Unternehmens 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 polynomielle Laufzeit benötigen, hat der Shor-Algorithmus nur polynomielle 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 polynomieller Laufzeit existiert. Der Algorithmus wurde 1994 von Peter 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. (de) 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((log N)3) y espacio O(logN), así nombrado por Peter Shor. El algoritmo de Shor es un procedimiento que permite encontrar factores de un número de una manera eficiente. La implementación de este algoritmo se puede llevar a cabo de manera clásica o utilizando (que no han sido llevados a la práctica todavía). Esta última implementación es (por supuesto) la más conveniente cuando se desea encontrar el orden, un parámetro muy necesario a la hora de encontrar los factores primos de un cierto número. 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((log N)k) para ningún k, así que llegan a ser rápidamente poco prá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 aplicado en la práctica en 2001 por un grupo en IBM, que descompuso 15 en sus factores 3 y 5, usando una computadora cuántica con 7 qubits. (es) En arithmétique modulaire et en informatique quantique, l’algorithme de Shor est un algorithme quantique conçu par Peter Shor en 1994, qui factorise un entier naturel N en temps O et en espace . Beaucoup de cryptosystèmes à clé publique, tels que le RSA, deviendraient vulnérables si l'algorithme de Shor était un jour implanté 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. Les algorithmes classiques connus deviennent donc 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 la plupart des 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. (fr) Shor's algorithm is a quantum computer algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. On a quantum computer, to factor an integer , Shor's algorithm runs in polynomial time, meaning the time taken is polynomial in , the size of the integer given as input. Specifically, it takes quantum gates of order using fast multiplication, or even utilizing the asymptotically fastest multiplication algorithm currently known due to Harvey and Van Der Hoven, thus demonstrating that the integer factorization problem can be efficiently solved on a quantum computer and is consequently in the complexity class BQP. This is almost exponentially faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time: . The efficiency of Shor's algorithm is due to the efficiency of the quantum Fourier transform, and modular exponentiation by repeated squarings. If a quantum computer with a sufficient number of qubits could operate without succumbing to quantum noise and other quantum-decoherence phenomena, then Shor's algorithm could be used to break public-key cryptography schemes, such as * The RSA scheme * The Finite Field Diffie-Hellman key exchange * The Elliptic Curve Diffie-Hellman key exchange RSA is based on the assumption that factoring large integers is computationally intractable. As far as is known, this assumption is valid for classical (non-quantum) computers; no classical algorithm is known that can factor integers in polynomial time. However, Shor's algorithm shows that factoring integers is efficient on an ideal quantum computer, so it may be feasible to defeat RSA by constructing a large quantum computer. 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 into , using an NMR implementation of a quantum computer with qubits. After IBM's implementation, two independent groups implemented Shor's algorithm using photonic qubits, emphasizing that multi-qubit entanglement was observed when running the Shor's algorithm circuits. In 2012, the factorization of was performed with solid-state qubits. Later, in 2012, the factorization of was achieved. In 2019 an attempt was made to factor the number using Shor's algorithm on an IBM Q System One, but the algorithm failed because of accumulating errors. Though larger numbers have been factored by quantum computers using other algorithms, these algorithms are similar to classical brute-force checking of factors, so unlike Shor's algorithm, they are not expected to ever perform better than classical factoring algorithms. (en) Het algoritme van Shor, vernoemd naar de Amerikaanse wiskundige Peter Shor die het in 1994 formuleerde, is een kwantumalgoritme (dat is een algoritme dat op een kwantumcomputer draait) voor het ontbinden in priemfactoren. Informeel lost het het volgende probleem op: vind, gegeven een geheel getal N, zijn priemfactoren. (nl) 쇼어 알고리즘(Shor's algorithm)은 소인수 분해를 빠르게 처리할 수 있는 양자 알고리즘이다. 수학자 피터 쇼어가 제안했다. 쇼어 알고리즘을 사용하면 크기가 인 수를 소인수 분해할 때 의 시간과 의 저장공간이 필요하다. 쇼어는 이 업적으로 국제수학자회의에서 가우스상을 받았다. 이 알고리즘의 가장 중요한 점은 이것을 이용하면 공개 키 암호 방식을 쉽게 깰 수 있다는 점이다. 예를 들어 RSA의 경우, 매우 큰 두 개의 소수를 곱한 값을 공개 열쇠 으로 사용한다. 이와 같은 방식이 안전한 이유는 을 빠른 시간 안에 효율적으로 소인수 분해하는 알고리즘이 지금까지 발견되지 않았기 때문이다. 그러나 쇼어 알고리즘을 충분히 큰 수에 대해서 적용할 수 있는 기계가 만들어지면, 오늘날의 공개 키 암호 방식은 모두 무용지물이 된다. 이런 점에서 쇼어 알고리즘은 양자 컴퓨터의 킬러 애플리케이션(killer application)인 셈이다. 그래서 양자암호와 양자 후 암호 기술이 개발되고 있다. 2001년에 IBM의 연구팀이 7개의 큐비트를 이용하여 15를 3과 5로 소인수 분해할 수 있는 양자 컴퓨터를 만들었다. 그러나 RSA 암호에서 실제로 사용하는 수백자리의 수를 소인수 분해하는 단계까지 이르기에는, 아직도 수많은 연구가 필요하다. (ko) 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. (it) Na teoria da complexidade computacional e em Computação quântica, o algoritmo de Shor, batizado em homenagem ao matemático Peter Shor, é um algoritmo quântico para fatorar um número N não primo de L bits. Usando bits quânticos, ou qubits reciclados, o cálculo quântico de Shor é utilizado, explorando a mecânica quântica, para simplificar a fatoração de números em um produto de números primos - uma tarefa difícil para os computadores comuns, clássico, quando os números ficam muito grandes. Até 2012, o maior número fatorado usando o algoritmo de Shor era 15. (pt) Kwantowy algorytm Shora – algorytm kwantowy umożliwiający rozkład na czynniki pierwsze liczby naturalnej N w czasie i wykorzystując pamięć 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 . Faktoryzacji liczby dokonano w 2011 roku. (pl) Алгоритм Шора — факторизації (розкладання числа на прості множники), що дозволяє розкласти число за час , використовуючи логічних кубітів. Алгоритм Шора був розроблений Пітером Шором в 1994 році. Сім років по тому, в 2001 році, його працездатність була продемонстрована групою фахівців IBM. Число 15 було розкладено на множники 3 і 5 за допомогою квантового комп'ютера з 7 кубітами. (uk) Алгори́тм Шо́ра — квантовый алгоритм факторизации (разложения числа на простые множители), позволяющий разложить число за время , используя логических кубитов. Алгоритм Шора был разработан Питером Шором в 1994 году. Семь лет спустя, в 2001 году, его работоспособность была продемонстрирована группой специалистов IBM. Число 15 было разложено на множители 3 и 5 при помощи квантового компьютера с 7 кубитами. (ru) 秀爾演算法（英語：Shor's algorithm）是一個于1994年發現的，以數學家彼得·秀爾命名，針對整數分解題目的的量子演算法（在量子計算機上面運作的演算法）。不正式地說，它解決的題目是：給定一個整數 ，找出它的質因數。在一個量子計算機上面，要分解整數，秀爾演算法的運作需要多項式時間（時間是 的某個多項式這麼長， 在這裡的意義是輸入的檔案長度）。准确来说，该演算法花費 的時間，展示出質因數分解問題可以使用量子計算機以多項式時間解出，因此在複雜度類BQP裡面。這比傳統上已知的最快的因數分解演算法普通數域篩選法所花費的次指數時間——大約 還要快了一個指數。 秀爾演算法非常重要，它意味着：假如有可用的量子計算機，我們可以破解基于公開密鑰加密的算法（比如RSA加密演算法）。RSA演算法的基礎在於假設了我們不能有效率的分解一個已知的整數。就目前所知，這假設對傳統（即非量子）的電腦為真；沒有已知的傳統演算法可以在多項式時間內解決這個問題。但秀爾演算法展示了因數分解問題在量子計算機上可以很有效率的解決，所以一個足夠大的量子計算機可以破解RSA。這對於建立量子計算機和研究新的量子計算機演算法是一個强大的動力。 2001年，IBM的一個小組展示了秀爾演算法的實例，使用的量子計算機及7個量子位元，將15分解成3×5。不过，对于IBM的實驗是否是量子計算的真實展示，有一些疑慮出現，因為沒有发现纏結現象。IBM的實驗之後，也有其他的團隊以光學量子位元實驗秀爾演算法，並強調可觀察到其纏結現象。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Shor's_algorithm.svg?width=300 |
| dbo:wikiPageExternalLink | https://www.amazon.com/Mathematics-Unlimited-Bj%C3%B6rn-Engquist/dp/3540669132 http://www.libquantum.de/ http://scottaaronson.com/blog/%3Fp=208%23comment-9958 https://quantum-algorithms.herokuapp.com/299/paper/index.html http://blogs.discovermagazine.com/80beats/2011/01/19/a-step-towards-quantum-computing-entangling-10-billion-particles/ http://www.cs.berkeley.edu/~vazirani/f04quantum/notes/lec9.ps http://www.pbs.org/video/hacking-at-quantum-speed-with-shors-algorithm-8jrjkq/ http://www.pbs.org/video/how-to-break-cryptography-ahby1s/ https://web.archive.org/web/20121115112940/http:/people.ccmr.cornell.edu/~mermin/qcomp/chap3.pdf http://www-users.cs.york.ac.uk/~schmuel/comp/comp.html http://www.cs.ucr.edu/~neal/1996/cosc185-S96/shor/high-level.html http://www.cs.york.ac.uk/~schmuel/ http://www.theory.caltech.edu/people/preskill/ph229/notes/chap6.ps http://www.fi.muni.cz/usr/gruska/survey1.ps http://scottaaronson.com/blog/%3Fp=208 https://quantum-algorithms.herokuapp.com/ https://quantum-algorithms.herokuapp.com/299/paper.pdf https://quantum-algorithms.herokuapp.com/299/paper.ps https://quantum-algorithms.herokuapp.com/299/paper.tex http://www.cs.princeton.edu/theory/complexity/quantumchap.pdf http://www.scottaaronson.com/blog/%3Fp=208%23comment-5187 http://homepages.cwi.nl/~rdewolf/publ/qc/survey.ps |
| dbo:wikiPageID | 42674 (xsd:integer) |
| dbo:wikiPageLength | 41394 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124429495 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Quantum_computer dbr:Quantum_entanglement dbr:Quantum_logic_gate dbr:Quantum_noise dbr:Qubit dbr:Root_of_unity dbr:Scott_Aaronson dbr:Euler's_totient_theorem dbc:Integer_factorization_algorithms dbr:Peter_Shor dbr:Integer_factorization dbr:Continued_fraction dbr:Measurement_in_quantum_mechanics dbr:Prime_factor dbr:Quantum_algorithm dbr:Quantum_cloning dbr:Quantum_decoherence dbr:Fundamental_theorem_of_arithmetic dbr:General_number_field_sieve dbr:Greatest_common_divisor dbr:Modular_arithmetic dbr:Modular_exponentiation dbr:Lenstra_elliptic-curve_factorization dbr:Shor's_algorithm dbr:Complexity_class dbr:Composite_number dbr:Post-quantum_cryptography dbr:Public-key_cryptography dbr:Quantum_superposition dbr:BQP dbr:Bézout's_identity dbr:Adder_(electronics) dbc:Quantum_algorithms dbr:Time_complexity dbr:Divisor dbr:Hadamard_transform dbr:Irreducible_fraction dbr:No-cloning_theorem dbr:Cyclic_group dbr:Euclidean_algorithm dbr:Euler's_totient_function dbr:Exponentiation_by_squaring dbr:Nontrivial dbr:PBS_Digital_Studios dbr:Discrete_logarithm dbr:Diffie-Hellman dbr:Quantum_gate dbr:Quadratic_sieve dbr:Quantum_Fourier_transform dbr:Group_(mathematics) dbr:Group_homomorphism dbr:Hadamard_gate dbr:Tensor_product dbr:Separable_state dbr:Chinese_remainder_theorem dbr:Hidden_subgroup_problem dbr:Divides dbc:Post-quantum_cryptography dbr:Coprime dbr:Grover's_algorithm dbr:Polynomial_time dbr:IBM dbr:IBM_Q_System_One dbr:Imaginary_unit dbr:Order_(group_theory) dbr:RSA_(cryptosystem) dbr:Nuclear_magnetic_resonance_quantum_computer dbr:Sub-exponential_time dbr:Photonics dbr:Multiplicative_group_of_integers_modulo_n dbr:Interference_(wave_propagation) dbr:Periodic_function dbr:Reversible_computing dbr:Quantum_phase_estimation dbr:Positive_real_axis dbr:Exponentiating_by_squaring dbr:Primality_testing dbr:File:Shor's_algorithm.svg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Cite_arXiv dbt:More_footnotes_needed dbt:Ordered_list dbt:Reflist dbt:Short_description dbt:Technical dbt:Isbn dbt:Number_theoretic_algorithms dbt:Quantum_computing |
| dcterms:subject | dbc:Integer_factorization_algorithms dbc:Quantum_algorithms dbc:Post-quantum_cryptography |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatIntegerFactorizationAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms yago:WikicatQuantumAlgorithms |
| rdfs:comment | خوارزمية شوور (بالإنجليزية: Shor's algorithm) هي خوارزمية لتفكيك عدد طبيعي N في زمن ((log N)3) وفي مساحة (O(log N. تحمل هاته الخوارزمية اسم بيتر شور. (ar) Het algoritme van Shor, vernoemd naar de Amerikaanse wiskundige Peter Shor die het in 1994 formuleerde, is een kwantumalgoritme (dat is een algoritme dat op een kwantumcomputer draait) voor het ontbinden in priemfactoren. Informeel lost het het volgende probleem op: vind, gegeven een geheel getal N, zijn priemfactoren. (nl) 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. (it) Na teoria da complexidade computacional e em Computação quântica, o algoritmo de Shor, batizado em homenagem ao matemático Peter Shor, é um algoritmo quântico para fatorar um número N não primo de L bits. Usando bits quânticos, ou qubits reciclados, o cálculo quântico de Shor é utilizado, explorando a mecânica quântica, para simplificar a fatoração de números em um produto de números primos - uma tarefa difícil para os computadores comuns, clássico, quando os números ficam muito grandes. Até 2012, o maior número fatorado usando o algoritmo de Shor era 15. (pt) Алгоритм Шора — факторизації (розкладання числа на прості множники), що дозволяє розкласти число за час , використовуючи логічних кубітів. Алгоритм Шора був розроблений Пітером Шором в 1994 році. Сім років по тому, в 2001 році, його працездатність була продемонстрована групою фахівців IBM. Число 15 було розкладено на множники 3 і 5 за допомогою квантового комп'ютера з 7 кубітами. (uk) Алгори́тм Шо́ра — квантовый алгоритм факторизации (разложения числа на простые множители), позволяющий разложить число за время , используя логических кубитов. Алгоритм Шора был разработан Питером Шором в 1994 году. Семь лет спустя, в 2001 году, его работоспособность была продемонстрирована группой специалистов IBM. Число 15 было разложено на множители 3 и 5 при помощи квантового компьютера с 7 кубитами. (ru) L'algorisme de Shor és un algorisme quàntic per descompondre en factors un nombre N en temps O ((log N)3) i espai O(log N), així nomenat per Peter Shor. Moltes criptografies de clau pública, com ara RSA, arribarien a ser obsoletes si l'algorisme de Shor és implementat alguna vegada en un 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((logN)k) per a cap k, de manera que arriben a ser ràpidament poc pràctics a mesura que s'augmentaN. Per contra, l'algorisme de Shor pot en temps polinòmic. També s'ha ampliat per atacar moltes altres criptografies de clau pública. (ca) 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. (de) 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((log N)3) y espacio O(logN), así nombrado por Peter Shor. El algoritmo de Shor es un procedimiento que permite encontrar factores de un número de una manera eficiente. La implementación de este algoritmo se puede llevar a cabo de manera clásica o utilizando (que no han sido llevados a la práctica todavía). Esta última implementación es (por supuesto) la más conveniente cuando se desea encontrar el orden, un parámetro muy necesario a la hora de encontrar los factores primos de un cierto número. (es) En arithmétique modulaire et en informatique quantique, l’algorithme de Shor est un algorithme quantique conçu par Peter Shor en 1994, qui factorise un entier naturel N en temps O et en espace . Beaucoup de cryptosystèmes à clé publique, tels que le RSA, deviendraient vulnérables si l'algorithme de Shor était un jour implanté 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. Les algorithmes classiques connus deviennent donc rapidement impraticables quand N augmente, à la différence de l'algorithme de Shor qui peut casser le RSA en temps poly (fr) Shor's algorithm is a quantum computer algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. On a quantum computer, to factor an integer , Shor's algorithm runs in polynomial time, meaning the time taken is polynomial in , the size of the integer given as input. Specifically, it takes quantum gates of order using fast multiplication, or even utilizing the asymptotically fastest multiplication algorithm currently known due to Harvey and Van Der Hoven, thus demonstrating that the integer factorization problem can be efficiently solved on a quantum computer and is consequently in the complexity class BQP. This is almost exponentially faster than the most efficient known classical factoring algorithm, the general number fiel (en) 쇼어 알고리즘(Shor's algorithm)은 소인수 분해를 빠르게 처리할 수 있는 양자 알고리즘이다. 수학자 피터 쇼어가 제안했다. 쇼어 알고리즘을 사용하면 크기가 인 수를 소인수 분해할 때 의 시간과 의 저장공간이 필요하다. 쇼어는 이 업적으로 국제수학자회의에서 가우스상을 받았다. 이 알고리즘의 가장 중요한 점은 이것을 이용하면 공개 키 암호 방식을 쉽게 깰 수 있다는 점이다. 예를 들어 RSA의 경우, 매우 큰 두 개의 소수를 곱한 값을 공개 열쇠 으로 사용한다. 이와 같은 방식이 안전한 이유는 을 빠른 시간 안에 효율적으로 소인수 분해하는 알고리즘이 지금까지 발견되지 않았기 때문이다. 그러나 쇼어 알고리즘을 충분히 큰 수에 대해서 적용할 수 있는 기계가 만들어지면, 오늘날의 공개 키 암호 방식은 모두 무용지물이 된다. 이런 점에서 쇼어 알고리즘은 양자 컴퓨터의 킬러 애플리케이션(killer application)인 셈이다. 그래서 양자암호와 양자 후 암호 기술이 개발되고 있다. (ko) Kwantowy algorytm Shora – algorytm kwantowy umożliwiający rozkład na czynniki pierwsze liczby naturalnej N w czasie i wykorzystując pamięć 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. (pl) 秀爾演算法（英語：Shor's algorithm）是一個于1994年發現的，以數學家彼得·秀爾命名，針對整數分解題目的的量子演算法（在量子計算機上面運作的演算法）。不正式地說，它解決的題目是：給定一個整數 ，找出它的質因數。在一個量子計算機上面，要分解整數，秀爾演算法的運作需要多項式時間（時間是 的某個多項式這麼長， 在這裡的意義是輸入的檔案長度）。准确来说，该演算法花費 的時間，展示出質因數分解問題可以使用量子計算機以多項式時間解出，因此在複雜度類BQP裡面。這比傳統上已知的最快的因數分解演算法普通數域篩選法所花費的次指數時間——大約 還要快了一個指數。 秀爾演算法非常重要，它意味着：假如有可用的量子計算機，我們可以破解基于公開密鑰加密的算法（比如RSA加密演算法）。RSA演算法的基礎在於假設了我們不能有效率的分解一個已知的整數。就目前所知，這假設對傳統（即非量子）的電腦為真；沒有已知的傳統演算法可以在多項式時間內解決這個問題。但秀爾演算法展示了因數分解問題在量子計算機上可以很有效率的解決，所以一個足夠大的量子計算機可以破解RSA。這對於建立量子計算機和研究新的量子計算機演算法是一個强大的動力。 (zh) |
| rdfs:label | خوارزمية شور (ar) Algorisme de Shor (ca) Shor-Algorithmus (de) Algoritmo de Shor (es) Algorithme de Shor (fr) Algoritmo di fattorizzazione di Shor (it) 쇼어 알고리즘 (ko) Algoritme van Shor (nl) Algorytm faktoryzacji Shora (pl) Shor's algorithm (en) Алгоритм Шора (ru) Algoritmo de Shor (pt) 秀爾演算法 (zh) Алгоритм Шора (uk) |
| owl:sameAs | freebase:Shor's algorithm yago-res:Shor's algorithm wikidata:Shor's algorithm dbpedia-ar:Shor's algorithm dbpedia-bg:Shor's algorithm dbpedia-ca:Shor's algorithm dbpedia-da:Shor's algorithm dbpedia-de:Shor's algorithm dbpedia-es:Shor's algorithm dbpedia-fa:Shor's algorithm dbpedia-fi:Shor's algorithm dbpedia-fr:Shor's algorithm dbpedia-he:Shor's algorithm http://hi.dbpedia.org/resource/शोर_का_अल्गोरिद्म dbpedia-hu:Shor's algorithm dbpedia-it:Shor's algorithm dbpedia-ko:Shor's algorithm dbpedia-lmo:Shor's algorithm http://lt.dbpedia.org/resource/Šoro_algoritmas dbpedia-nl:Shor's algorithm dbpedia-pl:Shor's algorithm dbpedia-pt:Shor's algorithm dbpedia-ru:Shor's algorithm dbpedia-sh:Shor's algorithm dbpedia-simple:Shor's algorithm dbpedia-sr:Shor's algorithm dbpedia-th:Shor's algorithm dbpedia-tr:Shor's algorithm dbpedia-uk:Shor's algorithm dbpedia-vi:Shor's algorithm dbpedia-zh:Shor's algorithm https://global.dbpedia.org/id/5679P |
| prov:wasDerivedFrom | wikipedia-en:Shor's_algorithm?oldid=1124429495&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Shor's_algorithm.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Shor's_algorithm |
| is dbo:knownFor of | dbr:Peter_Shor__Peter_Shor__1 |
| is dbo:wikiPageDisambiguates of | dbr:Shor |
| is dbo:wikiPageRedirects of | dbr:Shor's_Algorithm dbr:Shors_algorithm dbr:Quantum_factoring dbr:Shor_algorithm dbr:Shor_factorization_algorithm dbr:Shor_s_algorithm |
| is dbo:wikiPageWikiLink of | dbr:Quantum_logic_gate dbr:List_of_algorithms dbr:Micius_Quantum_Prize dbr:Merkle_signature_scheme dbr:Primality_test dbr:Peter_Shor dbr:Charge_qubit dbr:Uncertainty_principle dbr:ECRYPT dbr:Index_of_cryptography_articles dbr:Index_of_physics_articles_(S) dbr:Integer_factorization dbr:Integer_factorization_records dbr:Quantum_computing dbr:List_of_group_theory_topics dbr:List_of_mathematical_proofs dbr:List_of_number_theory_topics dbr:Simon's_problem dbr:Timeline_of_quantum_computing_and_communication dbr:15_(number) dbr:Computer dbr:McEliece_cryptosystem dbr:Elliptic-curve_cryptography dbr:One-time_pad dbr:Quantum_Computing:_A_Gentle_Introduction dbr:Quantum_algorithm dbr:Quantum_cloning dbr:Quantum_information_science dbr:Timeline_of_algorithms dbr:Timeline_of_fundamental_physics_discoveries dbr:Timeline_of_mathematics dbr:Modular_exponentiation dbr:Cryptographic_agility dbr:Quantum_technology dbr:Shor's_Algorithm dbr:Shor's_algorithm dbr:Stack_Exchange dbr:Computational_complexity dbr:Computational_complexity_of_mathematical_operations dbr:Computational_complexity_theory dbr:House_system_at_the_California_Institute_of_Technology dbr:Identity-based_encryption dbr:Key_size dbr:Quantum_annealing dbr:Post-quantum_cryptography dbr:Quantum_supremacy dbr:BQP dbr:Gödel_Prize dbr:Hadamard_transform dbr:Lattice-based_cryptography dbr:Daniel_J._Bernstein dbr:Euclidean_algorithm dbr:DiVincenzo's_criteria dbr:Discrete_logarithm dbr:Fourier_transform_on_finite_groups dbr:History_of_quantum_mechanics dbr:List_of_Massachusetts_Institute_of_Technology_faculty dbr:Lov_Grover dbr:QuEST dbr:Quantum_Fourier_transform dbr:Quantum_cryptography dbr:Quantum_digital_signature dbr:RSA_Factoring_Challenge dbr:2001_in_science dbr:Prime_number dbr:Hidden_subgroup_problem dbr:Boson_sampling dbr:Grover's_algorithm dbr:Krysta_Svore dbr:OProject@Home dbr:RSA_(cryptosystem) dbr:Knapsack_cryptosystems dbr:MIT_Center_for_Theoretical_Physics dbr:Nuclear_magnetic_resonance_quantum_computer dbr:Shor dbr:Supersingular_isogeny_key_exchange dbr:Umesh_Vazirani dbr:Neural_cryptography dbr:IMU_Abacus_Medal dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Quantum_finance dbr:NTRU dbr:Natural_computing dbr:Quantum_information dbr:Noisy_intermediate-scale_quantum_era dbr:Quantum_phase_estimation_algorithm dbr:P_versus_NP_problem dbr:Time-evolving_block_decimation dbr:Tanja_Lange dbr:Ring_learning_with_errors_signature dbr:Shors_algorithm dbr:Quantum_factoring dbr:Shor_algorithm dbr:Shor_factorization_algorithm dbr:Shor_s_algorithm |
| is dbp:knownFor of | dbr:Peter_Shor |
| is foaf:primaryTopic of | wikipedia-en:Shor's_algorithm |
