Diskussion:Quadratisches Sieb

Zumindest was in der alten Version steht und jetzt wieder hergestellt wurde, hat so in einer Enzyklopädie bestimmt nichts verloren. Was das "Quadratische Sieb" wirklich ist, weiss offenbar niemand. Ich konnte trotz intensiver Beschäftigung mit der Fragestellung keine Fachliteratur dazu finden. Dies gilt zumindest sofern man das zitierte Werk "A Tale of Two Sieves", zu deutsch heißt dies etwa "Die Fabel der zwei Siebe", nicht als Fachliteratur ansieht. Die äußere Form, z.B. der Titel und der Verweis auf den Lehrer des Herrn Pommerance, Herrn Erdös, erwecken zumindest nicht diesen Eindruck. Über die Herren Erdös und Pommerance habe ich zwar viele, jedoch keine seriös wirkenden Quellen gefunden. Falls tatsächlich bereits 1981 durch einen Herrn Pommerance ein Verfahren zur Faktorisierung einer 129-stelligen Zahl oder auch nur einer 110-stelligen ausgearbeitet wurde, ist kaum zu verstehen, dass erst mehr als ein Jahrzehnt später 100-stellige Zahlen tatsächlich faktorisiert wurden und wieso diese Arbeiten erst 1996 veröffentlicht wurden. 1981 wäre es zweifellos eine Sensation gewesen eine 100-stellige Zahl zu faktorisieren, da zu dieser Zeit Millionen und mehr Jahre dazu veranschlagt wurden.

Potential des Verfahrens

Trotzdem scheint das in der "Fabel" beschriebene Verfahren von Kraichik im Prinzip tatsächlich geeignet 100-stellige oder noch größere Zahlen zu faktorisieren. Es gibt sicher viele mehr oder minder nahe liegende Ideen, um das Verfahren noch erheblich zu beschleunigen. Einige davon hatte ich in einer revertierten Fassung dieses Artikels auch benannt. Fakt ist zumindest, dass heute bereits eine 200-stellige Zahl faktorisiert wurde. Sofern man den Angaben glauben kann, war der Rechaufwand dazu im Vergleich zur Rechenleistung von modernen Hochleistungsrechnern eher gering. Ferner sind heute kaum noch aktuelle Quellen zu finden, die RSA mit einer bestimmten Schlüssellänge als wirklich längerfristig sicher einstufen. Sogar von der Firma RSA Security, die das RSA-Verfahren patentiert hatte, findet man keine derartigen Aussagen mehr. (nicht signierter Beitrag von Fsswsb (Diskussion | Beiträge) 12:22, 6. Apr 2006)

Worum geht es eigentlich

Was das Qudratische Siebe ist, das ist im Artikel sehr wohl erklärt, ganz einfach einer der schnellsten Faktorisierungsalgorithmen.

Das ist aber eine sehr wage Erklärung und beantwortet nicht die relevante Frage bis zu welcher Schranke Zahlen mit dem Verfahren faktorisiert werden können. Hier gibt es widersprüchliche Angaben, weil einmal 110 Stellen und einmal 129 Stellen angegeben sind. Falls eine exponentielle Abhängigkeit von der Stellenzahl vorliegt, wie dies wird behauptet wird, sollte dies durchaus einen erheblichen Unterschied machen. In keinen Fall sollte die Faktorisierung einer 200-stelligen Zahl möglich sein, sofern die Abschätzungen über das Laufzeitverhalten nicht völlig falsch sind.

Die Frage bis zu welcher Grenze das Verfahren genau geht ist in etwa vergleichbar mit der, bis zu welcher Größe kann ich Zahlen mit der Hand multilplizieren obwohl hier der Aufwand viel langsamer ansteigt (ld(n)^2). Theoretisch beliebig große, aber irgendwann wird es mühsam. Für das quadratische Sieb gibt es folgende Komplexitätsabschätzung: $\exp {\left((1+o(1)){\sqrt {\ln {(n)}\cdot \ln {(\ln {n})}}}\right)}$ die Laufzeit wächst also subexponentiell, d.h. dass der Aufwand ab einer gewissen Grenze erheblich ansteigt, aber nicht, dass es gleich unmöglich wird.

Klar, geht es um die Frage bis zu welcher Grenze Zahlen faktorisiert werden können und damit der private Schlüssel beim RSA-Verfahren aus dem öffentlichen praktisch berechenbar ist. Genau dies und nichts anderes ist die praktische Relevanz der Faktorisierung großer Zahlen. Einen anderen nachvollziehbaren Grund sich mit der Faktorisierung großer Zahlen zu befassen, kann ich nicht erkennen.

Welche Zahlen damit faktorisiert werden können hängt von der Rechenleistung ab die man aufwendet. Ab ca. 120 Stellen ist das NFS oder GNFS einfach schneller, da es in

$O\left(\exp \left(\left({\begin{matrix}{\frac {64}{9}}\end{matrix}}\log n\right)^{1 \over 3}(\log \log n)^{2 \over 3}\right)\right)$

läuft. Wenn wir die Faktoren des Exponenten betrachten, sehen wir das das quadratische Sieb vom Faktor log (n) die 2. Wurzel zieht, während das GNFS nur die 3 Wurzel benötigt. Asymptotisch überdeckt dieser Vorteil den konstanten Faktor 64/9 sowie den anderen Exponenten an log log (n). D.h. ab einem gewissen Punkt ist das GNFS schneller. dieser liegt halt bei ca. 120 Stellen. Man könnte (mit stendig steigender Rechenleistung) auch eine 130 stellige Zahl mit dem QS zerlegen. Nur könnte man in der gleichen Zeit mit dem GNFS eine noch größere Zahl zerlegen. Daher wendet man zum Zerlegen von solch großen Zahlen das GNFS, da es darum geht möglichst große Zahlen zu zerlegen. Es steht jedem frei das QS so zu verbessern, dass es eine bessere Laufzeit als das GNFS bekommt. Die Abschätzungen sind korrekt. Allerdings beruhen sie auf Annahmen über die Eigenschaften von Zahlen, die nicht bewiesen sind. Es könnte durchaus sein dass die Laufzeit bei gewissen Zahlen nicht stimmen (war aber noch nie der Fall)-- Thilo Harich

Abschätzung der Laufzeit fragwürdig

Falls die Zahl der erforderlichen Rechenoperation exponentiell von der Schlüssellänge abhängt, kann eine Entschlüsselung durch die Verdopplung der Schlüssellänge faktisch ausgeschlossen werden.

Beispiel DES: Die Schlüssellänge lag ursprünglich bei 56 Bit, so dass die Entschlüsselung

$2^{56}=72.057.594.037.927.936$

Operationen erfordert. In den 90-er Jahren erreichten übliche Computer eine Rechenleistung mit der eine Entschlüsselung nicht mehr vollständig auszuschließen war. Die Schlüssellänge wurde daher auf 112 Bit verlängert. Damit ist die Zahl der Rechnenoperation für einen Brute Force-Angriff nicht etwa verdoppelt, verdreifacht oder vervierfacht worden sondern um den riesigen Faktor 72.057.594.037.927.936 erhöht worden.

Überträgt man diese Überlegungen auf die Faktorisierung, wird klar das es zunächst alles andere als selbstverständlich ist, dass eine Faktorisierung durch steigende Rechnerleistung irgendwann auch bei doppelter Stellenanzahl bzw. Schlüssellänge möglich wird. Bei exponentiellem Anstieg wäre dies undenkbar. Die Schlüssellänge L ist hier der Logarithmus ln(n). Nach der oben Angegebenen Formel nimmt der Exponent, das Argument der Exponentialfunktion, zwar nicht direkt proportional mit der Schlüssellänge sondern "nur" mit der Wurzel aus $L\cdot ln(L)$. Die Zunahme im Argument bedeutet aber weiterhin eine Zunahme um einen Faktor und nicht um eine additive Konstante. Auch in diesem Fall würde eine Verdopplung der Schlüssellänge, die Zunahme der erforderlichen Rechenleistung um einen riesigen Faktor bedeuten.

Wie du schon bemerkt hast wurden damit schon 129 stellige Zahlen faktorisiert. Daraus kann man aber schließen, dass etwas 300 stellige Zahlen mit derzeitiger Hardware unmöglich erscheinen. Man sollte aber nicht vergessen, dass das Mooresche Gesetz weiterhin gilt, obwohl in letzter Zeit die Komplexität moderner Chips nur mehr schwer handhabbar wird und man dadurch vermehrt auf Parallelisierung setzt. Der Siebschritt zB ist aber ohne weiteren Aufwand parallelisierbar. --Calisti 23:39, 6. Apr 2006 (CEST)

Trotz Mooreschem Gesetz und Parallelisierung sollte nach der Formel für das asymtotische Verhalten bereits die Faktorisierung einer 200-stelligen Zahl zumindest mit dem "Quadratischen Sieb" undenkbar sein, falls in den 80-er Jahren die Faktorisierung 100-stelliger Zahlen noch nicht möglich war. Eine 200-stellige Zahl wurde jedoch nachweislich faktorisiert. Es gibt dafür im Prinzip nur zwei denkbare Erklärungen.

• Die Abschätzung für das asymtotische Laufzeitverhalten ist falsch.

• Es gibt eine prinzipiell wesentlich effizienteres Verfahren als das Quadratische Sieb (nicht nur ein Faktor 10 oder so etwas lächerliches)

Hast du die Laufteitabschätzung verstanden? Die Laufzeit ist nicht exponentiell!!!!!!!

Warum wirfst du immer Fragen und Vermutungen mit möglichen Schlussfolgerunegn auf, anstatt mal versuchen die Fakten/Algorithmen/Abschätzungen zu verstehen???? Versuche doch bitte das Verfahren zu verstehen, anstatt hier alles zu blockieren. Die zweite Vermutung trifft zu Stichwort "GNFS" (etwa englisches Wikipedia)-- Thilo Harich

Ich persönlich kann nicht entscheiden welche der beiden Möglichkeiten zutrifft, tendiere aber zu der Vermutung, dass beide zutreffen.

Was soll das? Du schreibst hier immer irgendwelche Behauptungen und vergleichst Äpfeln mit Birnen. Die Laufzeit des Quadratischen Siebes ist oft in der Literatur angeführt und auch unumstritten. Nur du äußerest andauernd Zweifel darüber. Du solltest die angegeben Quellen vielleicht auch mal lesen bevor du was schreibst. Zu DES hier muss man auch sagen dass Spezialhardware verwendet wurde und keine einfachen PCs (auch ein Großrechner würde da dagegen blass ausschauen). Übrigens solche überlegungen gibts auch für den Siebschritt (TWINKLE, TWIRL). Und da die Rechenleistung laut Moore exponentiell wächst ist es nicht verwunderlich dass Schlüssellängen die in den 70ern als vernünftig angesehen wurden das heute nicht mehr sind, darum gibt es auch zB 3DES. Man muss eben die Schlüssellängen adaptierten und das ist von der Hardware eigentlich kein Problem. Es ist eben genau der Unterschied, dass man Zahlen leicht multiplizieren aber nur schwer faktorisieren kann. Wie oft noch, für so große Zahlen verwendet man das Zahlkörpersieb und wenn das so einfach gehen würde wäre die ganze RSA Challenge schon vorbei. Soweit ich weiß dauerte das Sieben bei RSA200 aber auch über ein Jahr, da wird der Faktor zehn schon bedeutend.--Calisti 19:44, 7. Apr 2006 (CEST)

Die Frage, ob das Verfahren das zweit, dritt oder viert schnellste ist, spielt dagegen eigentlich keine Rolle. Interessant ist lediglich, ob mit anderen Verfahren noch erheblich größere Zahlen faktorisiert werden können. Dazu gibt es keine klaren Aussagen.

Doch, wenn man sich beim den RSA Contest ansieht sind die größten Zahlen mit dem Zahlkörpersieb faktorisiert worden und wie man an dessen Komplexitätsabschätzung $\exp \left((c+o(1))(\ln {n})^{1/3}(\ln {(\ln {n}}))^{2/3}\right)$ sieht ist es besser als das Quadratische Sieb. Jedoch ist es für Zahlen kleiner als etwa 110 Stellen langsamer als das Quadratische Sieb darüber ist es schneller und vorallem wächst der Aufwand nich so schnell. Erheblich größere Zahlen können aber auch damit sicher nicht faktorisiert werden, z.B. 1000 stellige.--Calisti 23:39, 6. Apr 2006 (CEST)

Selbst 1000-stellige Zahlen können in einigen Spezialfällen schon mit dem ursprünglichen Verfahren von Fermat leicht faktorisiert werden. Die Abschätzungen für das asymtotische Verhalten gelten, wenn überhaupt, für den Wost Case aus Sicht des Code-Crackers. Allerdings habe ich nirgends eine nachvollziehbare Erklärung für diese Formeln gefunden. Ich bleibe daher skeptisch.

Name des Verfahrens

Diese Frage nicht wirklich von größerem Interesse.

Das ist aber schnell erklärt, da nämlich Kongruenzen der Form $x^{2}\equiv y{\pmod {n}}$ betrachtet werden und diese werden Quadratische Kongruenzen genannt. Weiters verwendete Pomerance erstmals Siebverfahren um nach glatten Zahlen zu sieben, die über der Faktorbasis zerfallen, und damit eine Kongruenz der Form $u^{2}\equiv v^{2}{\pmod {n}}$ zu erzeugen.

Ok, das Verfahren hat offensichtlich etwas mit Qudraten zu tun und es werden Zahlen selektiert bzw. gesiebt, die glatt also leicht zu faktorisieren sind. Von diesen werden wiederum einige ausgewählt, die als Produkt eine Quadratzahl ergeben. Dies alles trifft allerdings praktisch auf alle Verfahren zur Faktorisierung von über 100-stelligen Zahlen und auch schon auf Kraichiks Verfahren zu. Was wirklich das besondere am Quadratisches Sieb ist und was es von anderen Verfahren unterscheidet, kann ich nicht ganz nachvollziehen.

Eben nicht, weil bei Kraichik nicht gesiebt wird! --Calisti 23:39, 6. Apr 2006 (CEST)

Darum Quadratisches Sieb. Die Methode solche Kongruenzen zu kombinieren geht bereits auf Kraitchik zurück aber Pommerance war der erste der bei der Suche nach glatten Zahlen Siebverfahren einsetzte. Ob der Algorthmus allerdings 1981 oder 1985 entstanden ist weiß ich auch nicht genau. Fest steht dass es 1981 eine Veröffentlichung über Dixons Random Square Verfahren (Algorithmus ohne Siebverfahren) gibt.

J.D. Dixon. Asymptotically fast factorization of integers. Math. Comp. 36, pages 255-260, 1981

So weit ich die "Fabel" verstanden habe, hat Pommerance eine Verbesserung vorgeschlagen, wie die Teilbarkeit effizient ohne die Quadratische Kongruenzen überhaupt berechnen zu müssen, geprüft werden kann. Damit können die (wahrscheinlich) nicht glatten Zahlen ausgesiebt werden, ohne eine Probedivision durchführen zu müssen.

Das ist ja gerade der Trick am Sieb. Man findet damit Zahlen die sehr wahrscheinlich bis zu einer gewissen Schranke glatt sind und faktorisiert diese erst DANACH. Darum erspart man sich die Probedivisionen bei allen nicht glatten Zahlen.--Calisti 23:39, 6. Apr 2006 (CEST)

und 1985 eine von Pomerance über das Quadratische Sieb

C. Pomerance. The quadratic sieve factorization algorithm. In Adavances in Cryptology - EUROCRYPT 84, volume 209 of Lecture Notes in Mathematics, pages 169-182, 1985

Es gibt also Fachliteratur dazu und das ist nur ein sehr kleiner Auszug. Interssant zu lesen ist in diesem Zusammenhang auch diese Diplomarbeit (hier finden sich auch noch viele andere Referenzen) Das Number Field Sieve. Entwicklung, Varianten und Erfolge

Wenn du schon selbst schreibst du weißt nicht genau was das Quadratische Sieb ist, warum schreibst du dann irgendwelche Vermutungen in den Artikel? In eine Enzyklopädie gehören Fakten und keine Vermutugen.

Um zu erfahren, ob ich vielleicht etwas übersehen habe oder an meinen Überlegungen etwas falsch ist. Wenn es einer besser weiss, kann er mich ja korrigieren. Immhin gibt es ja jetzt ein paar Referenzen zu möglicherweise relevanter Fachliteratur.

Warum damals noch keine 100 Stelligen Zahlen damit faktorisiert wurden?

Hast du schon mal den Algorithmus implementiert? Dabei fällt auf, dass man für 100 stellige Zahlen sicher über 50MB Hauptspeicher braucht und das gabs 1985 IMHO noch nicht.

Um die RSA-Verschlüsselung durchzuführen müssen derartige Zahlen sogar mehrfach multipliziert bzw. quadriert werden. Dies war offenbar auch schon 1978 möglich. Zudem ist die Berechung beim Quadratischen Sieb nach der Idee von Pommerance überhaupt nicht erforderlich.

Multiplikation großer Zahlen ist auch eine ganz andere Baustelle und viel einfacher handzuhaben, siehe Komplexität Multiplikation und Faktorisierung.--Calisti 23:39, 6. Apr 2006 (CEST)

Zu den ganzen anderen Verbesserungsvorschlägen, die existieren bereits und sind eigentlich alle in dem Buch Prime Numbers, A Computational Perspective angeführt. Z.B. MPQS, large Prime Variante, spezielles Quadratisches Sieb.

Ich habe ja gar nicht behauptet, dass ich diese als erster vorgeschlagen habe. Es ist aber um so erstaulicher, dass die Faktorisierung noch bis in die letzten Jahre als unlösbares Problem dargestellt wurde.

Für große Zahlen ist es auch ein unlösbares Problem und man kann bei RSA problemlos so große Schlüssellängen wählen, außer vielleicht auf Smartcards, dass deren Faktorisierung ausgeschlossen werden kann. Das Problem ist eher das die Schüssellängen nicht gerne verändert werden weil es einfach Aufwand bedeutet. --Calisti 23:39, 6. Apr 2006 (CEST)

Und was das Faktorisieren von RSA-200 und ähnlich großer Zahlen anbelangt, wurde da IMHO auch das Zahlkörpersieb und nicht das Quadratische Sieb verwendet.

--Calisti 18:02, 6. Apr 2006 (CEST)

Wie schon gesagt. Nach den Laufzeitabschätzungen aus der Literatur sollte dies mit dem Quadratischen Sieb auch gar nicht möglich sein. Ich bin mir aber nicht sicher, ob diese wirklich stimmen. Aus meiner Sicht ist es nicht wirklich klar, was das Quadratische Sieb genau ist. Was jedoch das Zahlenkörpersieb ist, bleibt vollkommen im Dunkeln.

Paul Erdös. Die Notices of the AMS sind auch nicht gerade die Bäckerblume.--Gunther 12:29, 6. Apr 2006 (CEST)

Das Quadratische Sieb ist eines von mehreren Verfahren, die mit der Kongruenz x^2=y^2 arbeiten. Die Ideee ist tatsächlich alt, die Verfahren, eine solche Beziehung zu konstruieren sind sehr viel neuer. Von Fermat stammt die Idee x^2-y^2=n, von Kraitchik stammt x^2-y^2=0 mod n. Wikimath

Nein, das ist wohl nicht der entscheidende Punkt bei Kraitchik's Idee. Die Gleichung

$x^{2}\equiv y^{2}\mod n$

ist nichts weiter als eine andere Schreibweise für die Aussage

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle x^{2} = y^{2} + {k} \cdot {n}}

mit eine ganzen Zahl k. Fermats Betrachtung ist also ein Spezialfall mit k=1. Diese Ausage kann mittles der binomischen Formel auch in der Form

$(x-y)\cdot (x+y)=k\cdot n$

geschrieben werden. Der entscheidene Fortschritt bei Kraitchik liegt aber darin nicht einfach Zahlen x,y zu quadrieren, in der Hoffnung x,y mit der Eigenschaft zu finden, sondern die Primfaktorzerlegung der Quadratischen Reste

$qr=x^{2}\mod n$

zu verwenden, um eine Quadratzahl zu finden, die das Produkt der qr ist. Das entsprechende Produkt der x-Werte ist dann ebenfalls eine Quadratzahl, die sich nur um ein Vielfaches von n vom Produkt der qr unterscheidet. Franz Scheerer.

Um eine solche Kongruenz zu finden, gibt es folgende Verfahren: Dixon's Random square, die Kettenbruchmethode von Morrison und Brillhardt (1970), das Quadratische Sieb, das 1981 von Carl Pomerance vorgeschlagen wurde. Wikimath

Ich sehe bei all diesen Verfahren nicht wirklich einen entscheidenden Unterschied. Franz Scheerer.

Alle drei arbeiten ähnlich, unterscheiden sich allerdings in der Methode, wie die "glatten" Quadrate gefunden werden. Wikimath

Vor allem wohl darin wie die x-Werte bestimmt werden. Diese können jedoch weigehend zufällig gewählt werden. Daher sehe ich keinen wesentlicher Unterschied. Franz Scheerer.

Ausserdem gibt es noch das Zahlkörpersieb, das noch neuer ist und etwas anders arbeitet, aber auch eine derartige Kongruez konstruiert. Wikimath

Auch das Zahlenkörpersieb ist wohl auch nur eine eher unwesentliche Optimierung.Franz Scheerer.

Die alten Angaben waren korrekt.

Ich habe das Gefühl, dass "Fsswsb" die angegebenen Quellen (das Buch von Crandall und Pomerance und den Artikel von Pomerance) nicht besonders gut kennt, denn in seiner jetzigen Form beschreibt der Artikel nicht das quadratische Sieb. Wäre es so einfach, eine Zahl mit 200 Stellen in Primfaktoren zu zerlegen, müsste man sich wohl neue Verschlüsselungsalgorithmen suchen, weil RSA dann total unsicher wäre. Wikimath

Ich habe den Orginalartikel nicht erstellt und auch die Quellenangaben stammen nicht von mir. Das Buch kenne ich nicht. Meine wesentlichen Quellen sind der Orginalartikel, eigene Überlegungen und die Fabel über die beiden Siebe.

Eine 200 stellige Zahl, RSA-200, wurde definitiv bereits faktorisiert. Ich denke mit einem Verfahren, das sich von dem beschriebenen nur in Details unterscheidet. RSA lässt sich allerdings auch mit wesentlich größeren Zahlen mit über 10.000 Stellen berechnen. Allerdings kann dies wohl kaum noch auf einer Chipkarte implementiert werden. Eine wirklich langfristige hohe Sicherheit ist mit Public Key-Verfahren kaum zu erreichen. Falls die Verfahren jedoch nur genutzt werden eine Schlüssel auszutauschen und eine längerfristige Sicherheit nicht gefordert ist, ist dies kein wesentliches Problem. Franz Scheerer

Für eine Antwort wäre ich dankbar. --Wikimath 14:16, 28. Mär 2006 (CEST)

Du hast recht, die Verfahren unterscheiden sich tatsächlich nur in einem einzigen Detail, nämlich darin, wie die Quadrate gefunden werden, aus denen die Faktorisierung hervorgeht. Dieses Detail ist allerdings entscheidend für die Laufzeit und dafür, wie gross die Zahlen sind, die faktorisiert werden können. Für RSA-200 gilt: "sieving would have taken 55 years on a single 2.2 GHz Opteron CPU". In diesem Fall wurde das Zahlkörpersieb benutzt, das eine asymptotische Laufzeit von exp(1/3*lnN*lnlnN) hat. Das Qudratische Sieb wird mit exp(1/2*lnN*lnlnN) angegeben. Ab ca. 130 Stellen soll das Zahlkörpersieb schneller sein.

Bemerkung: Ich habe schon etliche ähnliche Abschätzungen für die asymptotische Laufzeit gefunden. Meist steht da allerdings noch eine Wurzel im Exponenten, was die Wert natürlich bei größerem N dramatisch verringert. Falls im Exponenten 1/3 statt 1/2 steht verringert dies den Wert des Ausdrucks um den Faktor exp(1/6*lnN*lnlnN). Für große N ist dies also ebenfalls ein dramatischer Unterschied. Allerdings habe ich noch keine nachvollziehbare Begründung für die Abschätzungen gesehen. Der Ausdruck exp(1/2*lnN) ist jedenfalls identisch mit der Wuzel aus N und gibt die Zahl der erforderlichen Probedivision (Worst Case) an. Daher erscheint dieser Wert nicht gerade auf ein extrem günstiges Verfahren hinzudeuten.

In diesen Artikel geht um das Quadratische Sieb. Dieses findet Zahlen, deren Quadrate glatt mit einem speziellem Siebverfahren (Name!), nicht die kleinen Primzahlen!. Und nur bei diesen Zahlen wird versucht, sie in Primfaktoren zu zerlegen, alles andere ist viel zu langsam. Die Wahrscheinlichkeit, dass eine 100-stellige Zahl in Primfaktoren zerfällt, die höchstens 10 Stellen haben liegt bei 10^-10. Also ist nur eine von 10 Milliarden Zahlen in diesem Bereich glatt. Hier findest Du eine Herleitung dieser Zahlen: http://www.math.leidenuniv.nl/~reinier/ant/sieving.pdf. Dieser Beitrag ist von Carl Pomerance, dem Verfasser der "Tale of two sieves", dem Erfinder dieses Verfahrens.

Der Originalartikel sah vor Mitte März ganz anders aus, er enthielt die Details, die den Algorithmus "Quadratisches Sieb" erst ausmachen. Falls Du der Meinung bist, das Faktorisieren solcher Zahlen sei einfach, könntest Du Dich am RSA-Wettbewerb beteiligen, die nächste Zahl RSA-704 (212 Stellen) bringt 30.000$ Preisgeld ! Ich denke, dass die Seite wieder die Details zum QS enthalten sollte und dafür die viel zu optimistische Herleitung der Häufigkeit glatter Zahlen gestrichen wird.

Der Originalartikel hat neben vielem Richtigen auch viel Falsches enthalten. Deshalb sollten wir versuchen, hier einen guten Stand zu erreichen, bei dem klar hervorgeht, wie das QS arbeitet, auch bei den für Dich völlig unwichtigen, für mich entscheidenden Details, die das QS aber erst ausmachen.

Gruss --Wikimath 15:59, 29. Mär 2006 (CEST)

Also ich bin durchaus der Meinung, daß das RSA-Verfahren wesentlich unsicherer ist, als es immer dargestellt wird. Seine größte Schwäche liegt in der, vermutlich notwendigen, Vorraussetzung einer Zahl n als Produkt zweier (teilerfremder) Primzahlen p und q.

Diese Bedingung bewirkt, das es für die meisten quadratischen Reste genau vier Zahlen gibt.

Beispiel: n=1763=41*43:

Ich greife mal eines von ungefähr 438 Vierergruppen raus: 446 = [47, 211, 1552, 1716]

Aus den in der Klammer befindlichen vier Zahlen kann man die Primteiler ermitteln: gcd((211-47),1763) = 41, gcd((211+47),1763) = 43, gcd((1552-47),1763) = 43, gcd((1552+47),1763) = 41, gcd((1716-1552),1763) = 41, gcd((1716+1552),1763) = 43.

Das funktioniert mit allen Vierergruppen gleichsam.

Wichtig ist, das man von einer Vierergruppe wenigstens drei Zahlen zusammenbekommt. Der Rest hängt vom Zufall ab. --84.177.157.4 20:06, 29. Mär 2006 (CEST)

Du hast recht: bei einer Zahl mit x Primfaktoren hat jeder quadratische Rest 2^x Wurzeln, bei einer Zahl n=p*q also 4. Die gehören jeweils paarweise zusammen 47 und -47=1716 mod 1763 211 und -211=1552 mod 1763. Die Kongruenz führt dann zu einer Lösung, wenn x nicht gleich y oder -y ist. Bei Deinem Beispiel gibt es zu 47 mit 211 oder 1552 eine Lösung, mit 1716 aber nicht. Hier liegt auch die Zufallskomponente, man weiss nämlich vorher nicht, ob man den guten oder dem schlechten Fall hat, erst nach dem ggT. Die Sicherheit von RSA beruht nur darauf, dass es eben sehr schwierig ist, bei grossen Zahlen solche Paare zu finden oder aber, was auf das gleiche rausläuft, Wurzeln modulo einer grossen Zahl zu ziehen. QS ist das zweitbeste Verfahren ein solches Paar zu finden, und ich denke, ein Artikel mit dieser Überschrift sollte genau dieses Verfahren erklären. Vielleicht sollte man sich hier mehr an den englischsprachigen Artikel halten. --Wikimath 14:52, 30. Mär 2006 (CEST)

So, ich habe deine Antwort verdaut! Eine Kleinigkeit hast Du übersehen: Um festzustellen, ob man ein Paar hat, muß man die größere Zahl nur von n abziehen. Also angenommen, ich habe 47 und 1716. Dann brauche ich nur von 1763 die 1716 abzuziehen, um zu wissen, das ich das "nutzlose" Gegenstück habe. Noch wichtiger: Ich brauche scho von vornherein den Bereich 1716 bis 1762 gar nicht erst zu berücksichtigen. --Arbol01 13:50, 31. Mär 2006 (CEST)

Nach der Kritik von Wikimath und dem Statement von Fsswsb: "Meine wesentlichen Quellen sind der Orginalartikel, eigene Überlegungen und die Fabel über die beiden Siebe", dass zeigt, dass die Aenderungen von Fsswb nicht ausreichend fundiert sind, habe ich die Aenderungen revertiert. Vielleicht sollte Fsswbwb ueberhaupt erstmal sagen, was er denn als Ziel einer Ueberarbeitung sieht. --DaTroll 14:19, 4. Apr 2006 (CEST)

Erklärung für Nicht-Mathematiker

Der Artikel in seiner jetzigen Form ist leider für eine Enzyklopädie völlig ungeeigent. Ohne mathematische Vorkenntnisse, ist er einfach nicht verdaulich.

Die Idee hinter dem Verfahren ist jedoch sehr einfach und mit wenigen Grundkenntnissen in Mathematik verständlich. Alle Verfahren zur Faktorisierung großer Zahlen basieren auf einer Idee, die schon im 17. Jahrhundert von Fermat benutzt wurde. Fermat versuchte Faktoren einer Zahl n zu finden, indem er diese Zahl als Differenz zweier Qudrate darstellte.

Als Beispiel betrachten wir die Zahl 161. Zunächst berechnen wir die Wurzel aus 161 und erhalten den Wert 12,7. Jetzt bilden wir für die kleinsten ganzen Zahlen größer als 12, die Differenz des Quadrats und 161. Ist das Ergebnis eine Quadratzahl, kann 161 als Differenz zweier Quadrate geschrieben werden.

• 13*13 - 161 = 8 = 2*2*2
• 14*14 - 161 = 35 = 7*5
• 15*15 - 161 = 64 = (2*2*2)*(2*2*2)

Bereits in dritten Versuch haben wir eine Differenz von Quadratzahlen gefunden, die 161 ergibt. 161 = 15*15 - 8*8 = (15-8)*(15+8) = 7 * 23. Damit haben wir die Primfaktorenzerlegung der Zahl 161 gefunden.

Das Produkt zweier Primzahlen größer als 2, wie sie bei RSA verwendet werden, kann immer als die Differenz zweier Zahlen im Quadrat, hier 15 und 8, geschrieben werden. Diese Zahlen sind die halbe Summe und die halbe Differenz der Zahlen p und q.

Optimierung für Fermat

Ist die zu faktorisierende Zahl das Produkt zweier ungerader Primzahlen p und q müssen, beginnend mit der kleinsten ganzen Zahl größer als die Wurzel, bis zur Zahl (p+q)/2 die Quadrate berechnet werden. Sind p und q annähernd gleich groß, dann sind p und q etwa gleich der Wurzel und das Ziel ist rasch erreicht. Der ungünstigste Fall ist eine extrem ungleiche Verteilung, die auftritt falls p oder q gleich 3 sind. In diesem Fall ist die Zahl der Versuche etwa n/6. In diesem Extremfall ist die Faktorisierung durch Probedivision viel schneller.

Wir machen die Annahme die größere Primzahl wäre Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle p = \left(1+\epsilon\right)\sqrt{n}} . Dann sind mit der Fermatschen Methode etwa Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle \frac{{\epsilon}^{2}}{2}\sqrt{n}} Berechnungen erforderlich.

Damit ist das Verfahren für 100-stellige und größere Zahlen jedoch in der Regel ungeeigent, da die Wurzel aus n dann bereits 50-Stellen aufweist. Wird p jedoch als etwa 50 stellige Primzahl und q als die nächst größere Primzahl gewählt, kann die Zerlegung auch mit dem einfachen Verfahren von Fermat gefunden werden.

Das Verfahren von Fermat ist jedoch immer dann effizient, wenn die zu faktorisierende Zahl n als das Produkt zweier ungerader Zahlen geschrieben werden kann, die sich nur um einen kleinen Bruchteil der Wurzel aus n unterscheiden. Wir nehmen n sei das Produkt zweier ungeraden oder zweier gerader Zahlen a und b. Dann kann n als

$\left({\frac {a+b}{2}}\right)^{2}-\left({\frac {a-b}{2}}\right)^{2}$

geschrieben werden. Dabei sind die Ausdrücke in den Klammern ganze Zahlen, wenn die Zahlen a und b beide ungerade oder auch beide gerade sind. Falls n das Produkt zweier großer Primzahlen ist, gibt es nur eine Zerlegung als Differenz von Quadratzahlen, die durch das Fermatsche Verfahren gefunden wird.

Die Unterscheidung zwischen ungeraden und geraden Zahlen kann vermieden werden, wenn statt dem Ausdruck

$Q(x)=x^{2}-n$

4*Q(x) darauf untersucht wird, ob es sich um eine Qudratzahl handelt. Diese Vorgehen kann auch so interpretiert werden, dass Teiler der Zahl 4*n mit dem Fermatschen Verfahren gesucht werden. Allgemein können Teiler von n auch gefunden werden, indem Teiler kleiner Vielfachen von n wie 3n, 5n, 15n, ..., etc gesucht werden.

Falls sich p und q um einen größeren Faktor unterscheiden, wird damit der Rechenaufwand sogar erheblich verringert. Dies kann wie folgt erklärt werden:

Das Fermatsche Verfahren ist dann schnell, falls es Faktoren a und b gibt, die annähernd gleich groß sind. Falls n das Produkt zweier großer Primzahlen ist, gibt es jedoch nur eine Zerlegung in Faktoren größer als eins. Falls n jedoch zuvor mit verschiedenen kleineren Primzahlen multipliziert wird, können die beiden Primfaktoren p und q mit diesen kleineren Faktoren derart zusammengefasst werden, dass sich annähernd gleich große Faktoren a und b ergeben. Das Verfahren von Fermat findet automatisch die Zerlegung in Faktoren a,b, mit der geringsten Differenz von a und b. Die größten gemeinsamen Teiler ggT(a,n) und ggT(b,n) liefern in diesem Fall die gesuchten Faktoren p und q.

Das Verfahren von Fermat lässt sich eventuell noch weiter verbessern, wenn man nicht abwartet bis das Ergebnis eine Quadratzahl ist, sondern versucht eine Qudratzahl aus den Nicht-Quadratzahlen auf der rechten Seite zu bilden. Hat man ein solches Produkt gefunden, kann man die entsprechenden Zahlen auch auf der linken Seite multiplizieren und hat damit zwei Quadratzahlen gefunden.

Hierfür kann die Primfaktorenzerlegung der Zahlen auf der rechten Seite genutzt werden. Damit lässt sich die Suche mit Standverfahren der linearen Algebra zurückführen. Auf diese Weise lassen sich Zahlen mit 100-Stellen und mehr faktorisieren.

Sicherheit von RSA

Effiziente Methoden zur Faktorsierung von 100-stelligen und größeren Zahlen haben praktisch nur diesen einen Hintergrund: RSA, ein kryptographisches Verfahren, das z.B. für die digitale Signatur eingesetzt wurde (und wird ?). Die Sicherheit dieses Verfahren beruht darauf, dass es praktisch unmöglich sein sollte, derartige Zahlen in Ihre Primfaktoren zu zerlegen. Diese Annahme ist jedoch zumindest für "nur" 200-stellige Zahlen offenkundig falsch.

Es ist nicht ganz eindeutig seit wann diese Tatsache allgemein bekannt war und welche Verfahren zur Faktorisierung dafür geeigent sind. Nach offizieller Darstellung ist das Quadratische Sieb nur für bis zu 129-stellige Zahlen geeignet. Nach meinen Überlegungen sollte es jedoch auch möglich sein größere Zahlen mit diesem Verfahren zu faktorisieren.

Extrem verwunderlich ist in diesem Zusammenhang, dass dieses Verfahren bereits 1981 entwickelt worden sein soll. Zu diesem Zeitpunkt galt die Faktorisierung einer 100-stelligen Zahl noch als faktisch ausgeschlossen. Erst etwa ein Jahrzehnt später wurde bekannt, dass 100-stellige Zahlen doch faktorisiert werden können. Dannach wurden 150-stellige Zahlen als nicht faktorisierbar erklärt, bis das Gegenteil 1999 belegt wurde. Jetzt gelten 300-stellige Zahlen als nicht faktorisierbar.

Die "Veröffentlichungen", die es zu diesem Thema gibt und mir zugänglich sind, wirken kaum wie seriöse wissenschaftliche Arbeiten. Ich hatte mal versucht die merkwürdigen Andeutungen, z.B. in dem Werk von Pommerance, zu verstehen und hier verständlich aufzuschreiben. Nach meinem Eindruck enthalten diese Arbeiten trotz einiger Merkwürdigkeiten viele Fakten, die aber nur seltsam verschleiert dargestellt werden.

Franz Scheerer

Was ist Fakt

Fakt ist vor allem eines

• RSA 640 is factoed!
• RSA 200 is factoed!
• RSA 576 is factoed!
• RSA 160 is factoed!
• RSA 155 is factoed!
• RSA 140 is factoed!

was unter http://www.rsasecurity.com/rsalabs/node.asp?id=2093 nachzulesen ist. Es sind ausnahmslos alle RSA-Challenges bis zu einer Größe von 200 Dezimalstellen faktorisiert. Die größeren Zahlen geben die Zahl der Stellen im Dualsystem an. Fakt ist weiterhin, dass dies in den 80-er Jahren für alle diese Zahlen als faktisch als ausgeschlossen galt. Selbst für eine nur 100-stellige Zahl sollte dies nach damaligen Schätzungen von einer Million bis Quatrillionen Jahre erfordern.

Es kann nicht eindeutig festgestellt werden, ob auch bereits größere Zahlen faktorisiert oder die Faktorisierung in Wahrheit nicht bereits früher erfolgte. Mit welchen Verfahren, in welcher Zeit, mit welchem Rechenaufwand, mit welcher Hardware und Software die Faktorisierung jeweils erfolgte, ist weniger eindeutig. Ich sehe zumindest nicht, wie diese Angaben auf ihre Richtigkeit geprüft werden sollten. Die Beschreibung der Algorithmen, die zu den jeweiligen Faktorisierungen verwendet wurden, beschränkt sich meist auf einige Schlagworte und eine mehr oder minder fantasievolle Bezeichnung des Verfahrens.

Die Abschätzungen über die asymmtotische Laufzeit sind daher in keiner Weise nachvollziehbar. Die Frage wie sich die Laufzeit eines solchen Verfahrens für beliebig große Zahlen verhält erscheint mir ohnehin von eher geringem Interesse. Interessanter wäre die Frage, mit welchem Aufwand heute übliche RSA-Module faktorisiert werden könnten. Dazu gibt es aus meiner Sicht keine glaubhaften Angaben. Warum sollte die Faktorisierung einer 212-stelligen Zahl weit aus schwieriger sein, als die Faktorisierung einer 200-stelligen.

Zur Faktorisierung von RSA-200 wird ein Rechenaufwand von unter 200 GHz-Jahren angegeben. Dies entspricht in etwa 200 GFLOPS-Jahre. Ein moderner Supercomputer könnte einen solchen Rechenaufwand in wenigen Tagen bewältigen. Franz Scheerer

Dynamische Faktorbasis mit Pseudoprimzahlen

Die Zerlegung der $Q(x)=x^{2}-n$ beim QS in Primfaktoren ist nicht optimal, da die Bestimmung der Primfaktorenzerlegung oft nicht effizient ist. Beim QS werden daher nur glatte Zahlen in ihre Primfaktoren zerlegt und die übrigen Relationen werden ausgesiebt, also nicht berücksichtigt, obgleich sie eventell zur Faktorisierung genutzt werden könnten. Es können jedoch alle Relationen $(x,Q(x)=x^{2}-n)$ effizient faktorisiert werden, wenn diese nicht in Primzahlen sondern in Pseudoprimzahlen faktorisiert werden.

Mit Pseudoprimzahlen bezeichnen wir dabei die Zahlen, die keine Qudratzahlen sind und nicht effizient mit der Pollard-Rho-Methode in etwa 1000-Iterationsschritten faktorisiert werden können. Selbst 100-stellige Zahlen lassen sich in wenigen Sekunden vollständig in Pseudoprimzahlen zerlegen oder sind selbst Pseudoprimzahlen. Die Zerlegung ist nicht immer eindeutig aber in den meisten Fällen identisch mit der "echten" Primfaktorzerlegung.

Das Verfahren im Auswahlschritt lässt sich exakt in gleicher Weise wie beim QS mittels der linearen Algebra durchführen. Der "Siebschritt", der jetzt nur aus der effizienten Faktorisierung aller Relationen in Pseudoprimzahlen besteht, kann leicht auf jedem gewöhnlichen PC implementiert werden. Unter Linux kann dazu bc benutzt werden. Dieses Verfahren kann verteilt im Internet durchgeführt werden.

Die Faktorbasis der Pseudoprimzahlen braucht nicht vorab berechnet werden, sondern wird einfach aus den berechneten Zerlegungen bestimmt. Speichert man die Pseudoprimzahlen in einer relationalen Datenbank, kann die Basis, die Liste der Pseudoprimzahlen, mit einem Statement der Art

select distinct pseudoprim from base

bestimmt werden. Franz Scheerer

Wieder schmeisst du alles was du mal gehört hast in einen Topf und rührst es zu einer dünnen Brühe. Ein guter Koch sollte seine Zutaten und das Ergebnis gut kennen. Die Auswahl der Faktoren der Faktorbasis ist sehr bewusst. Nur die Hälfte aller Primzahlen ist geeignet. Ausserdem braucht man eine FESTE Faktorbasis, um den Auswahlschritt über der Matrix effizient machen zu können. Ein Faktor der Faktorbasis entspricht einer Zeile der Matrix. Wenn du die Anzahl der Faktoren (durch die Aufnahme von Pseudoprimzahlen) erhöhst, musst du auch mehr solcher Zahlen finden, um das darunterliegende Gleichungssystem lösen zu können. D.h. das Verfahren wird insgesamt langsamer. Keine gute Idee. Zur Bestimmung der Primfaktoren wird ja das SCHNELLE Siebverfahren genommen, und nicht langsam mit Probedivision oder Pollard-Rho-Methode. -- Thilo Harich

Partielle Relationen und Kreise

Diese von mir vorgeschlagene Erweiterung des Artikels ist die Erklärung der Large Prime Quadratic Sieve Variante was wiederum auf dem Multiple Polynomial Quadratic Sieve bzw. Self Initializing Quadratic Sieve beruht. Man sollte davor zumindest das Multiple Polynomial Quadratic Sieve erklären. Was ich auch tun würde. Das Large Prime Quadratic Sieve ist quasi das Ende der Fahnenstange des QS. Es handelt sich um die Erklärung eines existierenden Verfahrens:

Selbst wenn eine Relation nicht glatt ist, können zwei (oder mehr) solcher partiellen Relationen zu einer glatten Kongruenz kombiniert werden. Dies ist nur der Fall, wenn die partiellen Relationen die gleichen Primzahlen außerhalb der Faktor Basis haben.

Beipiel: Zu n=91 und der Faktor Basis {2,3,5,7} finden sich die partiellen Relationen:

$21^{2}\equiv 7^{1}\cdot 11{\pmod {91}}$

$29^{2}\equiv 2^{1}\cdot 11{\pmod {91}}$

Diese ergeben das Produkt:

$(21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}\cdot 11^{2}{\pmod {91}}$

Durch Multiplikation mit (11²)⁻¹ modulo 91 (11⁻¹ modulo 91 ist 58), erhalten wir folgende glatte Relation:

$(58\cdot 21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}$

$14^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}$

Solch eine volle Relation die aus der Multiplikation von partiellen Relationen entstanden ist nennt man auch Kreis. Durch Partielle Relationen kann man die in einem gegebenen Suchintervall auffindbaren glatten Relationen erhöhen und somit die Laufzeit verbessern.

Die Large Prime Quadratic Sieve Variante betrachtet nur Primzahlen außerhalb der Faktor Basis, die nur um einen konstanten Faktor c größer sind als die Schranke S der Primzahlen der Faktor Basis. Damit ist gewährleistet dass pro Relation nur ein Faktor außerhalb der Faktorbasis liegt. Somit genügen zwei partielle Relationen um eine volle Relation zu bilden. Das Finden der einfachen großen Faktoren kostet dabei nur einen geringen Mehraufwand: In Schritt 3 wird die Konstante T um log (c * S) erhöht. Die Primfaktorzerlegung wird nach wie vor nur über der Faktorbasis bestimmt. Falls danach ein Faktor kleiner als c*S übrig bleibt wird dieser vermerkt. Dieser Faktor ist notwendigerweise größer als die Faktoren aus der Faktorbasis. Falls eine weitere Relation mit diesem Faktor auftaucht werden beide zu einer glatten Relation zusammengefasst.

Es gibt eine weitere komplexere Variante, die auch Faktoren der Größenordnung S² erlaubt.

Was ist daran wirklich neu

Ich verstehe nicht was an diesen Relationen und Kreisen nun eine wirkliche Neuerung sein soll. Klar ist es das Ziel des Verfahrens mehrere Relationen zu multiplizieren, um damit letztlich eine Quadratzahl zu finden. Wenn zwei Relationen zusammengefasst werden können, so dass daraus ein Produkt mit kleineren Primfaktoren entsteht, ist dies ein Schritt in diese Richtung. Eigentlich ist das aber bereits der Auswahlschritt, also die Lösung des linearen Gleichungssystems.

Benutzer:Fsswsb 18.04