Rozkład na czynniki: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
wstawienie {{Kontrola autorytatywna}} |
Funkcja sugerowania linków: dodane 4 linki. Znaczniki: VisualEditor Z urządzenia mobilnego Z wersji mobilnej (przeglądarkowej) Zadanie nowicjusza Zasugerowano edycję: dodanie linków |
||
Linia 2:
'''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 bez (istotnego) wpływu na wynik, tj. produkt mniejszej liczby obiektów da obiekt o tożsamej strukturze (lub nawet dokładnie ten sam obiekt). 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żenie|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).
Linia 16:
=== Algorytmy faktoryzacji ===
Najprostsza metoda polega na próbie dzielenia faktoryzowanej liczby <math>n</math> przez wszystkie [[Liczba pierwsza|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:
Linia 39:
gdzie <math>x</math> to iloczyn odpowiednich <math>z,</math> a <math>y</math> to iloczyn odpowiednich <math>p_i</math> w potędze będącej połową sumy potęg dla <math>z</math> znajdujących się po lewej stronie. Z prawdopodobieństwem 50% (dla <math>n</math> będącego iloczynem 2 liczb) lub większym (dla <math>n</math> mającego więcej czynników) liczby te są nietrywialną taką parą <math>(x \ne y \;(\operatorname{mod} n),</math> <math>x \ne -y \;(\operatorname{mod} n)).</math> Jeśli tak nie jest, można próbować znaleźć inny zestaw liczb <math>z^2,</math> których iloczyn ma parzyste wykładniki.
Większość zaawansowanych algorytmów rozkładu na [[Czynnik pierwszy|czynniki pierwsze]] polega na znajdowaniu liczb o dobrych rozkładach w znacznie krótszym czasie.
== Wielomiany ==
{{zobacz też|wielomian|wielomian nieprzywiedlny}}
Faktoryzacja
== Zobacz też ==
| |||