Hier das geforderte Programm

Neue Frage »

krzyzape Auf diesen Beitrag antworten »
Hier das geforderte Programm
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



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 smile

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 Hammer

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
Airblader Auf diesen Beitrag antworten »

Ich habe jetzt ein P eingegeben (ich verrate dir nicht, welches!). Die Ausgabe deines Programms:

Zitat:
(a+b)/2 = y = 144 dt=-25 b-a = 10


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
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
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
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
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
 
 
krzyzape Auf diesen Beitrag antworten »

Zitat:
Original von Airblader
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


Hi Air

Du mußt in der GA-Gleichung das d von P eingeben , also (b-a) welches ja noch unbekannt ist.

MfG
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
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:

code:
1:
dt = P - y^2


air
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.
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:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
DEFDBL A-Z:
DEF SEG = 0: SCREEN 12
CLEAR , , 2000
CLS

INPUT ; "Bitte P eingeben"; P
IF P = 0 OR P = 1 THEN END
y = (P - 1) / 2
s = y

start:
dt = P - y^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^2
IF dt < 0 or dt=0 THEN GOTO runter
IF dt > 0 THEN GOTO weiter

schluss:
CLS
d = SQR(ABS(dt)) * 2
ga = INT(((d / 2 - 1) ^ 2) / 2)
LOCATE zz + 1, 1: PRINT P; " = "; (y-d/2); " * "; (y+d/2); ", ga = "; ga;
END

runter:
IF tt > 5 THEN GOTO schluss
tt = tt + 1
y = y - 1
dt = P - y^2

IF dt < 0 or dt=0 THEN GOTO runter
IF dt > 0 THEN GOTO weiter


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
krzyzape Auf diesen Beitrag antworten »

Zitat:
Original von Airblader
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:

code:
1:
dt = P - y^2


air


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
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
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
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....
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
krzyzape Auf diesen Beitrag antworten »

Zitat:
Original von Airblader
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


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
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
galoisseinbruder Auf diesen Beitrag antworten »

Ich hege den Verdacht, dass das Programm in etwas verkomplizierter Form den Faktorisierungsalgorithmus von Fermat ausführen soll.

Zitat:
Original von krzyzape

Wenn dt dann ein negatives Quatrat ist Bingo.
.
Das gäber eine Darstellung (mit) und damit
Airblader Auf diesen Beitrag antworten »

Volltreffer.

air
krzyzape Auf diesen Beitrag antworten »

Zitat:
Original von Airblader
Volltreffer.

air


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
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
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. smile


P.S.: Noch 158 Minuten...
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
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
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
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. Augenzwinkern

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. verwirrt
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!
Airblader Auf diesen Beitrag antworten »

@ René

Ja, er sagte inzwischen irgendwo, dass das einfach "erfunden" war.

air
Neue Frage »
Antworten »



Verwandte Themen