• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Algorytm faktoryzacji Shora



    Podstrony: 1 [2] [3]
    Przeczytaj także...
    Algorytm szybkiego potęgowania – metoda pozwalająca na szybkie obliczenie potęgi o wykładniku naturalnym. Metoda ta wykorzystuje pośrednio dwójkową reprezentację wykładnika potęgi, a jej złożoność, wyrażona jako liczba wykonywanych mnożeń, wynosi Θ ( log ⁡ n ) {displaystyle Theta (log n)} , gdzie n oznacza wykładnik obliczanej potęgi.Kryptografia klucza publicznego (nazywana również kryptografią asymetryczną) to rodzaj kryptografii, w którym używa się zestawów dwu lub więcej powiązanych ze sobą kluczy, umożliwiających wykonywanie różnych czynności kryptograficznych. Jeden z kluczy może być udostępniony publicznie bez utraty bezpieczeństwa danych zabezpieczanych tym kryptosystemem.

    Kwantowy algorytm Shoraalgorytm 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.

    RSA – jeden z pierwszych i obecnie najpopularniejszych asymetrycznych algorytmów kryptograficznych z kluczem publicznym, zaprojektowany w 1977 przez Rona Rivesta, Adi Shamira oraz Leonarda Adlemana. Pierwszy algorytm, który może być stosowany zarówno do szyfrowania jak i do podpisów cyfrowych. Bezpieczeństwo szyfrowania opiera się na trudności faktoryzacji dużych liczb złożonych. Jego nazwa pochodzi od pierwszych liter nazwisk jego twórców.Rozkład na czynniki lub faktoryzacja – proces, w którym dla danego obiektu znajdują się obiekty, takie że ich iloczyn jest jemu równy, przez co są one w pewnym sensie od niego prostsze.

    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.

    Grupa – jedna ze struktur algebraicznych: zbiór niepusty, na którym określono pewne łączne działanie dwuargumentowe wewnętrzne, dla którego istnieje element odwrotny do każdego elementu oraz element neutralny. Można powiedzieć, że grupą jest monoid, w którym każdy element ma element odwrotny. Dział matematyki badający własności grup nazywa się teorią grup.Superpozycja – własność rozwiązań równania różniczkowego przejawiająca się w tym, że suma dwóch rozwiązań także jest rozwiązaniem równania. W podstawowym sensie własność ta może zostać wyrażona w inny sposób przez twierdzenie, że przestrzeń rozwiązań równania jest przestrzenią liniową. Tak wyrażone twierdzenie pozostaje prawdziwe, jeśli równanie różniczkowe jest liniowe.

    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.

    Rząd – w teorii grup pojęcie oddające intuicję „rozmiaru” (w sensie „rzędu wielkości”) danej grupy i ułatwiające przy tym opis jej podgrup; w szczególności rzędem elementu nazywa się rząd („rozmiar”) najmniejszej (pod)grupy zawierającej ten element.Kryptografia klucza publicznego (nazywana również kryptografią asymetryczną) to rodzaj kryptografii, w którym używa się zestawów dwu lub więcej powiązanych ze sobą kluczy, umożliwiających wykonywanie różnych czynności kryptograficznych. Jeden z kluczy może być udostępniony publicznie bez utraty bezpieczeństwa danych zabezpieczanych tym kryptosystemem.

    Spis treści

  • 1 Procedura realizacji
  • 1.1 Część klasyczna
  • 1.2 Część kwantowa: Znajdowanie okresu funkcji
  • 2 Analiza algorytmu
  • 2.1 Część klasyczna
  • 2.2 Część kwantowa
  • 3 Przypisy
  • 4 Literatura


  • Podstrony: 1 [2] [3]



    w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Warto wiedzieć że... beta

    Spektroskopia magnetycznego rezonansu jądrowego, spektroskopia NMR (ang. Nuclear Magnetic Resonance) – jedna z najczęściej stosowanych obecnie technik spektroskopowych w chemii i medycynie.
    Peter W. Shor (ur. 14 sierpnia 1959 roku w USA) – amerykański informatyk teoretyk i matematyk, autor kwantowego Algorytmu Shora. Algorytm Shora służy do rozkładu na czynniki pierwsze bardzo dużych liczb naturalnych z wykorzystaniem komputera kwantowego.
    Komputer kwantowy – układ fizyczny do opisu którego wymagana jest mechanika kwantowa, zaprojektowany tak, aby wynik ewolucji tego układu reprezentował rozwiązanie określonego problemu obliczeniowego.
    Kwantowa transformata Fouriera (ang. quantum Fourier transform, QFT) – kwantowa analogia dyskretnej transformaty Fouriera. Na dowolny n-kubitowy stan bazowy | j ⟩ {displaystyle |j angle } działa ona jak następuje:
    Algorytm kwantowy – rodzaj algorytmu przeznaczonego do działania na maszynie kwantowej (komputer kwantowy). Dotychczas powstało kilkanaście algorytmów wykorzystujących możliwości oferowane przez maszyny kwantowe. Należą do nich algorytmy Grovera, Deutscha, Simona, Shora, Kitaeva i Bernsteina-Vaziraniego.
    Bramka Hadamarda (ozn. w skrócie symbolem H) – jednokubitowa bramka kwantowa reprezentowana przez 2-wymiarową macierz unitarną będącą iloczynem 2 − 1 {displaystyle {sqrt {2}},^{-1}} i macierzy Hadamarda:
    Uniwersytet Stanforda, The Leland Stanford Junior University (ang. Stanford University) – prywatny uniwersytet w Stanfordzie, w Kalifornii, w Stanach Zjednoczonych, w Dolinie Krzemowej.

    Reklama

    Czas generowania strony: 0.029 sek.