Rozkład na czynniki: Różnice pomiędzy wersjami
[wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
drobne redakcyjne |
Nie podano opisu zmian |
||
Linia 1:
{{spis treści}}
'''Rozkład na czynniki''' lub '''faktoryzacja''' – proces w kategorii obiektów wyposażonej w produkt, tj. iloczyn (rozumiany być może w szerokim sensie), który dla danego obiektu matematycznego <math>x</math> prowadzi do wskazania takich (pod)obiektów, których iloczyn jest równy <math>x.</math> Obiekty wynikowe nazywa się ''czynnikami'' lub ''dzielnikami'' (faktorami) obiektu <math>x</math>.
Zwykle wymaga się, by rozkład nie zawierał czynników, które mogą być z niego usunięte, ponieważ w iloczynie dają obiekt o tożsamej strukturze. W szczególności unika się [[trywialność (matematyka)|trywialnych rozwiązań]] postaci: obiekt i obiekt jednostkowy. Ważną cechą rozkładu na czynniki jest też jego jednoznaczność, która ma miejsce wtedy, gdy istnieje wyłącznie jeden rozkład obiektu (niezależny od użytej metody), zwykle z dodatkowymi wyłączeniami, np. kolejności czynników w rozkładzie w przypadku [[przemienność|przemienności]] mnożenia.
Przez wyrażenie „rozkład na czynniki” rozumie się zazwyczaj rozkład na czynniki [[liczby całkowite]]j lub [[liczby naturalne|naturalnej]] (w drugim przypadku rozkład jest jednoznaczny, zachodzi równość; w pierwszym – z wyłączeniem/dokładnością do znaku czynników; w obu: nie uwzględniając kolejności czynników).
== Liczby całkowite ==
Linia 9 ⟶ 10:
Faktoryzacja liczby całkowitej <math>x</math> polega na znalezieniu takich liczb całkowitych <math>y_1, y_2, \dots, y_n,</math> że ich iloczyn jest równy danej liczbie: <math>x = y_1 y_2 \cdots y_n.</math> Domyślnie żąda się nietrywialności rozkładu: żaden z czynników <math>y_i</math> nie może być równy 1 lub <math>x</math>.
=== Złożoność obliczeniowa ===
O ile mnożenie jest bardzo prostą czynnością, to nie są znane żadne szybkie (działające w czasie wielomianowym względem ilości cyfr rozkładanej liczby) metody faktoryzacji. Na [[Złożoność obliczeniowa|złożoności obliczeniowej]] faktoryzacji opiera się [[Kryptografia klucza publicznego|system kryptografii asymetrycznej]] [[RSA (kryptografia)|RSA]].
Przykład: mając dwie liczby 65 537 i 65 539, można szybko je pomnożyć, uzyskując 4 295 229 443. Jednak rozłożenie 4295 229 443 na czynniki jest trudne. Wszystkie znane algorytmy działają w czasie wykładniczym wobec długości rozkładanej liczby.
=== Algorytmy faktoryzacji ===
Niektóre algorytmy opierają się na znajdowaniu takiej pary liczb <math>x</math> i <math>y,</math> gdzie <math>(x \ne y \;(\operatorname{mod} n),</math> <math>x \ne -y \;(\operatorname{mod} n)),</math> że:
|