Hier das geforderte Programm |
05.11.2011, 14:34 | krzyzape | Auf diesen Beitrag antworten » | |||||||
Hier das geforderte Programm 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 MfG krzyzape PS Falls a<ga dann P einfach mit einer Primzahl multiplizieren. Wenn dt dann ein negatives Quadrat ist Bingo. Das läuft würde Arno Dübel sagen Beim Nullpunkt finden hab ich noch n Fehler drin Werde ich sofort reparieren ---------------------------------------------------- So das ist die reparierte Version PS. Wenn diese Formel funktioniert, dann stimmt etwas mit unserem Bildungssystem nicht Good will hunting PS Also Leute, ich weiß nicht in welcher Phase des Mahatma Gandhi ich mich hier gerade befinde, Ignorier oder Kampfphase. Aber eines weiß ich jetzt ganz genau, nachdem ich mein Prog habe etwas laufen lassen: Ich gewinne . Gruß an Charlie Sheen. 11*31 <ga 3*11*31 >ga und bingo MfG PS Keiner stoppt dieses geniale Programm (Virus) mehr. Es wird die Welt verändern !!!!!!!!!!!!!!!!!!!!!! Habe die Ehre |
|||||||||
06.11.2011, 11:35 | Airblader | Auf diesen Beitrag antworten » | |||||||
Ich habe jetzt ein P eingegeben (ich verrate dir nicht, welches!). Die Ausgabe deines Programms:
In deinem Beitrag sagtest du "Bingo", falls dt ein negatives Quadrat ist. Das ist hier der Fall (dt = -25 = -5²). Wie lauten nun die Faktoren von P? air |
|||||||||
06.11.2011, 12:05 | krzyzape | Auf diesen Beitrag antworten » | |||||||
Hi Air 144*2 =a+b=288 (a+b)-(b-a)=2a 288-10=278 a=278/2=139 a+(b-a)=b 139+10=149 a*b =p 139*149=20711 Wie du jetzt selbst sehen kannst der Algorithmus funktioniert 1a. Gruß Krzyzape |
|||||||||
06.11.2011, 12:19 | Airblader | Auf diesen Beitrag antworten » | |||||||
Also gut. Das Ergebnis stimmt schonmal. Jetzt werd nicht zu euphorisch, solche Primzahlen zu faktorisieren ist noch kein Meisterwerk. Für alle anderen habe ich dein Programm mal modifiziert, so dass sie sich die Rechnerei sparen können; das Programm gibt die Faktoren nun direkt aus: Edit: Aktuellste Version weiter unten. Wie soll man sich verhalten, wenn dein Programm nicht-ganzzahlige Werte als Faktoren ausspuckt? Und nein, einfach runden tut's auch nicht, die Werte sind weit daneben. air |
|||||||||
06.11.2011, 12:38 | krzyzape | Auf diesen Beitrag antworten » | |||||||
hi Air Ja, danke ist einfacher so Wie du siehst es gibt es gibt nur 2 Arten von Zahlen a>ga Faktoren sind sofort da a<ga Faktoren sind nicht da bei a<ga P einfach durch Multiplikation in den Bereich a>ga beamen. Das genau leistet diese Formel. thx und mfg |
|||||||||
06.11.2011, 12:44 | Airblader | Auf diesen Beitrag antworten » | |||||||
Ich habe mir ga mit ausgeben lassen. Das Beispiel, bei welchem ich völlig falsche (und nicht ganzzahlige) Faktoren bekomme, erfüllt a > ga, denn ga ist 0. air |
|||||||||
Anzeige | |||||||||
|
|||||||||
06.11.2011, 12:50 | krzyzape | Auf diesen Beitrag antworten » | |||||||
Hi Air Du mußt in der GA-Gleichung das d von P eingeben , also (b-a) welches ja noch unbekannt ist. MfG |
|||||||||
06.11.2011, 12:59 | Airblader | Auf diesen Beitrag antworten » | |||||||
Habe ich gemacht. Korrigiere es bitte, ob du es so gemeint hast. Ich habe den Code auch gleich ein wenig übersichtlicher gestaltet und vor allem die ätzend komplizierten Berechnungen vereinfacht (es berechnet das selbe, nur eben einfacher): Edit: Aktuellste Version weiter unten. Auf die Eingabe P = 113123029 liefert dein Programm jedenfalls völlig abstruse Werte, es gilt aber dennoch a > ga. air |
|||||||||
06.11.2011, 13:09 | Airblader | Auf diesen Beitrag antworten » | |||||||
Nachtrag: Die Variable 'd' taucht nirgendwo auf, außer am Ende, ist also ständig Null. Die Berechnung der dt (die dreimal auftaucht, jedesmal die selbe Berechnung) ist also noch einfacher:
air |
|||||||||
06.11.2011, 13:17 | krzyzape | Auf diesen Beitrag antworten » | |||||||
Auf die Eingabe P = 113123029 liefert dein Programm jedenfalls völlig abstruse Werte, es gilt aber dennoch a > ga. air[/quote] Du mußt den Zahlenbereich von Q-Basic bedenken. Der ist nicht gerade der Hit. MfG Ps. Ich hab die Nullstellensuche auch unsauber programmiert. Programmieren war noch nie meine Stärke. Cool, danke für die Vereinfachungen Air. |
|||||||||
06.11.2011, 13:26 | Airblader | Auf diesen Beitrag antworten » | |||||||
Dann wird es Zeit, dass du das Programm in C umsetzt. Das sollte doch kein Problem sein, lediglich die Syntax ändert sich ein wenig. Die GoTo-Befehle würde ich einfach durch Funktionen ersetzen (edit: Wobei, C kann goto doch auch, oder? Dann wär's noch einfacher) Hier erstmal meine aktuelle "Säuberung" deines Codes, indem überflüssige Berechnungen entfernt wurden:
Meine Vermutung ist, dass dein Programm irgendetwas Triviales möglichst kompliziert ausführt und daher nach wie vor exponentielle Laufzeit hat. Deine (sowieso nie wirklich komplexen) Rechnungen lassen sich ja offenbar schon auf den ersten Blick enorm vereinfachen. Vielleicht magst du die Idee des Algorithmus ja einfach mal in Worte fassen. air |
|||||||||
06.11.2011, 13:29 | krzyzape | Auf diesen Beitrag antworten » | |||||||
Hi Air d (b-a) ist ja noch unbekannt. Ich hab die Formel ja erst vor 3 Tagen entdeckt. Deshalb ist das ganze etwas chaotisch. Bis jetzt MfG |
|||||||||
06.11.2011, 13:41 | krzyzape | Auf diesen Beitrag antworten » | |||||||
Hi air Ich bin geschockt wie einfach die Berechnung von dt ist. Jetzt geht es nur noch darum Die a<ga in a>ga zu verwandeln. MfG |
|||||||||
06.11.2011, 13:56 | krzyzape | Auf diesen Beitrag antworten » | |||||||
Meine Vermutung ist, dass dein Programm irgendetwas Triviales möglichst kompliziert ausführt und daher nach wie vor exponentielle Laufzeit hat. Deine (sowieso nie wirklich komplexen) Rechnungen lassen sich ja offenbar schon auf den ersten Blick enorm vereinfachen. Vielleicht magst du die Idee des Algorithmus ja einfach mal in Worte fassen. air[/quote] dt=p-y^2 Irgendwann wird bei genug hohem y dt negativ. Das ist die Grenze von Plus zu Minus. Und diesen Punkt habe ich nach der binären Sortiermethode gefunden. Dieses Verfahren ist extrem schnell. Es geht jetzt nur noch darum ein genausoschnelles Verfahren zu entwickeln welches a<ga in a> ga verwandelt. Thx und MfG |
|||||||||
06.11.2011, 14:10 | Interesse | Auf diesen Beitrag antworten » | |||||||
Es wäre verständlicher wenn du deine Idee/Algo. einfach mal beschreiben würdest... Eingabe: ..... (vielleicht auch die Variablen erklären) Schritt_1: .... (Was passiert mit dem eingegebenen? Was passiert mit dem Ergebnis?-Ausgabe oder Weiterverarbeitung?) Schritt_2:.... .... Ausgabe:.... Dein "dt" aus Zeile 12 ist im übrigen immer negativ.... |
|||||||||
06.11.2011, 14:15 | Airblader | Auf diesen Beitrag antworten » | |||||||
Also mit anderen Worten möchtest du zunächst die größte ganze Zahl y finden, für die gilt. Oder, anders gesagt, du möchtest eine ganze Zahl y mit finden. Das geht auch ohne Schleifen viel einfacher mittels , wobei floor() die Abrundungsfunktion ist. Alles klar. Nehmen wir an, wir haben dieses y. Was passiert dann? air |
|||||||||
06.11.2011, 14:25 | krzyzape | Auf diesen Beitrag antworten » | |||||||
Das was mit dem Programm schon die ganze Zeit passiert. Es sagt uns ob P zu den Bereich a< ga oder a> ga gehört. Alle Zahlen a>ga und das sind verdammt viele sind sofort faktorisiert !!! Die verbleibenden a< ga sind nicht direkt faktorisiert. Also mit Muliplikation in den a> Bereich beamen: Nochmal mein Beispiel !!!!!!!!!!! 11*31=341 a ist < ga Ich faktorisiere p mit 3 31*33 a>ga und Bingo 31 gefunden. MfG |
|||||||||
06.11.2011, 14:26 | Airblader | Auf diesen Beitrag antworten » | |||||||
Vergiss doch mal dieses a < ga und a > ga. Wir haben y wie oben gefunden. Was macht dein Algorithmus damit jetzt? Das y ist schließlich keiner der Faktoren, die wir suchen. air |
|||||||||
06.11.2011, 14:30 | galoisseinbruder | Auf diesen Beitrag antworten » | |||||||
Ich hege den Verdacht, dass das Programm in etwas verkomplizierter Form den Faktorisierungsalgorithmus von Fermat ausführen soll.
Das gäber eine Darstellung (mit) und damit |
|||||||||
06.11.2011, 14:33 | Airblader | Auf diesen Beitrag antworten » | |||||||
Volltreffer. air |
|||||||||
06.11.2011, 15:19 | krzyzape | Auf diesen Beitrag antworten » | |||||||
Ja das ist die Methode !!! Jetzt such ich nur noch einen Algorithmus der aus zB( y und dt) mit P multipliziert immer diese netten Quadrate generiert. Danke an Galoiseinbruder |
|||||||||
06.11.2011, 16:51 | Airblader | Auf diesen Beitrag antworten » | |||||||
Ich glaube, du hast nicht verstanden. Der Algorithmus, den du gefunden hast (was sicherlich eine respektable Leistung ist), ist rund 400 Jahre alt und nicht effizient genug, um RSA zu "töten". air |
|||||||||
06.11.2011, 17:22 | René Gruber | Auf diesen Beitrag antworten » | |||||||
Allerdings hat der Algorithmus einen Vorteil: Die im anderen Thread diskutierte Verwendung spezieller Bibliotheken zum Rechnen mit großen Zahlen kann hier weitgehend entfallen: Der Algorithmus ist so ineffizient, dass er für so große Zahlen sowieso keine Verwendung finden kann. P.S.: Noch 158 Minuten... |
|||||||||
07.11.2011, 22:26 | krzyzape | Auf diesen Beitrag antworten » | |||||||
RE: Hier das geforderte Programm Hier das Programm welches alle netten Quadrate (q) generiert. Ein kürzeres wird folgen. Nu ist bei Quadrat (q) = (a+b)/2 !!! Genau d=p-nu^2 Dann haben wir die orginalen - Quadrate -(((b-a)/2)^2) MfG DEFDBL A-Z: DEF SEG = 0: SCREEN 12 CLEAR , , 2000 CLS k = 1 FOR f = 0 TO 10000000000000# a = 31 b = a + 60 p = a * b FOR x = 1 TO p r1 = p - x ^ 2 - k * f IF r1 < 0 OR r1 = 0 THEN GOTO sp NEXT sp: nu = x + f d = (SQR(ABS(p - nu ^ 2))) * 2 pp = (nu * 2 - d) / 2 k = pp FOR x = 1 TO p r1 = p - x ^ 2 - k * f IF r1 < 0 OR r1 = 0 THEN GOTO sq NEXT sq: r1 = ABS(r1) q = ((r1 + k * f - 1) + 1) LOCATE 1, 1: PRINT "f="; f; "a="; a; "b="; b; " P="; p; " (a+b)/2="; nu; " q="; q; " (b-a)="; d LOCATE 30, 1: INPUT ; a7 IF a7 = 1 THEN END CLS NEXT |
|||||||||
07.11.2011, 23:45 | krzyzape | Auf diesen Beitrag antworten » | |||||||
Wenn ich das richtige f meiner letzten Formel zwingend erhalten würde, wäre auch dieser Algorithmus für alle Zahlen geeignet. MfG |
|||||||||
08.11.2011, 09:26 | Airblader | Auf diesen Beitrag antworten » | |||||||
Die Variablen umzubenennen und das Ganze neu zu versuchen, sowie "Hätte, Könnte, Sollte, Wollte" machen den Algorithmus nicht schneller. Es ist für dich an der Zeit, einzusehen, dass Fermat 400 Jahre schneller war als du und der Algorithmus RSA nicht töten wird. Wenn du den Code hier postest, dich zurücklehnst und darauf wartest, dass ihn jemand nutzt, um die Welt(-wirtschaft) zu ihrem Ende zu bringen, ist das deine Entscheidung, aber du wirst viel Zeit damit verschwenden. air |
|||||||||
08.11.2011, 10:23 | René Gruber | Auf diesen Beitrag antworten » | |||||||
Ja, man kann eine ganze Reihe komplizierter bzw. kompliziert erscheinender Algorithmen wegwerfen, wenn denn eines Tages mal der unendlich schnelle Computer erfunden wird (wahrscheinlich vom Erbauer des ersten funktionierenden Perpetuum mobile). An dem Tag wird dann auch dieser Algorithmus hier zu Ehren kommen, ganz sicher. In dem Zusammenhang würde ich doch gern einmal erfahren, wie krzyzape auf diese Zeitschätzung gekommen ist? Vielleicht hat er das ja irgendwo in jenem ellenlangen Thread gesagt, ich hab es aber nicht mitgekriegt. |
|||||||||
08.11.2011, 10:28 | Interesse | Auf diesen Beitrag antworten » | |||||||
Die Abschätzung ist natürlich aus der Luft gegriffen.... und wohl daraus entstanden, dass sein Algo. für sein Beispiel 11*31 topp funktioniert! |
|||||||||
08.11.2011, 13:38 | Airblader | Auf diesen Beitrag antworten » | |||||||
@ René Ja, er sagte inzwischen irgendwo, dass das einfach "erfunden" war. air |
|