Informatiker Board | Berechenbarkeits- und Komplexitätstheorie | Zeitaufwand Primfaktorzerlegung

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Zeitaufwand Primfaktorzerlegung » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 4 Beiträge

eulerscheZahl

Allgemein braucht der Algorithmus Summe(Teiler)-Anzahl(Teiler) modulo-Divisionen

Für N=2^n * (2^n-1) und (2^n-1) als Primzahl sind das 2*n+(2^n-1)-(n+1) = 2^n+n-2 Schritte.
Nach etwas Termumformung (ich hoffe, ich habe mich nicht verrechnet):
$[latex]f(N=2^n*(2^n-1))=\frac{1+\sqrt{1+4\cdot N}}{2}+\log_2(\frac{1+\sqrt{1+4\cdot N}}{2})-2[/latex]$
für die 56 kommt da übrigens 9 raus, nicht 8. Für den letzten Faktor müss von 2-7 die modulo-Operation 6 mal ausgeführt werden.
f(127*128) = 133 ist der nächste Wert der Folge, da 63 nicht prim ist.

Unterm Strich bleibt festzustellen, dass es deutlich bessere Algorithmen zur Faktorisierung gibt.

zteve

Hallo,

Danke für die Antwort.

Hab mir das nohcmal durch den Kopf gehen lassen. Meine Formel log(n+1) + n-2 macht nur bedingt Sinn.

n wäre hier quasi bei 56, die 7 --> 2*2*2*7=56 und 8 * 7 = 56. Also der Primzahlfaktor, der nach den 2ern kommt.

Zusätzliche Bedingung, dass die Formel log(n+1) + n-2 stimmt ist aber dann auch, dass n genau eins weniger ist, als das Produkt der 2er ergibt.

Also Beispiel:
Bei 56 stimmt die formel (8*7 = 56 --> 2*2*2=8 --> 8-1 = 7 --> 8 * (8-1) = 56)
Bei 40 stimmts nicht: (8*5 = 40 ---> 2*2*2 = 8 --> 8-3 = 5 --> 8* (8-3) = 40)

Ich hoffe du versehst, woraus ich hinaus will.

Also die Formel Log(n+1) + (n-2) mit n = der letzte Primfaktor nach den 2er Potenzen gilt nur, wenn sich die Zahl aus 2^x * ((2^x) - 1) zusammensetzen lässt.

eulerscheZahl

Ich gebe dir Recht, dass die Lösung falsch ist.

Zitat:

der maximale Aufwand wäre eher: 1+1+1+1+1+1+... und das maximal log(N+1) + n-2 mal.

was soll n sein?

Das schlechteste Verhalten erreichst du, wenn die zu faktorisierende Zahl eine Primzahl ist. Dann brauchst du in NächsterTeiler N-1 Durchläufe.

zteve

Zeitaufwand Primfaktorzerlegung

Hallo zusammen,

ich habe ein Verständnisproblem mit der Lösung, die wir bekommen haben bezüglich des Zeitaufwands zu folgendem Algorithmus:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

Eingabe N: Natürliche Zahl
Ausgabe PrimFak: Menge der Prim-Faktoren von N 

PrimFak := {}; 
While N>1 do 
  NächsterTeiler (N,T)
  N := N/T Füge T zu PrimFak


Funktion NächsterTeiler (Eingabe: N, Ausgabe:T) 
  T:=2 
  While N mod T != 0 do T:= T+1

Bezüglich des Zeitaufwands ist folgende Lösung angegeben:

Rechenzeitaufwand für Nächster Teiler ist beim ersten Aufruf höchstens N,
beim zweiten Aufruf durch Teilen des Faktors N/T < N/2
beim dritten Aufruf durch weiteres Teilen N/T /T´ < N/2 /2 = N/4
Insgesamt höchstens N* (1 + ½ + ¼ + ..) < N*2 .

Ich meine aber, dass das falsch ist:
Wenn "NächsterTeiler" den Rechenzeitaufwand von N hat, dann gibt es keinen zweiten Aufruf von "NächsterTeiler" da, durch das Teilen dann N/T = 1 herauskommen würde. Das beim 2. Aufruf maximal N/2 Schritte benötigt werden setzt voraus, dass N halbiert wurde, also der 1. Aufruf 1 Schritt und nicht N Schritte gebraucht wurde, sondern der Teiler 2 die Liste halbiert.

Somit würde ich sagen, der maximale Aufwand wäre eher: 1+1+1+1+1+1+... und das maximal log(N+1) + n-2 mal.

Beispiel: anhand 56:
1. Primfaktor 2 (Durchlauf NächsterTeiler 1 Schritt)
2. Primfaktor 2 (Durchlauf NächsterTeiler 1 Schritt)
3. Primfaktor 2 (Durchlauf Nächster Teiler 1 Schritt)
4. Primfaktor 7 (Durchlauf Nächster Teiler 5 Schritte)

Macht insgesamt: 3 + 5 = 8 Schritte bzw. log(8) + 7-2 = 8

Habe ich hier etwas übersehen, oder wie soll ich nun diese Musterlösung interpretieren?