Prvočíselný rozklad

Z Multimediaexpo.cz

Prvočíselný rozklad je matematický pojem z oboru aritmetiky. Jedná se o vyjádření přirozeného čísla jako součinu mocnin prvočísel.

Definice

Nechť je \(x\) přirozené číslo větší než 1. Za jeho prvočíselný rozklad označíme zápis

\(p_1^{m_1} \cdot p_2^{m_2} \cdot p_3^{m_3} \cdots p_n^{m_n}\),

který splňuje následující podmínky:

1. \(p_1^{m_1} \cdot p_2^{m_2} \cdots p_n^{m_n} = x\),
2. \(n > 0, m_1 > 0, m_2 > 0, \ldots, m_n > 0\) jsou kladná celá čísla,
3. \(p_1 < p_2 < \ldots < p_n\) jsou vzájemně různá prvočísla seřazená podle velikosti.

Příklady

Několik příkladů prvočíselných rozkladů (jedničkové mocniny se v zápisu vynechávají):

• \(2 = 2\)
• \(3 = 3\)
• \(4 = 2^2\)
• \(6 = 2 \cdot 3\)
• \(8 = 2^3\)
• \(12 = 2^2 \cdot 3\)
• \(15 = 3 \cdot 5\)
• \(1800 = 2^3 \cdot 3^2 \cdot 5^2\)
• \(9699690 = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19\)
• \(4127911259 = 50177 \cdot 82267\)

Základní věta aritmetiky

Podrobnější informace naleznete na stránce: Základní věta aritmetiky

Nabízí se otázka, zda takovýto rozklad existuje pro každé přirozené číslo větší než 1, a zda je určen jednoznačně (tj. zda nelze nějaké číslo takto rozložit na prvočísla více způsoby).

Kladnou odpověď (tj. „prvočíselný rozklad existuje pro každé číslo a je vždy jednoznačný“) dává tzv. základní věta aritmetiky.

Metody faktorizace

Hrubou silou

Pro malá čísla lze postupovat hrubou silou: rozkládané číslo postupně zkoušet dělit všemi prvočísly. Tento algoritmus je sice jednoduše pochopitelný a implementovatelný, jeho složitost je ale exponenciální, pro větší čísla je proto nepoužitelný.

Příklad implementace

Následující kód je v jazyce Python.

import math
def rozklad_delenim(cislo):
  horni_mez = int(math.sqrt(cislo))
  prvocisla = eratosthenovo_sito(horni_mez)
  rozklad = []
  for prvocislo in prvocisla:
    while cislo % prvocislo == 0:
      rozklad.append(prvocislo)
      cislo /= prvocislo
  if cislo != 1:
    rozklad.append(cislo)
  return rozklad

V příkladu je volána funkce eratosthenovo_sito(), což je implementace Eratosthenova síta.

Metody faktorizace použitelné pro větší čísla

Zatímco vynásobení dvou nebo více prvočísel je jednoduchá úloha, opačný proces, nazývaný rozkládání neboli faktorizace, je v obecném případě obtížný. Není znám žádný algoritmus, který by to dokázal v polynomiálním (vzhledem k velikosti vstupu tj. délce binárního zápisu složeného čísla) čase. Rozklad násobku dvou náhodně vybraných prvočísel o celkové velikosti 1024 bitů je prakticky neproveditelný i na dnešních počítačích a s využitím nejlepších známých algoritmů. Této skutečnosti se využívá v kryptografii, zejména v algoritmu RSA.

Obecně postupujeme tak, že nalezneme jednoho netriviálního dělitele D a spustíme faktorizaci na N/D a D. Po odstranění dělitele jenž je součinem malých prvočísel vždy testujeme, zda zbytek je prvočíslo (například Millerovým-Rabinovým testem prvočíselnosti) a pokračujeme jen v případě negativní odpovědi. Nejsložitějším krokem faktorizace je nalezení předposledního co do velikosti prvočíselného dělitele.

Algoritmy jejichž složitost je závislá na velikosti dělitelů

• faktorizace postupným dělením zkouší postupně dělit všemi čísly (v lepším případě jen prvočísly). Algoritmus končí když nalezneme dělitele nebo když nám dojde trpělivost. Má smysl jen při faktorizaci čísel, kde očekáváme hodně malých dělitelů.
• Pollardův ró algoritmus: Zvolme náhodný polynom f(x) (typicky binom) a počítejme postupně pro x₀=2, y₀=2 posloupnosti x_i+1=f(x_i), y_i+1=f(f(y_i)). Je-li NSD(x_i-y_i,N) rovno jedné, pokračujme. Jinak buď algoritmus selhal, nebo jsme našli netriviálního dělitele. Protože násobení je rychlejší než počítání NSD, je možno algoritmus urychlit násobením několika rozdílů a počítání NSD tohoto součinu s N. Pohybujeme se tak po blocích. Je-li výsledkem N, je možno poslední blok zpracovat po jednotlivých rozdílech. Algoritmus pak selže za stejných okolností jako neurychlený algoritmus. Algoritmus je založen na tom, že je pravděpodobné, že délky cyklů funkce f jsou modulo jednotlivé dělitele čísla N různě dlouhé. Pokud se modulo některý dělitel dostaneme do stejného čísla v obou posloupnostech, bude rozdíl dělitelný tímto dělitelem.
• Pollardův p-1 algoritmus: Zvolme B a spočtěme pro všechna prvočísla menší než B nejvyšší mocninu menší než B a spočtěme jejich součin M. Zvolme a, například a=2 a spočtěme NSD(a^M-1,N). Algoritmus selhal, pokud jsme nedostali netriviálního dělitele N. Algoritmus je založen na malé Fermatově větě. Je-li D prvočíselný dělitel N, pak a^k(D-1)-1 je dělitelné D. Pokud D-1 dělí M, bude tedy a^M-1 dělitelné D. Pokud je společný dělitel roven jedné, můžeme zkusit zvětšit B. Pokud je roven N, můžeme zkusit B zmenšit.
• Lenstrova faktorizace pomocí eliptických křivek: Algoritmus založený na principu Pollardova p-1 algoritmu, ale začíná náhodnou volbou eliptické křivky, která následně definuje aritmetickou operaci sčítání bodů na křivce. Při této operaci je použito NSD(x,N) jakožto podoperace a v případě, když x je dělitel N, operace selže. Algoritmus pracuje tak, že počítáme pro náhodně zvolený bod P na křivce hodnotu MP (kde M je z Pollardova p-1 algoritmu). Samozřejmě nesčítáme po jedné, ale sčítáme mezisoučty. Pokud sčítání selže, našli jsme dělitele. Pokud sčítání neselže, selhal algoritmus. Výhoda tohoto algoritmu je, že náhodnou volbou eliptické křivky dostaneme dostatečně náhodnou délku cyklu pro jednotlivé dělitele D čísla N. Úspěšnost rozložení čísla N nezáleží proto na hladkosti čísla D-1 ale na hladkosti délky cyklu. Při volbě prvočísel pro RSA klíč se můžeme snadno vyvarovat hladkosti P-1 i P+1 (můžeme P otestovat a prvočíslo případně zahodit). Úspěšnosti faktorizace Lenstrovým algoritmem při šťastné volbě eliptické křivky se ale neubráníme.

Algoritmy jejichž složitost je možno odhadnout na základě velikosti faktorizovaného čísla

Tyto algoritmy typicky hledají dvě čísla x, y tak aby \( x^2\equiv y^2\pmod N \) a jeden z faktorů získají pomocí NSD(x-y,N). Důvodem je vztah \(x^2-y^2\equiv (x-y)(x+y)\). Předpokladem úspěšnosti faktorizace tedy je aby \( \{-x,x\}\not\equiv\{-y,y\} \pmod N\).

K systematickému nalezení takové dvojice slouží

• Kvadratické síto využívá síta k paralelnímu rozkládání čísel získaných pro malá k z \( (\lfloor\sqrt{N}\rfloor+k)^2-N \) a po nalezení dostatečného počtu rozkladů hledá součin, který by byl sudou mocninou. K tomu stačí sledovat součet parit mocnin jednotlivých prvočísel v prvočíselných rozkladech činitelů. Jedná se tedy o soustavu lineárních rovnic. Problém rozkladu jednoho velkého čísla na činitele tak byl převeden na problém rozkladu dostatečného počtu čísel z množiny menších čísel. Podstatné je, že se nesnažíme rozložit každé číslo z dané množiny, ale rozkládáme jenom ta čísla, kde je rozklad jednoduchý (K-hladká čísla neboli rozložitelná na prvočísla menší než K). Teorie čísel nám dává odhad počtu čísel, mezi nimiž dostatečný počet K-hladkých čísel najdeme. Množinu čísel, kterou bychom měli prosívat je možno zmenšit tím, když evidujeme i K,L skoro hladká čísla, rozložitelná na součin prvočísel menších než K a jednoho prvočísla mezi K a L. Pokud najdeme dva skorohladké rozklady obsahující stejné prvočíslo větší než K, pak jejich součin se od hladkého čísla liší druhou mocninou a může být tento pár zařazen do lineární soustavy pro hledání druhé mocniny součinu.
• Síto nad číselným tělesem je založeno na principech kvadratického síta, ale podařilo se zajistit, aby rozkládaná množina čísel byla tvořena menšími čísly. Cenou za to je počítání v komplikovanější aritmetice. Jedná se o v současnosti nejrychlejší známý algoritmus na faktorizaci součinu velkých prvočísel. Jeho složitost je \(O\left(e^{4\sqrt[3]{(b/9)\log^2 b}}\right),\) kde \(b\) je délka binárního zápisu rozkládaného čísla.

Použití pro malá čísla

Pomocí prvočíselného rozkladu lze snadno určit nejmenší společný násobek a největší společný dělitel dvou čísel:

Pro určení nejmenšího společného násobku se vezmou všechna prvočísla, která se vyskytují alespoň v jednom rozkladu a u každého z nich se použije největší z mocnin, ve které se vyskytuje. Výsledkem je prvočíselný rozklad nejmenšího společného násobku.

Pro určení největšího společného dělitele se vezmou všechna prvočísla, která se vyskytují v obou (popř. ve všech) prvočíselných rozkladech (pokud žádné takové není, je největší společný dělitel 1) a u každého se použije nejmenší z mocnin, ve které se vyskytuje. Výsledkem je prvočíselný rozklad největšího společného dělitele.

Tento postup je snadno pochopitelný a při znalosti prvočíselných rozkladů triviální. Zjištění neznámého prvočíselného rozkladu nějakého čísla je však algoritmicky náročnou úlohou, zatímco pro zjištění největšího společného dělitele a nejmenšího společného existuje jednoduchý Eukleidův algoritmus s lineární složitostí. Toto využití faktorizace je tak spíše školní ukázková úloha, v praxi pro větší čísla nepoužitelná. Naopak, zjišťování největšího společného dělitele pomocí Eukleidova algoritmu se používá v mnoha algoritmech pro faktorizaci velkých čísel.

Příklady

• \(1800 = 2^3 \cdot 3^2 \cdot 5^2\)
• \(2800 = 2^4 \cdot 5^2 \cdot 7^1\)
• nejmenší společný násobek: \(2^4 \cdot 3^2 \cdot 5^2 \cdot 7^1 = 25200\)
• největší společný dělitel: \(2^3 \cdot 5^2 = 200\)

Související články

• Prvočíslo
• Základní věta aritmetiky
• Dělitelnost
• Faktorizace

Externí odkazy