WikiDer > Faktorisierungsmethode von Dixonon

In dem Zahlentheorie, eine Unterregion der Mathematik, wird der Faktorisierungsmethode von Dixonon (ebenfalls Dixons Algorithmus bezeichnet) allgemein verwendet für die Faktorisierung von positiv ganze Zahlen im Primzahlen; es ist eine Methode für die Faktorisierung von ganzen Zahlen. Es Algorithmus wurde 1981 von John Dixon, a Mathematiker des Carleton-Universität.

Die Grundidee

Dixons Methode zur Faktorisierung der ganzen Zahl gehele ${Displaystil N}$ basiert auf der Prämisse von Faktorisierungsmethode von Fermat indem du nach zwei suchst Quadrate Das modular${Displaystil N}$ gleichwertig sein. Die Faktorisierungsmethode von Fermat findet solche Quadrate, indem sie systematisch alle Möglichkeiten überprüft. Dies nimmt in der Regel viel Rechenzeit in Anspruch.

Daher ersetzt Dixon in seiner Methode die Bedingung „ist das Quadrat einer ganzen Zahl“ durch die viel schwächere Bedingung „hat nur kleine Primfaktoren“.

Der Algorithmus findet nun Quadrate ${displaystyle z_{i}^{2}equiv p_{1}^{m_{1}}cdot ldots cdot p_{n}^{m_{n}}{pmod {N}}}$ das modulo ${Displaystil N}$ sei das Produkt von Potenzen einer festen Anzahl kleiner Primzahlen ${displaystyle p_{1},ldots ,p_{n}}$ und findet das Produkt einer Anzahl solcher Quadrate, in denen alle Potenzen der Primzahlen gerade sind:

${displaystyle z_{1}^{2}z_{2}^{2}ldots z_{r}^{2}equiv p_{1}^{2M_{1}}cdot ldots cdot p_{n}^{2M_{ n}}{pmod {N}}}$

Dann ist:

${displaystyle x^{2}equiv z_{1}^{2}z_{2}^{2}ldots z_{r}^{2}equiv left(p_{1}^{M_{1}}cdot ldots cdot p_{n}^{M_{n}}Nacht)^{2}Äquiv y^{2}{pmod {N}}}$

und damit ist

${Anzeigestil x^{2}-y^{2}=(x y)(x-y)}$ ein Vielfaches von ${Displaystil N}$.

Algorithmus

Wählen Sie eine Obergrenze ${Anzeigestil B}$ für die zu verwendenden Primzahlen ${displaystyle p_{1}=2,p_{2}=3,ldots ,p_{k}leq B}$. Diese Menge von Primzahlen wird als Faktorbasis bezeichnet. Dann suche nach Zahlen ${Anzeigestil (z_{i})}$ im Bereich ${displaystyle lceil {sqrt {N}}ceil leq z_{i}leq N}$ deren Quadrate modulo . sind ${Displaystil N}$ B-rutschig sind, haben also nur Primfaktoren aus der Faktorbasis.

${displaystyle z_{i}^{2}=prod_{j=1}^{k}p_{j}^{m_{ij}}{pmod {N}}}$.

Dann aus den Zahlen ${Anzeigestil (z_{i})}$ eine Auswahl getroffen, deren Produkt nur gerade Potenzen der Primzahlen enthält. Dies kann mit Methoden aus der Lineare Algebra.

Sie nämlich. ${Anzeigestil M=(m_{ij})}$ die Matrix mit den Potenzen, dann ein Vektor ${Anzeigestil c}$ wollte wofür ${displaystyle Mcequiv 0{pmod {2}}}$. Der Vektor ${Anzeigestil c}$ gibt an, welche der ${Anzeigestil (z_{i})}$ gehören zur gewünschten Auswahl.

wenn ${Displaystyle-Operatorname {ggd} (x-y,N)}$ kein echter Teiler von ${Displaystil N}$ Erträge ist anscheinend ${displaystyle xequiv pm y{pmod {N}})}$, und sollte man eine andere Auswahl oder eine andere ausprobieren ${Anzeigestil (z_{i})}$ ermittelt, ggf. mit neuer Faktorbasis.

Beispiele

Beispiel 1

Um die Zahl 65621 zu faktorisieren, nehmen Sie {2,3,5,7} als Faktorbasis. Es gilt: ${displaystyle {sqrt {65621}}>256}$. Die erste Zahl, deren quadrierter Modulo 65621 nur Faktoren aus der Faktorbasis hat, ist 261:

${displaystyle 261^{2}mod 65621=2500=2^{2}cdot 5^{4}}$

Da die Exponenten der Primzahlen beide gerade sind, kann der folgende Schritt sofort durchgeführt werden:

${displaystyle (261-2cdot 5^{2})(261 2cdot 5^{2})=211 imes 311mod 65621=0}$

So

${displaystyle 65621=211 imes 311}$

Beispiel 2

Um 94563 zu faktorisieren, nehmen Sie die Faktorbasis {2,3,5,7,11,13}.

${displaystyle 821^{2}mod 94563=12100=2^{2}cdot 5^{2}cdot 11^{2}}$

Es gilt also:

${displaystyle (821-2 mal 5 mal 11)(821 2 mal 5 mal 11)=711 mal 931{pmod {94563}}=0}$

und

${displaystyle 711 imes 931=94563 imes 7}$

Es ist leicht zu erkennen, dass 711 durch 9 und 931 durch 7 teilbar ist, so dass

${displaystyle 3^{2} imes 79 imes 133=94563}$

Obwohl es nicht schwer ist, das zu sehen

${displaystyle 133=7 imes 19}$

kann auch mit dem Algorithmus bestimmt werden.

${displaystyle 13^{2}mod 133=36=2^{2}imes 3^{2}}$

${Displaystil (13-2 Monate 3)(13 2 Monate 3)=7 Monate 19=133}$

Das Endergebnis folgt:

${displaystyle 94563=3^{2} imes 7 imes 19 imes 79}$

quadratisches Sieb

Das quadratisches Sieb ist eine Optimierung des Dixon-Verfahrens. Das macht passende Werte für ${Anzeigestil x}$ in der Nähe von ${displaystyle {sqrt {N}}}$ so gewählt, dass ${displaystyle x^{2}!!!{pmod {N}}}$ klein ist und die Chance, eine glatte Zahl zu finden, stark erhöht ist.