Faktoryzacja - Polski Serwis Naukowy

przekierowanie z „Rozkład na czynniki”. Zapoznaj się również z: czynniki pierwsze.

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.

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: $x = y_{1}y_{2}\cdots y_{n}$ , przy czym żadne z yi nie może być równe 1 lub x (tzw. faktoryzacja trywialna).

RSA - jeden z pierwszych i obecnie jeden z najpopularniejszych asymetrycznych algorytmów kryptograficznych, zaprojektowany w 1977 przez Rona Rivesta, Adi Shamira oraz Leonarda Adlemana. Pierwszy, który można stosować 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.
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). Konsekwencją zasadniczego twierdzenia algebry i twierdzenia Bézout jest następujące twierdzenie (często zwane również Zasadniczym twierdzeniem algebry):

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.

Liczby zespolone – liczby będące elementami rozszerzenia ciała liczb rzeczywistych o jednostkę urojoną i, tj. pierwiastek wielomianu x + 1 (innymi słowy, jednostka urojona spełnia równanie i = − 1). Każda liczba zespolona z może być zapisana w postaci z = a + bi, gdzie a,b są pewnymi liczbami rzeczywistymi, nazywanymi odpowiednio częścią rzeczywistą oraz częścią urojoną liczby z.
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.

czytaj dalej: [2], [3]

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