Alle Zahlen faktorisieren < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 05:35 So 06.11.2011 | | Autor: | krzyzape |
DEFDBL A-Z:
DEF SEG = 0: SCREEN 12
CLEAR , , 2000
a = 101
FOR d = 0 TO 400 STEP 2
vv = 30
b = a + vv
p = a * b
zz = 1
ga = INT((((vv / 2 - 1) ^ 2) * 2) / 4)
FOR y = ((a - b) / 2 + b) - 10 TO ((a - b) / 2 + b) + 10
zz = zz + 1
IF zz MOD 25 = 0 THEN
zz = 1
END IF
dt = (p - ((y - (d / 2 - 1)) * (d - 2) + ((y - (d / 2 - 1))) ^ 2)) * 2
dt = (dt - 2) / 2
LOCATE zz + 1, 1: PRINT "y="; y
LOCATE zz + 1, 10: PRINT "ga="; ga; " d-test="; dt
PRINT " "
PRINT " a="; a; " b="; b; "P="; a * b; "b-a= "; b - a; " Bingo (a+b)/2 ="; (a + b) / 2;
"d="; d
NEXT
LOCATE 30, 1: INPUT ; a7
IF a7 = 1 THEN END
CLS
NEXT
---------------------------------------------------------------
ok hier mal ein Beispiel !!!
P=a*b
P=101 *131
vv=b-a=131-101=30
y=(a+b)/2=116 Das ist der Wert für y
Alle dt- Werte bis einschließlich y=1 bis y=115 sind Positiv !!!!
Alle dt-Werte über y=115 sind negativ.Das ist wichtig ,
denn das ist unser Nullpunkt.
Die Werte bei y=116
d=0 dt=-225
d=2 dt-226
d=4 dt=-225
d=6 dt=-222
d=8 dt=-217
d=10 dt=-210
d=12 dt=-201
d=14 dt=-190
d=16 dt =-177
d=18 dt=-162
d=20 dt=-145
d=22 dt=-126
d=24 dt=-105
d=26 dt=-82
d=28 dt=-57
d=30 dt=-30 Bingo!! ist gleich b-a
Und so verhalten sich "alle" Zahlen wenn a>ga für alle d und nicht nur 30
Das Programm ist im kostenlosen QBASIC geschrieben.
Einfach Quelltext kopieren und in den MS-Editor einfügen und speichern.
Dann die Dateiendung .txt in .bas ändern. Dann selbige mit Qbasic 4.5 öffnen
und starten.
Kommentar oder Hilfe
Die Faktorisierung kann man bei y=(a+b)/ 2 ablesen (+-)-Grenze, weil dann zb
bei
a=101 und d = 30 dt =- 30 ergibt.
das gilt für alle a über den Wert a =97.
der dt-Wert bei y=(a+b)/2 ist bei bei allen a Konstant.
bei a >ga zeigt das - (minus) genau auf diese Stelle .
Darüber ist +.
Somit sind alle Zahlen mit a>ga direkt faktorisierbar !!!
für die a unter den Grenzwert GA beginnt der Nullpunkt zu wandern.
Man muß P einfach mit einer Zahl multiplizieren und bekommt eine
berechenbare raus ( a>ga).
Wenn man d =0 setzt, sieht man was ich meine.
y=(a+b)/2 dann [mm] dt=-((((b-a)/2)^2)
[/mm]
somit ist jedes Produkt direkt teilbar was zu finden war
zb wenn bei 3* 13 a (die 3) unter ga wäre dann P mal zB 3 nehmen
dann wäre das neue P (3*3) *13 (13-9)
Delta (b-a) also kleiner und somit ga also kleiner und 13 direkt berechenbar.
was zu finden war (3*13)
PS2
Übrigens
bei (a+b)/2 [mm] =-((((b-a)/2)^1) [/mm] und d=0 nähert sich der wert (a+b)/2
------------------------------------------------
PS. Der Wert ist an der Grenze (+-) bei d=0 abzulesen. Das ist der Bezugspunkt
ohne den keine Ablesung möglich wäre.
Wenn d =-vv beträgt ist das b-a gefunden !!!!
Daß alle Zahlen a >ga direkt faktorisierbar sind weiß ich !!!
Es geht nur um den Kram a<ga und das soll P*x lösen.
Ich freue mich auf eure Kommentare !!!
PS
Den Nullpunkt zu finden dürfte im binär-Sortiersystem eigentlich kein großes
Problem darstellen.
Wenn p > gp = int(((vv / 2) ^ 2 - 1) ^ 2) dann ist auch a>ga.
Somit wäre die Erweiterung x*p prinzipiell auch kein Problem.
--------------------------------------------------------------------------
Hier das Programm zur Formel.
DEFDBL A-Z:
DEF SEG = 0: SCREEN 12
CLEAR , , 2000
CLS
INPUT ; "Bitte P eingeben"; P
IF P = 0 OR P = 1 THEN END
REM ga = INT((((d / 2 - 1) ^ 2) * 2) / 4)
REM gp = INT(((d / 2) ^ 2 - 1) ^ 2)
y = (P - 1) / 2
s = y
start:
dt = (((P - ((y - (d / 2 - 1)) * (d - 2) + ((y - (d / 2 - 1))) ^ 2)) * 2) - 2) / 2
t = y
IF dt < 0 OR dt = 0 THEN y = y - INT(s / 2): GOTO sp
IF dt > 0 THEN y = y + INT(s / 2)
sp:
s = INT(s / 2)
IF y = t THEN GOTO weiter
GOTO start
weiter:
tt = tt + 1
y = y + 1
dt = (((P - ((y - (d / 2 - 1)) * (d - 2) + ((y - (d / 2 - 1))) ^ 2)) * 2) - 2) / 2
IF dt < 0 or dt =0 THEN GOTO runter
IF dt > 0 THEN GOTO weiter
schluss:
CLS
d = SQR(ABS(dt)) * 2
LOCATE zz + 1, 1: PRINT "(a+b)/2 = y = "; y; " dt="; dt; " b-a ="; d
END
runter:
IF tt > 5 THEN GOTO schluss
tt = tt + 1
y = y - 1
dt = (((P - ((y - (d / 2 - 1)) * (d - 2) + ((y - (d / 2 - 1))) ^ 2)) * 2) - 2) / 2
IF dt < 0 or dt =0 THEN GOTO runter
IF dt > 0 THEN GOTO weiter
-----------------------------------------------------
Wenn a > ga sind die Faktoren sofort da !!!
MfG
Meine Formel funktioniert zu 100 Prozent und ich bin mir über dessen Bedutung im klaren.
Keine Computerverschlüsselung mehr !!!
MfG
KRZYZAPE
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 06:15 So 06.11.2011 | | Autor: | krzyzape |
Anmerkung meinerseits.
P=11*31
a<ga also nicht lösbar
Nun kommt mein nächster Geniestreich
P*3 =31*33 a>ga und somit lösbar
Ich weiß ich habe einen jahrtausende alten Menschheitstraum erfüllt.
Helft mir ,daß die oben ihn nicht mehr zerstören können.
MfG
KRZYZAPE
|
|
|
| |
|
> Anmerkung meinerseits.
>
> P=11*31
> a<ga also nicht lösbar
>
> Nun kommt mein nächster Geniestreich
>
> P*3 =31*33 a>ga und somit lösbar
>
> Ich weiß ich habe einen jahrtausende alten
> Menschheitstraum erfüllt.
Das ist ja gewaltig !
Alles Gute ...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:18 So 06.11.2011 | | Autor: | krzyzape |
Darum gehts nicht.
Es geht darum, daß dieses Programm in polynominaler Zeit jedes Produkt
faktorisiert, du Genie.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:57 So 06.11.2011 | | Autor: | tobit09 |
> Es geht darum, daß dieses Programm in polynominaler Zeit
> jedes Produkt
> faktorisiert, du Genie.
Wenn der Algorithmus das nicht schaffen würde, wäre er auch ein sehr schlechter. Z.B. durch Ausprobieren aller denkbaren Teiler erhält man auch einen Algorithmus von polynomialer Laufzeit.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:02 So 06.11.2011 | | Autor: | krzyzape |
Nein das stimmt nicht.
Deshalb hat RSA ja auch bis jetzt funktioniert.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:31 So 06.11.2011 | | Autor: | reverend |
Hallo krzyzape,
Tobias hat Recht. Die einfache sequentielle Teilersuche ist natürlich polynomial.
Wenn Dein Algorithmus so gut ist, dann zerleg doch einfach eine der noch nicht faktorisierten ![[]](/images/popup.gif) RSA-Zahlen, z.B. RSA 704.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:45 Di 08.11.2011 | | Autor: | felixf |
Moin,
> Tobias hat Recht. Die einfache sequentielle Teilersuche ist
> natürlich polynomial.
so einfach ist das nicht. Die grosse Frage ist: polynomiell in was?
In der Komplexitaetstheorie, wo man von polynomieller oder exponentieller Laufzeit spricht, bezieht man sich immer auf die Groesse $n$ der Eingabe. Die Eingabe ist hier die Zahl $N$, die zu faktorisieren ist. Die Groesse der Eingabe ist also die Anzahl Bit, die man benoetigt, um diese Zahl darzustellen. Die Groesse $n$ ist also [mm] $\approx \log_2 [/mm] N$.
Da die Teilersuche polynomiell in $N$ ist, ist sie somit exponentiell in $n$, also exponentiell in der Eingabegroesse.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:08 Di 08.11.2011 | | Autor: | reverend |
Hallo Felix,
> > Tobias hat Recht. Die einfache sequentielle Teilersuche ist
> > natürlich polynomial.
>
> so einfach ist das nicht. Die grosse Frage ist: polynomiell
> in was?
>
> In der Komplexitaetstheorie, wo man von polynomieller oder
> exponentieller Laufzeit spricht, bezieht man sich immer auf
> die Groesse [mm]n[/mm] der Eingabe. Die Eingabe ist hier die Zahl [mm]N[/mm],
> die zu faktorisieren ist. Die Groesse der Eingabe ist also
> die Anzahl Bit, die man benoetigt, um diese Zahl
> darzustellen. Die Groesse [mm]n[/mm] ist also [mm]\approx \log_2 N[/mm].
>
> Da die Teilersuche polynomiell in [mm]N[/mm] ist, ist sie somit
> exponentiell in [mm]n[/mm], also exponentiell in der
> Eingabegroesse.
Ja, klar. Ich hatte nur den Eindruck, der Behauptung hier läge die Annahme zugrunde, die Faktorisierung sei bisher exponentiell in N gewesen, und das ist sie ja nicht.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:51 So 06.11.2011 | | Autor: | reverend |
Hallo krzyzape,
hier ein einfacheres Beispiel mit "nur" 113 Dezimalstellen:
87.714.969.705.038.411.076.272.137.418.539.099.801.877.190.558.970.371.113.
762.453.702.525.982.911.939.243.939.521.562.715.111.692.818.014.473.106.391
Das ist das Produkt aller Primzahlen bis einschließlich 277, zuzüglich 1.
Eine Zerlegung ist m.W. bisher nicht publiziert, sie liegt mir aber vor. Es gibt drei Faktoren, davon zwei sehr große.
Die Zerlegung hat mit spezialisierten Programmen auf normalen PCs (4 an der Zahl) etwa sieben Tage gedauert. Mit den schnellsten heute handelsüblichen sollte ein PC das sogar in etwa 3 Tagen schaffen (Methode: quadratisches Sieb). Mit elliptischen Kurven dauerts wesentlich länger, geschätzt 8 Tage.
Natürlich musst Du Dein Programm dann erst auf "Langzahlen" umstellen, aber der Algorithmus kann ja der gleiche bleiben.
Viel Erfolg!
reverend
PS: einfacher einzulesen ist die Zahl natürlich ohne Punkte. Wegen der Fensterbreite habe ich eine einzige Leerstelle eingebaut, die musst Du dann wieder löschen.
8771496970503841107627213741853909980187719055897037111376245370252598
2911939243939521562715111692818014473106391
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:22 So 06.11.2011 | | Autor: | tobit09 |
Hallo krzyzape,
ich muss dich enttäuschen:
Die Schwierigkeit zum Hacken von RSA liegt nicht darin, irgendeinen Algorithmus zu finden, der natürliche Zahlen faktorisiert. Du bist nicht der erste, der einen solchen Algorithmus findet.
Die Schwierigkeit liegt vielmehr darin, einen entsprechenden Algorithmus zu finden, der so schnell ist, dass er die extrem großen Zahlen (mehrere hundert Dezimalstellen), die zur Verschlüsselung verwendet werden, in akzeptabler Zeit faktorisieren kann.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:06 So 06.11.2011 | | Autor: | krzyzape |
Und genau das leistet meine formel.
Gib das (Programm zur Formel) in Qbasic ein, dann siehst du es.
MfG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:59 So 06.11.2011 | | Autor: | krzyzape |
| 1: | DEFDBL A-Z:
| | 2: | DEF SEG = 0: SCREEN 12
| | 3: | CLEAR , , 2000
| | 4: | CLS
| | 5: |
| | 6: | INPUT ; "Bitte P eingeben"; P
| | 7: | IF P = 0 OR P = 1 THEN END
| | 8: | y = (P - 1) / 2
| | 9: | s = y
| | 10: |
| | 11: | start:
| | 12: | dt = P - y^2
| | 13: | t = y
| | 14: | IF dt < 0 OR dt = 0 THEN y = y - INT(s / 2): GOTO sp
| | 15: | IF dt > 0 THEN y = y + INT(s / 2)
| | 16: |
| | 17: | sp:
| | 18: | s = INT(s / 2)
| | 19: | IF y = t THEN GOTO weiter
| | 20: | GOTO start
| | 21: |
| | 22: | weiter:
| | 23: | tt = tt + 1
| | 24: | y = y + 1
| | 25: | dt = P - y^2
| | 26: | IF dt < 0 or dt=0 THEN GOTO runter
| | 27: | IF dt > 0 THEN GOTO weiter
| | 28: |
| | 29: | schluss:
| | 30: | CLS
| | 31: | d = SQR(ABS(dt)) * 2
| | 32: | ga = INT(((d / 2 - 1) ^ 2) / 2)
| | 33: | LOCATE zz + 1, 1: PRINT P; " = "; (y-d/2); " * "; (y+d/2); ", ga = "; ga;
| | 34: | END
| | 35: |
| | 36: | runter:
| | 37: | IF tt > 5 THEN GOTO schluss
| | 38: | tt = tt + 1
| | 39: | y = y - 1
| | 40: | dt = P - y^2
| | 41: |
| | 42: | IF dt < 0 or dt=0 THEN GOTO runter
| | 43: | IF dt > 0 THEN GOTO weiter
| | 44: |
| | 45: |
| | 46: | Hier eine Vereinfachung des Algorithmuses
|
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:06 Di 08.11.2011 | | Autor: | felixf |
Moin!
> | 1: | DEFDBL A-Z:
| | 2: | > DEF SEG = 0: SCREEN 12
| | 3: | > CLEAR , , 2000
| | 4: | > CLS
| | 5: | >
| | 6: | > INPUT ; "Bitte P eingeben"; P
| | 7: | > IF P = 0 OR P = 1 THEN END
| | 8: | > y = (P - 1) / 2
| | 9: | > s = y
| | 10: | >
| | 11: | > start:
| | 12: | > dt = P - [mm]y^2[/mm]
| | 13: | > t = y
| | 14: | > IF dt < 0 OR dt = 0 THEN y = y - INT(s / 2): GOTO sp
| | 15: |
| | 16: | Was soll eigentlich dieses voellig ueberfluessige "GOTO sp"?
| | 17: |
| | 18: | > IF dt > 0 THEN y = y + INT(s / 2)
| | 19: | >
| | 20: | > sp:
| | 21: | > s = INT(s / 2)
| | 22: | > IF y = t THEN GOTO weiter
| | 23: | > GOTO start
| | 24: | >
| | 25: | > weiter:
| | 26: | > tt = tt + 1
| | 27: | > y = y + 1
| | 28: | > dt = P - [mm]y^2[/mm]
| | 29: | > IF dt < 0 or dt=0 THEN GOTO runter
| | 30: | > IF dt > 0 THEN GOTO weiter
| | 31: | >
| | 32: | > schluss:
| | 33: | > CLS
| | 34: | > d = SQR(ABS(dt)) * 2
| | 35: | > ga = INT(((d / 2 - 1) ^ 2) / 2)
| | 36: | > LOCATE zz + 1, 1: PRINT P; " = "; (y-d/2); " * "; (y+d/2);
| | 37: | > ", ga = "; ga;
| | 38: | > END
| | 39: | >
| | 40: | > runter:
| | 41: | > IF tt > 5 THEN GOTO schluss
| | 42: | > tt = tt + 1
| | 43: | > y = y - 1
| | 44: | > dt = P - [mm]y^2[/mm]
| | 45: | >
| | 46: | > IF dt < 0 or dt=0 THEN GOTO runter
| | 47: | > IF dt > 0 THEN GOTO weiter
| | 48: | > |
>
> Hier eine Vereinfachung des Algorithmuses
Warum postest du den Algorithmus nicht a) ohne alle Eingabe/Ausgabe-Teile, und b) in einer vernuenftigen, gut lesbaren Programmiersprache? GOTOs sind seit Jahrzehnten out. (Ausserdem: wer hat schon QBasic oder aehnliches auf dem Rechner?)
Mal davon abgesehen: wo ist dein Beweis, dass dieses Programm in [mm] $O(poly(\log_2 [/mm] P))$ Schritten fertig wird und eine echte Faktorisierung ausspuckt? Oder ist das eine (unbewiesene) Vermutung von dir?
Ich habe mal versucht, das Programm in C++ zu uebersetzen. Bei der Eingabe 116 gibt es mir "116 = 7.46887 * 15.5311, ga = 4" aus.
LG Felix
|
|
|
|
