Rozkład na czynniki: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
Luckas-bot (dyskusja | edycje) m robot dodaje: el:Παραγοντοποίηση |
poprawa linków |
||
Linia 1:
{{disambigP|Rozkład na czynniki|[[Czynnik pierwszy|czynniki pierwsze]]}}
'''Rozkład na czynniki''' lub '''faktoryzacja''' – proces, w którym dla danego obiektu znajdują się obiekty, takie że ich [[Mnożenie|iloczyn]] jest jemu równy, przez co są one w pewnym sensie od niego prostsze.
Linia 7:
== 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ę [[
Przykład: mając dwie liczby 65537 i 65539, można szybko je pomnożyć uzyskując 4295229443. Jednak aby rozłożyć 4295229443 na czynniki trzeba próbować podzielić je przez wszystkie liczby pierwsze po kolei, aż natrafi się na właściwe czynniki. Dla bardzo dużych liczb możliwych czynników pierwszych będzie o wiele za dużo, żeby dało się je wszystkie sprawdzić. Istnieją efektywniejsze algorytmy (takie jak [[sito kwadratowe]] i [[GNFS]]), jednak wszystkie one działają w czasie wykładniczym wobec długości rozkładanej liczby.
| |||