Wersja z 13:42, 26 kwi 2015 edytuj Daroooo (dyskusja \| edycje) Redaktorzy 7642 edycje m ency. Znacznik: VisualEditor ← poprzednia edycja		Wersja z 14:08, 26 kwi 2015 edytuj anuluj edycję Daroooo (dyskusja \| edycje) Redaktorzy 7642 edycje m formatowanie math następna edycja →
Linia 2: '''Rozkład na czynniki''' lub '''faktoryzacja''' – proces, w którym dla danego obiektu znajduje się obiekty, takie, że ich [[Mnożenie\|iloczyn]] jest jemu równy, przez co są one w pewnym sensie od niego prostsze. Faktoryzacja [[liczby całkowite]]j ''x'', czyli to co zwykle mamy na myśli mówiąc o ''faktoryzacji'', to znalezienie takich liczb całkowitych ''y<sub>1</sub>'', ''y<sub>2</sub>'', ..., ''y<sub>n</sub>'', że ich iloczyn jest równy danej liczbie: <math>x = ~~y_{1}y_{2}~~y_1 y_2 \cdots ~~y_{n}~~y_n</math>, przy czym żadne z ''y<sub>i</sub>'' nie może być równe 1 lub ''x'' (tzw. faktoryzacja trywialna). Faktoryzacja [[wielomian]]u 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 [[Zasadnicze twierdzenie algebry\|zasadniczym twierdzeniem algebry]] dowolny wielomian o stopniu ''n'' nad [[Ciało (matematyka)\|ciałem]] [[Liczby zespolone\|liczb zespolonych]] można rozłożyć na iloczyn ''n'' wielomianów 1. stopnia. Linia 14: Najprostszy algorytm 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: : <math>x^2 = y^2 \;(\operatorname{mod} n)</math> : <math>x^2 - y^2 = 0 \;(\operatorname{mod} n)</math> : <math>(x-y)(x+y) = 0 \;(\operatorname{mod} n)</math> Czyli albo <math>x = y \;(\operatorname{mod} n)</math>, albo <math>x = -y \;(\operatorname{mod} n)</math>, albo <math>n</math> ma wspólne dzielniki z <math>x-y</math> oraz <math>x+y</math>, a zatem sfaktoryzowaliśmy <math>n</math>. Najprostszą metodą tego typu jest sprawdzanie dla losowych liczb <math>z</math> czy <math>z^2 \;(\operatorname{mod} n)</math> jest kwadratem (zwykłym, nie modulo). Można szybko znaleźć faktoryzację niektórych liczb, ale ogólnie metoda ta nie jest dużo lepsza od prób dzielenia. O wiele lepszym sposobem jest wybranie zestawu małych liczb pierwszych i próby faktoryzacji kwadratów <math>z^2</math> kolejnych losowanych <math>z</math> liczb używając tylko tych liczb pierwszych – jeśli faktoryzacja się nie powiedzie należy odrzucić wylosowaną liczbę, jeśli się powiedzie trzeba zachować <math>z</math> i wykładniki: Linia 31: Otrzymuje się wtedy: : <math>x^2 = y^2 \;(\operatorname{mod} n)</math>, 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 czynniki pierwsze polega na znajdowaniu liczb o dobrych rozkładach, w znacznie krótszym czasie.

Rozkład na czynniki: Różnice pomiędzy wersjami