Prvočíselný rozklad

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

Nechť je  x \,\! přirozené číslo větší než 1. Za jeho prvočíselný rozklad označíme každý zápis
p_1^{m_1} \cdot p_2^{m_2} \cdot p_3^{m_3} \cdot \ldots \cdot p_n^{m_n} \,\!
který splňuje následující podmínky:

  1. p_1^{m_1} \cdot p_2^{m_2} \cdot \ldots \cdot 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[editovat | editovat zdroj]

Tato poměrně hrozivě vypadající definice má jednoduchý význam, jak je vidět z následujících příkladů prvočíselných rozkladů:

  •  2 = 2^1 \,\!
  •  3 = 3^1 \,\!
  •  4 = 2^2 \,\!
  •  5 = 5^1 \,\!
  •  6 = 2^1 \cdot 3^1 \,\!
  •  7 = 7^1 \,\!
  •  8 = 2^3 \,\!
  •  9 = 3^2 \,\!
  •  10 = 2^1 \cdot 5^1 \,\!
  •  11 = 11^1 \,\!
  •  12 = 2^2 \cdot 3^1 \,\!
  •  13 = 13^1 \,\!
  •  14 = 2^1 \cdot 7^1 \,\!
  •  15 = 3^1 \cdot 5^1 \,\!
  •  \ldots \,\!
  •  1800 = 2^3 \cdot 3^2 \cdot 5^2 \,\!
  •  \ldots \,\!
  •  9699690 = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19

Příklad implementace pro malá čísla[editovat | editovat zdroj]

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.

Základní věta aritmetiky[editovat | editovat zdroj]

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 náhodou nelze jedno číslo rozložit na prvočísla dvěma způsoby).

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

Použití pro malá čísla[editovat | editovat zdroj]

Pomocí prvočíselného rozkladu lze velice 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 vezmu všechna prvočísla, která se vyskytují v rozkladu prvního nebo druhého čísla a u každého z nich použiji maximální mocninu, ve které se vyskytuje. Získávám tím prvočíselný rozklad nejmenšího společného násobku.

Pro určení největšího společného dělitele vezmu všechna prvočísla, která se vyskytují v obou prvočíselných rozkladech (pokud žádné takové není, je největší společný dělitel 1) a u každého použiji minimální mocninu, ve které se vyskytuje. Získávám tím prvočíselný rozklad největšího společného dělitele.

Pro čísla, jejichž zápis vyžaduje desítky číslic je výpočet největšího společného dělitele popsaným způsobem časově nerealizovatelný, zato Euklidův algoritmus s velikostí čísel problémy nemá. Naopak, Euklidův algoritmus je používán snad ve všech netriviálních algoritmech, pomocí nichž se snažíme velká čísla faktorizovat.

Příklad[editovat | editovat zdroj]

  •  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 \,\!

Metody faktorizace použitelné pro větší čísla[editovat | editovat zdroj]

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ů[editovat | editovat zdroj]

  • 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 x0=2, y0=2 posloupnosti xi+1=f(xi), yi+1=f(f(yi)). Je-li NSD(xi-yi,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(aM-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 ak(D-1)-1 je dělitelné D. Pokud D-1 dělí M, bude tedy aM-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[editovat | editovat zdroj]

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  (\lceil\sqrt{N}\rceil+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.

Související články[editovat | editovat zdroj]