0 Daumen
632 Aufrufe

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"


Avatar von

Das Programm sollte noch einige Erweiterungen erfahren:

1) die Variable o sollte auch mit o = o^2 durchgerechnet werden - in der While-Schleife:

  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:

2) Ich habe noch mit einer anderen Version gearbeitet, die aus m und n ein anderes o generiert. Dies führte zu zusätzlichen Faktorisierungen.

1 Antwort

0 Daumen

Ja, schein so (auf den ersten Blick; habe nicht genug Zeit für komplette Analyse).

Hinweis:

Wenn Du bereits den 1. Teiler hast, reicht die Modulo-Funktion -> wenn 0,

dann 2.Teiler = Eingabe / Teiler1 fertig, d.h. es braucht nicht noch eine langsame if + ggT berechnet werden.

Für große Zahlen scheint es sehr langsam zu werden...

Für richtig große Zahlen ist der Carmichael-Zahl-Faktorisierer  (manchmal auch für Typ C geeignet)

http://www.lamprechts.de/gerd/php/Carmichael-Zahl-Faktorisierer.php

schneller.

Wie groß können denn Deine Zahlen werden (64 Bit Integer?)

Teste mal:

18446744176328438063 (nur Typ F = Fermat)

4048239384520320198159152895702691412734136987483292987079034606881 (auch für Typ C) 

Avatar von 5,7 k

Danke für die schnelle Antwort.

Ich habe inzwischen irgendwo gelesen, dass Mathematica extrem schnell für ganz große Zahlen zum Faktorisieren ist. Werde mir das Programm kaufen.

lg

Peter

http://www.lamprechts.de/gerd/php/RechnerMitUmkehrfunktion.php ,

WolframAlpha.com , und http://www.alpertron.com.ar/ECM.HTM  

können auch große Zahlen (über 65 Stellen)  kostenlos faktorisieren.

Wozu willst Du über 380 Euro ausgeben?

Brauchst Du über 200 Stellen?

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community