Peter Rasinger, Ferlach, Österreich
ich beschäftige mich mit der Faktorisierung von Produkten (Kurz "Prod") der Form a = P1 * P2 (Primzahl 1 * Primzahl 2) -> P1>=3, P2>=3, P1<>P2, a ist somit immer ungerade.
Ich suche dabei nach Lösungen der Polynomform (kurz "Polynom") x2 - y2 = ( x + y ) * ( x - y ) = z, wobei x2 > z < ( x + 2 )2 sein soll, in Ausnahmefällen ist x2 = z, dies gilt nur dann, wenn f ein Faktor von z ist.
Um dies zu Erreichen, multipliziere ich a mit einem Faktor f -> z = a * f.
Ich weiss, dass zum Beispiel eine Multiplikation mit 8, also f = 8, öfters zu solchen Polynomen führt. Ebenfalls ist mir bekannt, dass eine Suche nach einem passenden Multiplikator irgendwann ins Unendliche führt.
Der folgende Algorithmus führt zwar auch vermehrt zu einer Lösung, muss jedoch nicht immer zu einer Lösung führen, daher kein Anspruch auf Vollständigkeit.
Definitionen:
ggT(b,c) (=größter gemeinsamer Teiler der zwei Zahlen b und c) -> Beispiel: ggT(24,30) = 6
ZoF2(d) (=Zahl ohne Faktor 2) -> Beispiele: ZoF2(24) = 3; ZoF2(1024) = 1; ZoF2(30)=15; ZoF2(33)=33
Q(e) (=Quadrat) -> Beispiele: Q(9)=81; Q(253)=64009; Q(1003)=1006009
W(f) (=Wurzel) -> Beispiele: W(49)=7, W(50)=7,07106781...; W(1000)=31,622776...
Gz(h) (=Ganzzahl), wird immer abgerundet -> Beispiele: Gz(2,8)=2; Gz(3)=3; Gz(W(500))=22
Zu diesem Algorithmus habe ich folgende Frage:
Ist dieser Algorithmus eine Abwandlung der Faktorisierungsmethode von Fermat?
// Programm zum Finden von Faktoren
While true:
label jump
Input z
if z <= 1 then stop
if Gz(z) <> z then Fehlermeldung: "Keine Ganzzahl"; stop
if ZoF2(z) <> z then Fehlermeldung: "Zahl ist durch 2 teilbar"; stop
b = Gz(W(z)) // Ganzahl(Wurzel(z))
if Q(b) = z then Fehlermeldung: "Zahl ist eine Quadratzahl"; stop
b = b + 1
m = Q(b) - z
m = Q(m)
if Gz(m/2) <> m/2 then m = m - 1 // Zahl ist nicht durch 2 teilbar, erzeuge gerade Zahl
n = Q(z)
n = n - 1
o = ggT(m,n)
o = ZoF2(o) // erzeuge ungerade Zahl - auch: While Gz(o/2) = o/2: o = o / 2; Wend
if o = 1 then o = o * 4 // ggT(m,n) ist eine Zahl zur Basis 2
While o < z:
q = z * o
r = Gz(W(q))
if W(q)=r then Meldung: "Teiler ist:" ggT(r,z); goto label jump
s = r
While s <= r + 1: // s gerade und ungerade
s = s + 1
t = Q(s) - q
u = W(u)
if Gz(u)=u then Meldung: "Teiler ist:" ggT(z,s-u); goto label jump // 2.Teiler gleich s+u
Wend
v = o / 2
if Gz(v) <> v then o = o * 2 // hier eventuell if v \ 2 <> 0 then ... einsetzen
o = o * 2
Wend
Meldung "Es wurde kein Teiler gefunden"
Wend
Beispiel mit Zahlen:
z = 37 * 197 = 7289
b = W(z) = 85,37...
b = Gz(W(z)) = 85 // Ganzahl(Wurzel(z))
b = b + 1 = 86
m = Q(b) - z = 87 * 87 - 7289 = 107
m = Q(m) = 107 * 107 = 11449
if Gz(m/2) <> m/2 then m = m - 1; if 5724 <> 5724,5 then m = 11449 - 1 = 11448 // erzeuge gerade Zahl
n = Q(z) = 7289 * 7289 = 53129521
n = n - 1 = 53129521 - 1 = 53129520
o = ggT(m,n) = ggT(1148,53129520) = 432
o = ZoF2(o) = 432 / 16 = 27 // erzeuge ungerade Zahl - auch: While Gz(o/2) = o/2: o = o / 2; Wend
if o = 1 then o = o * 4 // ggT(m,n) ist eine Zahl zur Basis 2
While o < z: // o = 27, z = 7289...; bis zu o = 1728
q = z * o = 7289 * 27 = 196803...; ab o = 1728 ... q = 12595392
r = Gz(W(q)); ab o = 1728 ...; r=Gz(W(12595392)) = 3548
if W(q)=r then Meldung: "Teiler ist:" ggT(r,z); goto label jump
s = r; ab o = 1728 ...;s = 3548
While s <= r + 1:; 3548 <= 3548 + 1 // s gerade und ungerade
s = s + 1; ab o = 1728 ...; s = 3548 + 1 = 3549
t = Q(s) - q; ab o = 1728 ...; t = 12595401 - 12595392 = 9
u = W(u); ab o = 1728 ...; u = W(9) = 3
if Gz(u)=u then Meldung: "Teiler ist:" ggT(z,s-u); goto label jump // 2.Teiler gleich s+u
if Gz(u)=u ...;; ab o = 1728 ...; if Gz(3)=3 then Meldung: "Teiler ist" ggT(7289,3549-3)=197
// 2.Teiler gleich s+u; ggT(7289,3549+3)=37
Wend
v = o / 2 = 27 / 2
if Gz(v) <> v then o = o * 2; Gz(13,5) <> 13,5 = 13 <> 13,5 then o = 27 * 2 = 54
o = o * 2; o = 54 * 2 = 108; ....; o = 864 * 2 = 1728
Wend
Meldung "Es wurde kein Teiler gefunden"
