Bachs algoritme - Bach's algorithm

Bach's algoritme is een probabilistisch polynomiaal tijdalgoritme voor het genereren van willekeurige getallen samen met hun factorisaties , genoemd naar zijn ontdekker, Eric Bach . Het is interessant omdat er geen algoritme bekend is dat getallen efficiënt factoren, dus de eenvoudige methode, namelijk het genereren van een willekeurig getal en het vervolgens ontbinden, is onpraktisch.

Het algoritme voert, in verwachting, O(log n) -primaliteitstesten uit .

Een eenvoudiger, maar minder efficiënt algoritme (het uitvoeren van, in verwachting, priemtesten), is te danken aan Adam Kalai . ${\displaystyle O(\log ^{2}n)}$

Overzicht

Het algoritme van Bach produceert een willekeurig willekeurig getal in het bereik (voor een gegeven invoer ), samen met de factorisatie. Het doet dit door een priemgetal en een exponent te kiezen zodat , volgens een bepaalde verdeling. Het algoritme genereert vervolgens recursief een getal in het bereik , waarbij , samen met de factorisatie van . Het stelt dan en voegt toe aan de factorisatie van om de factorisatie van te produceren . Dit geeft met logaritmische verdeling over het gewenste bereik; Een afwijzingssteekproef wordt vervolgens gebruikt om een ​​uniforme verdeling te krijgen. ${\displaystyle x}$${\displaystyle N/2<x\leq N}$${\displaystyle N}$ ${\displaystyle p}$${\displaystyle een}$${\displaystyle p^{a}\leq N}$${\displaystyle y}$${\displaystyle M/2<y\leq M}$${\displaystyle M=N/p^{a}}$${\displaystyle y}$${\displaystyle x=p^{a}y}$${\displaystyle p^{a}}$${\displaystyle y}$${\displaystyle x}$${\displaystyle x}$

Referenties

Verder lezen

• Bach, Erik . Analytische methoden in de analyse en het ontwerp van getaltheoretische algoritmen , MIT Press, 1984. Hoofdstuk 2, "Generation of Random Factorizations", waarvan een deel hier online beschikbaar is .

Dit artikel over algoritmen of datastructuren is een stomp . Je kunt Wikipedia helpen door het uit te breiden .

• v
• t
• e