Diskussion:Faktorisierungsverfahren

Alte Diskussion

Ich habe gerade irgendwo gelesen, dass man in Diskussion begründen sollte, wenn man was löscht. Deshalb: Ich habe die Beschreibung der Probedivision gelöscht, und will demnächst eine ausführlichere eigene Seite diesem Thema widmen. Die eine Zeile, die bisher da war, wäre aber auf einer einzelnen Seite nicht sinnvoll.--Berni 18:54, 13. Dez 2003 (CET)

Ich weiß nicht, wieviel es zur Probedivision zu schreiben gibt, deshalb mach einfach mal eine Seite dazu und verlinke sie von diesem Artikel. --SirJective 14:39, 14. Dez 2003 (CET)

Ein bisschen was gibt es, ich bin aber noch am Sammeln. Sobald ich genug zusammen habe und die Zeit finde pack ich es rein.--Berni 17:27, 14. Dez 2003 (CET)

Außerdem fehlt in der Wiki eine Erklärung der Existenz und Eindeutigkeit der Primfaktorzerlegung in den ganzen Zahlen und gewissen weiteren Ringen, sowie eine Beschreibung von zusammengesetzen Zahlen. Die Artikel Primfaktorzerlegung (z.Z. ein redirect) wäre ein geeigneter Kandidat. --SirJective 14:39, 14. Dez 2003 (CET)

Ist mir auch schon aufgefallen. Ich werde mich aber vorerst auf die Faktorisierungsverfahren beschränken; da gibt es schon genug zu tun :-) --Berni 17:27, 14. Dez 2003 (CET)

Mir ist gerade aufgefallen, dass Primfaktor auf diese Seite umgelenkt wird. Sollte das nicht besser auf Primzahl zeigen? --Berni 18:47, 16. Dez 2003 (CET)

Eher auf die (noch zu schreibende) Seite Primfaktorzerlegung. Biege das mal um... --SirJective 14:18, 17. Dez 2003 (CET)

Eine Laufzeitangabe zum Vergleich der Algorithmen wäre sicher eine gute Erweiterung. 85.181.9.243 01:09, 19. Okt. 2007 (CEST)

Ist die der Probedivision eigentlich O(n*ln(n)) ?

Nein, O(Wurzel(n)) wenn n die zu zerlegende Zahl ist (Es wird ja im wesentlichen für jede Zahl zwischen 2 und sqrt(n) geprüft ob sie n teilt). --Khong 18:47, 29. Jan. 2008 (CET)

Eine Idee

Ich weiß nicht, ob es hier hin passt, aber ich habe eine Idee. Folgendes: Ich habe mich mit Stieltjes Beweis beschäftigt, um zu sehen, welche Primzahle sich durch Stieltjes Beweis erzeugen lassen. Dabei ist mir folgender gedanke gekommen: Statt kosequent alle Möglichkeiten auszuprobieren nach dem Motto, welche Primzahl bekomme ich mit der Formel (3*5)+(2*7), zerlege ich jede Primzahl in zwei Zahlen, z.B. 13 = 6+7 = 5+8 = 4+9 = 3+10 = .. , und verwende davon die Form die am besten in das Schema reinpasst. In diesem Fall 13 = 3 + 10 = (3)+(2*5). Ich überspringe ein paar Gedankengänge, und komme auf den Punkt: Zwei Dinge sind mir aufgefallen: 1. Primzahlen und Nichtprimzahlen unterscheiden sich in einem Punkt:

31	35
15+16	17+18
14+17	16+19
13+18	15+20 ggT(15,20)=5
12+19	14+21 ggT(14,21)=7
11+20	13+22
10+21	12+23
9+22	11+24
8+23	10+25 ggt(10,25)=5
7+24	9+26
6+25	8+27
5+26	7+28 ggT(7,28)=7
4+27	6+29
3+28	5+30 ggT(5,30)=5
2+29	4+31
1+30	3+32

Während bei der zuammengesetzten Zahl ggT's mit größer 1 vorkommen, sind die jeweiligen Bestandteile der Primzahl Teilerfremd. Ich vermute, das dies auf alle Primzahlen zutrifft, und sich mit Stieltjes beweisen läßt.

2. Die ggT's sind Teiler der zusammengesezten Zahl. Man hätte hier also eine mögliche Primfaktorzerlegung.

Gibt es für diese beiden Punkte (Primzahltest und Faktorzerlegung) schon einen Namen? Das wäre sehr praktisch. Gibt es Einwände gegen meine Folgerungen? --Arbol01 20:07, 20. Aug 2004 (CEST)

Antwort (anonym)

Mit der Zelegung von p in p = d*a + d*b gilt p = d * (a+b). Daraus folgt: Wenn p eine Primzahl ist, muss d=1 sein und damit sind alle Bestandteile teilerfremd.

Wenn p zusammengesetzt ist und einer der Bestandteile einen Teiler d von p hat, muss dieser auch im zweiten Bestandteil enthalten sein, sonst wäre die Summe kein Vielfaches von d und damit unmöglich p.

Zur Primfaktorzerlegung: Diese Variante scheint nicht schneller zu sein, wie Probedivision durch Zahlen von 2 bis Wurzel(p).--81.209.204.136 16:42, 8. Aug 2005 (CEST)

Kennnt jemand dieses PPS Verfahren? Ich behaupte mal das ist kein funktionierendes Verfahren, siehe mein Eitrag bei http://de.wikipedia.org/wiki/PPS-Methode. Ich würde den Link löschen.

Revert Berechnung des größten gemeinsamen Teilers - Bitte um Erklärung

Was genau steht denn in der Quelle? Ich werde mir das Buch bei nächster Gegelenheit mal in der Bibliothen anschauen. Unabhängig davon ist die Aussage, wie sie jetzt im Artikel steht, falsch. m ist i.d.R. kein Teiler von n, damit ist n/m echt rational. Eine Probedivision macht bei rationalen Zahlen aber keinen Sinn - wie soll denn "Primzahl p ist teiler von n/m" definiert sein?

Als zweiten Punkt möchte ich noch anmerken dass das Verfahren allgemeiner ist als hier vorgestellt: Die Faktoren von m müssen nicht alle aus einem bestimmten Intervall stammen. Vielmehr kann mit dem Verfahren getestet werden, ob eine Zahl n irgendeinen Teiler aus einer bestimmten Menge M von Primzahlen hat, indem m gleich dem Produkt aller Zahlen in M gesetzt wird. Ist der ggt von n und m dann nicht 1, so gibt es einen Teiler. --Khong 15:26, 31. Jan. 2008 (CET)

Erklärung erfolgt am Wochenende. Ich gebe zu, dass die Vorgehensweise schlecht beschrieben ist. --Stefan Birkner 08:00, 1. Feb. 2008 (CET)

Gibts hier etwas neues? Ich würde ungerne den aktuellen Stand stehen lassen, da er stellenweise leider falsch ist. --Khong 11:35, 1. Mär. 2008 (CET)

Sorry, ich hatte noch keine Zeit. Stell einfach wieder einen Stand her, den du für richtig hältst. Sinnvollerweise sollte man den Abschnitt wohl in den Artikel zur Probedivision verschieben, da es eher eine Ergänzung jenes Verfahrens als ein eigenständiges Faktorisierungsverfahren ist. --Stefan Birkner 12:01, 1. Mär. 2008 (CET)

SQUFOF

Das Faktorisierungsverfahren Methode der Klassengruppen geht zurück auf den Algorithmus CLASNO von Daniel Shanks in Class number, a theory of factorization, and genera. Proc Sympos. Pure Math. 20 (1971) S. 415-440. Es beruht auf der Struktur der Idealklassengruppe quadratischer Zahlkörper mit negativer Diskriminante. Der Artikel erwähnt das Verfahren SQUFOF nicht, und Shanks hat dieses Verfahren nie publiziert, allerdings in einem Abstract in den Notices AMS 22 (1975) angekündigt.

Der Shankssche Artikel regte eine relativ leistungsfähige Implementierung (ca. 1985) von A. O. L. Atkin und Neil William Rickert unter dem Namen SPAR (nach Shanks, Pollard, Atkin und Rickert) an,außerdem die erwähnten Varianten von Seysen und Lenstra/Schnorr.

SQUFOF verwendet die Reduktionstheorie binärer quadratischer Formen mit positiver Diskriminante und hat enge Beziehungen zur Kettenbruchmethode. Es ist daher ein eigenständiger Algorithmus, sowohl in seiner Entstehungsgeschichte, in seiner theoretischen Begründung als auch in seinen Anwendungsbesonderheiten. -- TeesJ 07:37, 11. Dez. 2010 (CET)

Sorry, ich habe gedacht es handelt sich um den gleichen Algorithmus. Allerdings frage ich mich ob der Algorithmus bedeutend genug ist um erwähnt zu werden, wenn er weder publiziert wurde noch sonst größere Beachtung gefunden hat. Auch die abgeleiteten Algorithmen sind mir unbekannt. Aber lass ruhig so, schade ja nichts.-- ThiloHarich 11:18, 11. Dez. 2010 (CET)

Der Shor-Algorithmus "benötigt" einen "Quantencomputer"? Wirklich?

Das halte ich für ein Gerücht! Allerdings läuft er vermutlich nur auf einem "Quantencomputer" in Polynomialzeit. Jeder "klassische Rechner" kann einen "Quantencomputer" simulieren, mit exponentiellem Zeitverlust und Speicherverbrauch. Die vollständige Simulation eines "Quantencomputers" ist aber vermutlich gar nicht erforderlich, um den Shor-Algorithmus auszuführen. Nachdem die "Quanten-Fouriertransformation" eine Einschränkung der diskreten Fouriertransformation ist, dürfte man hier mit den "üblichen Algorithmen", etwa der "schnellen Fouriertransformation" arbeiten können. Aber vermutlich ist man auch dann oberhalb der Polynomialzeit. 79.245.185.70 00:29, 12. Dez. 2015 (CET)

P? NP?

Zwar ist bekannt, dass das Problem (in seiner Entscheidungsvariante) in der Klasse NP liegt, aber unbekannt, ob es bereits in polynomieller Zeit lösbar ist. Gilt das auch unter der Annahme P != NP, oder liegt das nur allgemein daran, dass halt immer noch nicht ganz ausgeschlossen ist, dass ganz NP in P liegt? --138.245.1.1 19:18, 16. Jan. 2020 (CET)