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&nbsp;537 i 65&nbsp;539, można szybko je pomnożyć, uzyskując 4&nbsp;295&nbsp;229&nbsp;443. Jednak rozłożenie 4295&nbsp;229&nbsp;443 na czynniki jest trudne. Wszystkie znane algorytmy działają w czasie wykładniczym wobec długości rozkładanej liczby.
 
=== Algorytmy faktoryzacji ===
NajprostszyNajprostsza algorytmmetoda polega na próbie dzielenia faktoryzowanej liczby <math>n</math> przez wszystkie liczby pierwsze od 2 do <math>\sqrt n.</math> Algorytm ten dobrze nadaje się do tego, żeby zacząć faktoryzować liczbę – losowa liczba ma zarówno małe, jak i duże czynniki. Połowa liczb dzieli się przez 2, co trzecia przez 3, co piąta przez 5 itd. Jeśli więc faktoryzowana liczba jest losowa, można z bardzo dużym prawdopodobieństwem pozbyć się szybko niskich czynników, po czym skończyć faktoryzację innym algorytmem. W najgorszym przypadku (<math>n</math> jest iloczynem dwóch liczb pierwszych podobnej wielkości, jak w [[RSA (kryptografia)|RSA]]) algorytm ten zajmie bardzo dużo czasu.
 
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: