Office: Fermats Faktorisierungsalgorithmus

Hallo!
Ich habe ein/zwei Problem mit der Implementierung eines Algorithmus.

Dieser Algorithmus soll das Produkt N zweier Primzahlen p und q wieder in die Ausgangsfaktoren (also p und q) zerlegen.

Dafür wird die Wurzel aus dem Produkt gezogen und auf die nächste ganze Zahl aufgerundet. Diese Zahl heißt bspw. a.
Bis hierhin ist ja alles klar.

Nun Quadriert man a zieht davon N ab und schaut ob das eine Quadratzahl ist. Wenn nicht dann nimmt man (a+1)^2-N und immer so weiter, bis man die Quadratzahl gefunden hat.

Hier ist mein erstes Problem:
Ich würde gerne Excel solange rechnen lassen, bis er diese Quadratzahl gefunden hat, sprich bis

=WENN(REST(WURZEL($G16);1)=0;WAHR; FALSCH)
$G16=REST(($B$7+$H16)^2;$B$2)
B7=a
H16=1,2,3,4...
B2=N

wahr ist.

Wie sage ich Excel, dass es, wenn die Bedingung wahr auftritt, aufhören soll? Ist das mit dem Formeleditor eigentlich möglich?

Mein zweites Problem ist, dass mein Algorithmus für Zahlen wie N=1649 oder N=487633 korrekt arbeitet und mir die Lösungen für p und q liefert.
Gebe ich aber für N=6 ein, habe ich p=2 und q=6... was ja eindeutig nicht 6 sonder 12 ist...
Weiß jemand wo mein Fehler stecken köntne und warum es nur bei manchen Zahlen funktioniert, und bei anderen nicht?

Danke
Bradrulck

 

Hallo!

Die Matrixformel in B4 sollte dein Problem der Abbruchbedingung lösen:

	A	B
1	N	1649
2	a	41
3
4	y	40
5	x	57
6
7	p	17
8	q	97

Zelle	Formel
B2	=AUFRUNDEN(WURZEL(B1);)
B4	{=MIN(WENN(REST(WURZEL((B2+ZEILE(1:999)-1)^2-B1);1)=0;WURZEL((B2+ZEILE(1:999)-1)^2-B1)))}
B5	=WURZEL(B4^2+B1)
B7	=B5-B4
B8	=B4+B5

<table><tr><td>Achtung, Matrixformel enthalten!</td></tr><tr><td><span>Die geschweiften Klammern{} werden </span><span>nicht</span><span> eingegeben.</span></td></tr><tr><td><span>Verlassen Sie den Zelleneditor mit </span><span>Strg+Shift + Enter</span><span>, statt Enter alleine.</span></td></tr></table>[/parsehtml]

Allerdings hast du recht: Bei N=6 rechnet der Algorithmus falsch. Er scheint sogar in allen Fällen falsch zu rechnen, wenn N gerade ist. Da man aber weiß, dass bei geradem N einer der beiden Primfaktoren die 2 sein muss, ist dieses Manko wohl zu verkraften...

 

Super, Danke es funktioniert!

Was mich jetzt noch interessieren würde, wäre was deine Formel genau bewirkt, bzw. was sie anders macht als meine?

Danke,
Bradrulck

 

Hallo!

Nun ja, letztenendes errechnet meine Formel in B4 denselben Wert wie deine Formel in B10, nur eben auf einem etwas "direkteren" Weg, der ohne die von dir angelegte Hilfstabelle auskommt.
Dein Werk rechnet ja schließlich auch richtig, wenn man mal die 2 als Primfaktor ausschließt, da der Algorithmus hierfür wohl nicht geeignet ist.
Also wäre es ja schlimm, wenn meine Formel auf ein anderes Ergebnis käme, welches dann ja definitiv falsch wäre!