Sensation oder Bluff: liegt die Faktorisierung bald nicht mehr in NP?

Question

Das ist jetzt nicht gerade Schulmathematik, ich hoffe es gibt trotzdem ein paar interessierte Zahlentheoretiker unter euch.

Seit einiger Zeit beschäftigt mich die Darstellung von natürlichen Zahlen als Summe von Quadraten. Bekannt ist, dass jede Zahl \(\in\mathbb{N}\)  in die Summe von höchstens vier Quadraten dargestellt werden kann. Interessant für mich sind besonders diejenigen, die als Summe von genau zwei Quadraten dargestellt werden können.

sei \(\ p \in \mathbb{P}\wedge p\equiv 1 (mod\ 4)\ \quad a,b\in\mathbb{N}^{+}\wedge a \gt b \)

dann gibt es für \( p=a^2+b^2 \) genau eine Lösung.

Effiziente Algorithmen dafür sind bekannt, spätestens seit Brillhart (1972).

Für zusammengesetzte Zahlen galt bisher , dass deren Primfaktorzerlegung (im wesentlichen) bekannt sein muss, um sie als Summe von Quadratzahlen darstellen zu können.

Darío Alpern zeigt jedoch einen Algorithmus, der zusammengesetze Zahlen in Polynomialzeit als Summe von Quadraten darstellt. Sum of squares scheint die Gesetze der klassischen Mathematik außer Kraft zu setzen.

Beispiel:
Von der zwölften Fermatzahl: \(F_{12}=2{^2}^{12}+1 \) sind bisher 6 Faktoren bekannt. Der zusammengesetze Rest (1133 Dezimalstellen) wird von Alpern's Algorithmus (nahezu) sofort in die Summe zweier Quadratzahlen zerlegt.

Wie ist das möglich? Kann jemand den Algorithmus erläutern?

Für alle Fermatfaktoren gilt \( \equiv 1 (mod\ 4) \) und bislang auch die quadratfreiheit.
Deshalb kann jede Fermatzahl mit \(n\)-Faktoren aus genau \( 2^{n-1} \) verschiedenen Summen zweier Quadrate dargestellt werden. Sind alle Summen bekannt, sollten auch die Primfaktoren über ein Gleichungssystem ermittelt werden können. Das entspricht dann allenfalls der Komplexitätsklasse P.

Ist das das der Anfang vom Ende der Faktorisierung in der Komplexitätsklasse NP ?

Was meint ihr?

Comments

Sorry, wenn ich die formalen Konventionen hier in Deutschland nicht exakt einhalte.
Es ist nicht so leicht alles exakt auszudrücken, wenn man ständig zwischen den Sprachen wechselt.
'Sum of squares' means 'Summe der Quadratzahlen'

Edit: wenn ich von 'Summe von  n Quadraten' spreche, meine ich einvernehmend mit der deutschen Konvention: ' Summe von n Quadratzahlen'

---

Ihr/Dein Deutsch ist besser und verständlicher als 60 % aller Fragen hier im Forum.

Der Tipp kam so schnell, dass ich hier fast ein Insider vermute (Beteiligter am Code/Internetseite?)...

Der Algorithmus ist wirklich beeindruckend! Noch dazu die Erweiterung auf über 1000stellige Zahlen mit einer so langsamen Sprache wie JavaScript -> und trotzdem so schnell !

JavaScript ist kompatibler und sicherer als das JAVA-Applet der anderen Rechner (Calculators), die auf vielen Browsern (Google Chrome usw.) absichtlich NICHT mehr funktionieren, da der User sonst jegliche Rechte an JAVA abgibt.

Nach den vielen Hausaufgaben-Fragen eine tolle Abwechslung.

Danke.

Answer 1

Zunächst danke für den LINK, der sogar den Quellcode beinhaltet.

Das die Seite selbst offline (lokal gespeichert) funktioniert,

gibt es auch kein Trick mit online abgelegten Tabellen.

Erklärung hier:

https://www.alpertron.com.ar/4SQUARES.HTM

Der Autor ist auch Herausgeber der "Elliptic Curve Method"

wo große Zahlen (Primzahlen bis 60 Stellen) relativ schnell in Faktoren zerlegt werden.

zu "...scheint die Gesetze der klassischen Mathematik außer Kraft zu setzen"

Auch ich staune oft über neue Algorithmen, die zusammen mit Ausnutzung der neuen CPU-Befehle (keine Interpreter  oder .NET, sondern AVX und Multitasking)

unglaublich schnell sind.

Beispiel nextProbablePrime(x) liefert in wenigen Sekunden die nächste Primzahl bis 3000 stellig.

Irrtum 2^{-100} -> nach 3 Jahren Suche mehrerer Leute wird vermutet, dass die erste "falsche" nicht unter 10000 stellig ist.

Oder Carmichael Faktorisierung: bei vielen Zahlen (400 .... 1000 stellige erfolgreich getestet) gibt's eine Abkürzung für Faktorisierung. -> konnte selbst eine 400stellige in die Internet-Datenbank eintragen.

Anders: es wird immer schwerer, echt gute RSA Zahlen zu finden, die Prime(x)*Prime(y) sind und nicht durch gute Algorithmen "gefunden" werden.

Dass Algorithmen immer besser werden, bedeutet aber nicht, dass alte Gesetze "außer Kraft" gesetzt werden (das wäre nur der Beweis, dass die alten falsch/unvollständig waren).

Habe bisher noch keine Fehler auf der "Sum of Squares" gefunden -> der Autor bietet aber LINK zum Melden von Fehlern an.

Auch interessant: Fibonacci-Zahlen

Viele kennen nur die explizite Formel oder die Rekursion aus den beiden Vorgängern.

Ab 100 Mio. stelligen Zahlen werden beide (wenn man alle Stellen exakt haben will) extrem langsam.

Es gibt aber noch bessere Algorithmen! Habe gerade einen ausprobiert und

Fibonacci(1 Mrd.=1e9) berechnet!

Comments

Hier Beispiele, wo falsch gerechnet wird:

sum=2260138526203405784941654048610197513508038915719776718321197768109445641817966676608593121306582577250631562886676970448070001811149711863002112487928199487482066070131066586646083327982803560379205391980139946496955261;

r=36691897499967975162088880039389333347428995019323458426574310444158434779986104305812297550685479243949995526;

s=30229839299196574443602572935363619369132005445014208049848320311929528735935192338347447943403216610503106779;

t=108;

print "a= \n",quad3(sum,r,s,t),"\n" ergibt -1172080 statt 0

sum=2260138526203405784941654048610197513508038915719776718321197768109445641817966676608593121306582577250631562886676970448070001811149711863002112487928199487482066070131066586646083327982803560379205391980139946496943597;

r=46020071290999814424827424417841199736564563503643059738567950254691094019381753021900724769131399827216342760;

s=11928602792225938588782650789095279343896836444475604681128097046257306950549208709773599303112472741107173806;

t=1;

print "a= \n",quad3(sum,r,s,t),"\n" ergibt -360 statt 0

sum=40386086203521847842442038116961395908045388225743593887534051882867088867451422279926227658353369309602134937818767935489955578234805439581534625494985324713549730074875381338741302421655631135507379857269344735228428553001352597596691638801743636629329355013511352942721273050339170429834278987040381747960884411851433916486144170476008852597093750739127802680309124526032940172579802008470093339990359384991503503614458710698904103258512429909701566697333753540519871100983916899540657050034590964623607736274756781417764221105569531562147057912826327014822324375878810085123801163054580870423717464500275259286644790292287618742984022979008217487409481420224445378839089353872030913057691176817044086502550278535272750787424451118761716552849620868806555149154293300951201837849814408323169458959040706805689440625767829357238882085766112685307073105174963070427573702738362159098805163558648031695168433171835632969724871377060199849541218845177450315677176119955499412825504179204908105894697957170244421770769366517833025139901383316838896066622320648993411213811241118825043233830644947321875736006536117418021434702300430337;

r=200632848085394229198405077309776409669556160755822894920478194045891524675173877582799789843512719390209285348887171584058267613825062519170949236869832740299611688879431491248560122275125138227835639875304442149679485916420376715785002453587853905329008047468218821526665318251417289791164787502264540469658007753188396466487968753988674615092615847790001421479841641921279595503860736218792224235350272376658369292603790019796500735806899786991660195728966759044116399240680328117271881207382080232786405040556863376322477213246700048245459183343930058344600346916;

s=11512882899820054257144225772505994511430981968359355559240636997087397239461885404688940982112272498773691260355731224763278685518244745544198267923163368736091123701779226072209279679342867029500044275233215203437226071842172804234583591297137729569486761340213325710137879698831126615998659706343950808674850862574868322314902443424081205544133789500128645355501388833990928089030944977862262874243179626287736961093227838096073086612878632276868708056678373714902078426666851025890207418013027573248367464970951431311736356210867866665430397629513384884406535591;

t=0;

print "a= \n",quad3(sum,r,s,t),"\n" ergibt 0 OK

---

Nein er rechnet nicht falsch, es wird nur falsch dargestellt.

Tipp: stelle den zeiger "Number of digits per group" auf 9999 anstatt auf 0.

---

Danke für den Tipp.

Das ist ja ein Bug: statt 0=keine Leerzeichen einfügen (was ja auch bei den ersten beiden funktioniert)

bedeutet 0=zufällig hinten Ziffern weglassen ... mal nur 1 oder 3 Ziffern anzeigen ... :-(

Bleibt aber trotzdem ein toller Algorithmus! Selbst mit langsamen JavaScript sehr schnell!

---

interessant:

RSA-1536 Status: Not Factored Decimal Digits: nur 463 

benötigt etwa die 10-fache Berechnungszeit (> 35 s) gegenüber vielen 1000 stelligen Zahlen (< 4 s)!

zu: "Sind alle Summen bekannt, sollten auch die Primfaktoren über ein Gleichungssystem ermittelt werden können..."

Bezieht sich vermutlich auf "nur Fermat" und "nur 2 Summanden aus Quadratzahlen", denn

alle untersuchten RSA-Zahlen bestanden aus 3 oder 4 Summanden.