Bachs algoritm

Bachs algoritm är en probabilistisk polynomtidsalgoritm för att generera slumptal tillsammans med deras faktoriseringar , uppkallad efter dess upptäckare, Eric Bach . Det är av intresse eftersom ingen algoritm är känd som effektivt faktoriserar tal, så den enkla metoden, nämligen att generera ett slumptal och sedan faktorisera det, är opraktisk.

Algoritmen utför, i förväntan, O(log n) primatitetstester .

En enklare, men mindre effektiv algoritm (som i förväntan utför $O(\log ^{2}n)$ primatitetstester), beror på Adam Kalai .

Översikt

Bachs algoritm producerar ett nummer $x$ likformigt slumpmässigt i intervallet $N/2<x\leq N$ (för en given ingång ${\displaystyle N} )$ , längs med dess faktorisering. Den gör detta genom att välja ett primtal $p$ och en exponent $a$ så att $p^{a}\leq N$ , enligt en viss fördelning. Algoritmen genererar sedan rekursivt ett tal $y$ i området $M/2<y\leq M$ , där $M=N/ p^{a}$ , tillsammans med faktoriseringen av $y$ . Den sätter sedan $x=p^{a}y$ och lägger till $p^{a}$ till faktoriseringen av $y$ för att producera faktoriseringen av $x$ . Detta ger $x$ med logaritmisk fördelning över det önskade området; avslagsprovtagning används sedan för att få en enhetlig fördelning.

Vidare läsning

• Bach, Eric . Analytic methods in the Analysis and Design of Number-Theoretic Algorithms , MIT Press, 1984. Kapitel 2, "Generation of Random Factorizations", varav en del är tillgänglig online här .