• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Faktoryzacja



    Podstrony: 1 [2] [3]
    Przeczytaj także...
    Kwantowy algorytm Shora – algorytm kwantowy umożliwiający rozkład na czynniki pierwsze liczby naturalnej N w czasie O((log N)) 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.Teoria złożoności obliczeniowej – dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów.

    Rozkład na czynniki lub faktoryzacja – proces, w którym dla danego obiektu znajduje się obiekty, takie, że ich iloczyn jest jemu równy, przez co są one w pewnym sensie od niego prostsze.

    Faktoryzacja liczby całkowitej x, czyli to co zwykle mamy na myśli mówiąc o faktoryzacji, to znalezienie takich liczb całkowitych y1, y2, ..., yn, że ich iloczyn jest równy danej liczbie: , przy czym żadne z yi nie może być równe 1 lub x (tzw. faktoryzacja trywialna).

    Wielomian – wyrażenie algebraiczne złożone ze zmiennych i stałych połączonych działaniami dodawania, odejmowania, mnożenia i podnoszenia do potęgi o stałym wykładniku naturalnym.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.

    Faktoryzacja wielomianu to znalezienie takich wielomianów, że ich iloczyn jest równy danemu. W tym wypadku rozwiązanie nietrywialne nie może zawierać wielomianu o tym samym stopniu, co wielomian faktoryzowany. Zgodnie z zasadniczym twierdzeniem algebry dowolny wielomian o stopniu n nad ciałem liczb zespolonych można rozłożyć na iloczyn n wielomianów 1. stopnia.

    Zasadnicze (podstawowe) twierdzenie algebry – twierdzenie algebry i analizy zespolonej mówiące, że każdy wielomian zespolony stopnia dodatniego ma pierwiastek (w ciele liczb zespolonych). Innymi słowy, ciało liczb zespolonych jest algebraicznie domknięte. Konsekwencją zasadniczego twierdzenia algebry i twierdzenia Bézouta jest następujące twierdzenie (często zwane również zasadniczym twierdzeniem algebry):Liczby całkowite – liczby naturalne dodatnie N + = { 1 , 2 , 3 , … } {displaystyle mathbb {N} _{+}={1,2,3,dots }} oraz liczby przeciwne do nich { − 1 , − 2 , − 3 , … } {displaystyle {-1,-2,-3,dots }} , a także liczba zero. Uogólnieniem liczb całkowitych są liczby wymierne i tym samym liczby rzeczywiste, szczególnym przypadkiem liczb całkowitych są: liczby naturalne.

    Spis treści

  • 1 Złożoność obliczeniowa
  • 2 Algorytmy faktoryzacji
  • 3 Zobacz też
  • 4 Linki zewnętrzne


  • Podstrony: 1 [2] [3]



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

    Warto wiedzieć że... beta

    Algorytm Fermata to jedna z metod faktoryzacji, czyli rozkładu liczby na czynniki pierwsze. Metoda ta szybko znajduje rozkład n jeśli jego dzielniki są bliskie pierwiastkowi kwadratowemu z n. Z powodu istnienia tej metody, tworząc klucze kryptograficzne oparte na iloczynach liczb pierwszych (RSA), unika się iloczynów niewiele różniących się liczb.
    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.
    Mnożenie – działanie dwuargumentowe będące jednym z czterech podstawowych działań arytmetycznych. Mnożone elementy to czynniki (określane również jako mnożna i mnożnik), a jego wynik to iloczyn. Może być ono traktowane jako zapis wielokrotnego dodawania elementu do siebie.
    Sito kwadratowe (ang. Quadratic Sieve) to najszybszy znany algorytm do faktoryzacji liczb, które są krótsze niż 150 cyfr dziesiętnych.
    Ogólne sito ciała liczbowego (GNFS, ang. general number field sieve) jest najszybszym obecnie znanym algorytmem faktoryzacji dużych (ponad 100-cyfrowych) liczb. Używając tego algorytmu, zespół z Uniwersytetu w Bonn (wspólnie z kilkoma innymi instytutami) 3 grudnia 2003 rozłożył na czynniki pierwsze liczbę RSA-576 (mającą 576 bitów, czyli 174 cyfry dziesiętne), a 2 listopada 2005 rozłożył liczbę RSA-640 (mającą 193 cyfry dziesiętne). Pierwsze obliczenie wymagało około 3 miesięcy pracy, a drugie około 5 miesięcy.
    Ciało – struktura formalizująca własności algebraiczne liczb wymiernych, czy liczb rzeczywistych. W trakcie badań nad tymi obiektami rozwinął się aparat matematyczny (tzw. teoria Galois) umożliwiający rozwiązanie takich problemów jak rozwiązalność równań wielomianowych (jednej zmiennej) przez tzw. pierwiastniki (działania obowiązujące w ciałach i wyciąganie pierwiastków), czy wykonalność pewnych konstrukcji klasycznych (konstrukcji geometrycznych, w których dozwolone jest korzystanie z wyidealizowanych cyrkla i linijki). Działem matematyki zajmującym się opisem tych struktur jest teoria ciał.
    Rho Pollarda to algorytm rozkładu liczb na czynniki pierwsze, opracowany przez Johna Pollarda w 1975 roku. Jest szczególnie efektywny przy rozkładaniu liczb mających niewielkie dzielniki. Dla liczb będących iloczynem dwóch liczb pierwszych tej samej długości, jego złożoność jest rzędu O(n polylog(n)).

    Reklama

    Czas generowania strony: 0.03 sek.