Bachsův algoritmus - Bachs algorithm - Wikipedia

Bachův algoritmus^[1] je pravděpodobnostní polynomiální čas algoritmus pro generování náhodných čísel spolu s jejich faktorizace, pojmenoval podle jeho objevitele, Eric Bach. Je zajímavé, protože není znám žádný algoritmus, který by účinně faktoroval čísla, takže přímočará metoda, jmenovitě generování náhodného čísla a jeho faktorování, je nepraktická.

Algoritmus provádí v očekávání O (log n) testy primality.

Jednodušší, ale méně efektivní algoritmus (provedení, v očekávání, ${ displaystyle O ( log ^ {2} n)}$ testy primality), je způsobeno Adam Kalai.^[2]

Přehled

Bachův algoritmus vytváří číslo ${ displaystyle x}$ rovnoměrně náhodně v rozsahu ${ displaystyle N / 2$ (pro daný vstup ${ displaystyle N}$), spolu s jeho faktorizací. Dělá to výběrem a prvočíslo ${ displaystyle p}$ a exponent ${ displaystyle a}$ takhle ${ displaystyle p ^ {a} leq N}$, podle určité distribuce. Algoritmus poté rekurzivně vygeneruje číslo ${ displaystyle y}$ v dosahu ${ displaystyle M / 2$, kde ${ displaystyle M = N / p ^ {a}}$, spolu s faktorizací ${ displaystyle y}$. Pak se nastaví ${ displaystyle x = p ^ {a} y}$a připojí se ${ displaystyle p ^ {a}}$ na faktorizaci ${ displaystyle y}$ vyrobit faktorizaci ${ displaystyle x}$. To dává ${ displaystyle x}$ s logaritmickou distribucí v požadovaném rozsahu; odmítnutí vzorkování se pak používá k získání rovnoměrného rozdělení.

Reference

Další čtení

• Bach, Eric. Analytické metody v analýze a návrhu numericko-teoretických algoritmů„MIT Press, 1984. Kapitola 2,„ Generování náhodných faktorizací “, jejíž část je k dispozici online tady.

Tento algoritmy nebo datové struktury související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.