In der Zahlentheorie ist das allgemeine Sieb des numerischen Feldes (GNFS) der effizienteste klassische Algorithmus, der für ganze Factoring-Zahlen bekannt ist, die größer sind als 100 Ziffern. Heuristisch ist seine Kompliziertheit für das Factoring eine ganze Zahl n (aus dem Klotz n Bit bestehend), der Form

(in der L-Notation). Es ist eine Generalisation des speziellen Siebs des numerischen Feldes: Während die letzte Dose nur Faktor-Zahlen einer bestimmten speziellen Form, das allgemeine Sieb des numerischen Feldes Faktor jede Zahl abgesondert von Hauptmächten kann (die zum Faktor durch die Einnahme von Wurzeln trivial sind). Wenn der Begriff Sieb des numerischen Feldes (NFS) ohne Qualifikation gebraucht wird, bezieht es sich auf das allgemeine Sieb des numerischen Feldes.

Der Grundsatz des Siebs des numerischen Feldes (sowohl speziell als auch allgemein) kann als eine Verbesserung zum einfacheren vernünftigen Sieb oder quadratischen Sieb verstanden werden. Wenn man solche Algorithmen am Faktor eine Vielzahl n verwendet, ist es notwendig, nach glatten Zahlen (d. h. Zahlen mit kleinen Hauptfaktoren) des Auftrags n zu suchen. Die Größe dieser Werte ist in der Größe von n (sieh unten) Exponential-. Das allgemeine Sieb des numerischen Feldes schafft andererseits, nach glatten Zahlen zu suchen, die in der Größe von n Subexponential-sind. Da diese Zahlen kleiner sind, werden sie mit größerer Wahrscheinlichkeit glatt sein als die in vorherigen Algorithmen untersuchten Zahlen. Das ist der Schlüssel zur Leistungsfähigkeit des Siebs des numerischen Feldes. Um diese Beschleunigung zu erreichen, muss das Sieb des numerischen Feldes Berechnung und factorizations in numerischen Feldern durchführen. Das läuft auf viele ziemlich komplizierte Aspekte des Algorithmus verglichen mit dem einfacheren vernünftigen Sieb hinaus.

Bemerken Sie, dass Klotz n die Zahl von Bit in der binären Darstellung von n ist, der die Größe des Eingangs zum Algorithmus ist, so ist jedes Element des Auftrags n für einen unveränderlichen c im Klotz n Exponential-. Die Laufzeit des Siebs des numerischen Feldes ist Superpolynom, aber Subexponential-in der Größe des Eingangs.

Numerische Felder

Nehmen Sie an, dass f ein N-Grad-Polynom über Q (die rationalen Zahlen) ist, und r eine komplizierte Wurzel von f ist. Dann, f (r) = 0, der umgeordnet werden kann, um r als eine geradlinige Kombination von Mächten von r weniger auszudrücken, als n. Diese Gleichung kann verwendet werden, um weg irgendwelche Mächte von r  n zu reduzieren. Zum Beispiel, wenn f (x) = x + 1 und r die imaginäre Einheit i, dann ich + 1=0 oder ich = 1 ist. Das erlaubt uns, das komplizierte Produkt zu definieren:

: (a+bi) (c+di) = ac + (ad+bc) ich + (bd) ich = (ac  bd) + (ad+bc) ich.

Im Allgemeinen führt das direkt zur algebraischen Zahl Feld Q[r], das als der Satz von reellen Zahlen definiert werden kann, die gegeben sind durch:

:ar +... + ar + ar, wo a..., in Q.

Das Produkt irgendwelcher zwei solcher Werte kann durch die Einnahme des Produktes als Polynome, dann das Reduzieren irgendwelcher Mächte von r  n, wie beschrieben, oben, das Nachgeben eines Werts in derselben Form geschätzt werden. Um sicherzustellen, dass dieses Feld wirklich n-dimensional ist und zu einem noch kleineren Feld nicht zusammenbricht, ist es genügend, dass f ein nicht zu vereinfachendes Polynom ist. Ähnlich kann man den Ring des numerischen Feldes Z[r] als die Teilmenge von Q[r] wo a definieren... zu sein, der eingeschränkt ist, um ganze Zahlen zu sein.

Methode

Zwei Polynome f (x) und g (x) von kleinen Graden d und e werden gewählt, die Koeffizienten der ganzen Zahl haben, die über den rationals nicht zu vereinfachend sind, und die, wenn interpretiert, mod n, eine allgemeine Wurzel der ganzen Zahl M haben. Eine optimale Strategie, um diese Polynome zu wählen, ist nicht bekannt; eine einfache Methode ist, einen Grad d für ein Polynom aufzupicken, die Vergrößerung von n in der GrundM zu denken (Ziffern zwischen m und m erlaubend) für mehrer verschiedene M des Auftrags n, und f (x) als das Polynom mit den kleinsten Koeffizienten und g (x) als x  M aufzupicken.

Denken Sie, dass das numerische Feld Z[r] und Z[r] anruft, wo r und r Wurzeln der Polynome f und g sind. Da f des Grads d mit Koeffizienten der ganzen Zahl ist, wenn a und b ganze Zahlen sind, dann so wird b sein · f (a/b), den wir r nennen. Ähnlich s = b · g ist (a/b) eine ganze Zahl. Die Absicht ist, Werte der ganzen Zahl von a und b zu finden, die gleichzeitig r und hinsichtlich der gewählten Basis der Blüte glatten s machen. Wenn a und b klein sind, dann werden r und s auch über die Größe der M klein sein, und wir haben eine bessere Chance für sie, zur gleichen Zeit glatt zu sein. Die aktuelle am besten bekannte Annäherung für diese Suche ist siebendes Gitter; um annehmbare Erträge zu bekommen, ist es notwendig, eine große Faktor-Basis zu verwenden.

Genug solche Paare mit der Beseitigung von Gaussian habend, kann man veranlassen, dass Produkte von bestimmtem r und vom entsprechenden s Quadrate zur gleichen Zeit sind. Eine ein bisschen stärkere Bedingung ist erforderlich — dass sie Normen von Quadraten in unseren numerischen Feldern sind, aber dass Bedingung durch diese Methode auch erreicht werden kann. Jeder r ist eine Norm eines  rb und folglich, dass das Produkt der entsprechenden Faktoren ein  rb ist ein Quadrat in Z[r] mit einer "Quadratwurzel", die (als ein Produkt bekannter Faktoren in Z[r]) bestimmt werden kann — es wird normalerweise als eine vernunftwidrige algebraische Zahl vertreten. Ähnlich das Produkt der Faktoren ein  rb ist ein Quadrat in Z[r] mit einer "Quadratwurzel", die auch geschätzt werden kann. Es sollte bemerkt werden, dass der Gebrauch der Beseitigung von Gaussian die optimale Durchlaufzeit des Algorithmus nicht gibt. Statt dessen werden spärliche Matrixlösen-Algorithmen wie Block Lanczos oder Block Wiedemann verwendet.

Da M eine Wurzel sowohl von f als auch von g mod n ist, gibt es Homomorphismus von den Ringen Z[r] und Z[r] zum Ring Z/nZ (die ganzen Zahlen mod n), welche Karte r und r zur M und dieser Homomorphismus jede "Quadratwurzel" (normalerweise nicht vertreten als eine rationale Zahl) in seinen Vertreter der ganzen Zahl kartografisch darstellen werden. Jetzt kann das Produkt der Faktoren ein  Mb mod n als ein Quadrat auf zwei Weisen — ein für jeden Homomorphismus erhalten werden. So kann man zwei Nummern x und y, mit x  y teilbar durch n und wieder mit der Wahrscheinlichkeit mindestens eine Hälfte finden von uns bekommen einen Faktor von n, indem wir den größten allgemeinen Teiler von n und x  y finden.

Besserung polynomischer Wahl

Die Wahl des Polynoms kann die Zeit drastisch betreffen, um den Rest des Algorithmus zu vollenden. Die Methode, Polynome zu wählen, die auf der Vergrößerung von n in der GrundM gestützt sind, gezeigt ist oben in vielen praktischen Situationen suboptimal, zur Entwicklung von besseren Methoden führend.

Eine solche Methode wurde von Murphy und Brent angedeutet; sie führen eine zweiteilige Kerbe für Polynome ein, die auf der Anwesenheit von Wurzeln modulo kleine Blüte und auf dem durchschnittlichen Wert gestützt sind, dass das Polynom das siebende Gebiet übernimmt.

Die besten berichteten Ergebnisse wurden durch die Methode von Thorsten Kleinjung erreicht, der g (x) = Axt + b erlaubt, und über einen gelassenen von kleinen Hauptfaktoren sucht, die zu 1 modulo 2. und über Hauptkoeffizienten von f kongruent sind, die durch 60 teilbar sind.

Durchführungen

Einige Durchführungen konzentrieren sich auf eine bestimmte kleinere Klasse von Zahlen. Diese sind als spezielle Sieb-Techniken des numerischen Feldes, solcher, wie verwendet, im Projekt von Cunningham bekannt.

Ein Projekt genannt NFSNET ist von 2002 mindestens 2007 durchgegangen. Es hat verteilte Computerwissenschaft des Freiwilligen im Internet verwendet.

Paul Leyland des Vereinigten Königreichs und Richard Wackerbarth aus Texas wurden beteiligt.

Bis 2007 war die Goldwährungsdurchführung ein Gefolge der Software, die entwickelt und durch CWI in den Niederlanden verteilt ist, der nur laut einer relativ einschränkenden Lizenz verfügbar war. 2007 hat Jason Papadopoulos eine schnellere Durchführung der Endverarbeitung als ein Teil von msieve entwickelt, der öffentliches Gebiet ist. Beide Durchführungen zeigen die Fähigkeit, unter mehreren Knoten in einer Traube mit einer genug schnellen Verbindung verteilt zu werden.

Polynomische Auswahl wird normalerweise durch die GPL Software durchgeführt, die von Kleinjung, oder durch msieve und Gitter geschrieben ist, das durch die GPL Software siebt, die von Franke und Kleinjung geschrieben ist; diese werden in GGNFS verteilt.

• NFS@Home
• GGNFS
• pGNFS
• Faktor durch gnfs
• CADO-NFS
• msieve, der ausgezeichneten End-in einer Prozession Gcode, eine gute Durchführung der polynomischen Auswahl enthält, die sehr gut für kleinere Zahlen und eine Durchführung des Liniensiebs ist.
• kmGNFS

Siehe auch

• Spezielles Sieb des numerischen Feldes
• Arjen K. Lenstra und H. W. Lenstra der Jüngere. (Hrsg.).. "Die Entwicklung des numerischen Feldes siebt". Vortrag-Zeichen in der Mathematik. (1993) 1554. Springer-Verlag.
• Richard Crandall und Carl Pomerance. Primzahlen: Eine Rechenbetonte Perspektive (2001). 2. Ausgabe, Springer. Internationale Standardbuchnummer 0-387-25282-7. Abschnitt 6.2: Sieb des Numerischen Feldes, Seiten 278-301.