Faktorisierung mittels Probedivision --> Vermutung

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Faktorisierung mittels Probedivision --> Vermutung

Beitrag von oren78 »

hallöchen miteinander,

ich hab mich ein bisschen der Probedivisionsmethode beschäftigt und hab eine Vermutung aufgestellt die ich jedoch nicht beweisen kann...
wir haben ein gegebenes zusammengesetztes n das wir faktorisieren sollen...

wir fangen zunächst an mit: \(u\; =\; upperbound\;=\;\lfloor\sqrt\;n\rfloor\)
es muß also einen primteiler p geben mit: \(p\; \le\;u\) der ein ko-faktor von n ist...

nun partionieren wir das intervall: \(I\; =\; [1\;; u]\) in zwei gleichgroße teilintervalle...

\(A\;=\; [2\;;\;m\; =\; middle\; =\; \lfloor(u\;-\;2)/2\rfloor]\)
\(B\;=[m\;+1\;;\;u\;-\;1]\)

laut der Annäherungsformel von Gauß existieren: \(\frac {x}{ln(x)}\) Primzahlen in einem Intervall mit der Schranke x
also gibt es ingesammt ca. \(\frac {u}{ln(u)}}\) Primzahlen die als Primteiler in Frage kommen...meine Vermutung ist nun das für ein hinreichend großes n die Wahrscheinlichkeit stark sinkt, das sich die Primteiler im Intervall B befinden können, wenn n aus mindestens 3 Primteiler zusammengesetzt ist, sodass insgesamt deutlich wenige Überprüfungen benötigt werden um ein passendes p zu finden...

wie könnte man so eine vermutung beweisen..?
Zuletzt geändert von oren78 am 22. Feb 2009 11:33, insgesamt 1-mal geändert.
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Benutzeravatar
Tristan
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 22. Okt 2008 20:32

Re: Faktorisierung mittels Probedivision --> Vermutung

Beitrag von Tristan »

laut der Annäherungsformel von Gauß existieren: \(\frac {x}{ln(x)}\) Primzahlen in einem Intervall mit der Schranke \(x\)
Die Formel gilt nur asymptotisch. Ist ja auch nur ne Näherungsformel.
meine Vermutung ist nun das für ein hinreichend großes n die Wahrscheinlichkeit stark sinkt, das sich die Primteiler im Intervall A befinden können
Was bedeutet denn "stark sinkt"? Was bringt dich denn auf die Vermutung?

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: Faktorisierung mittels Probedivision --> Vermutung

Beitrag von oren78 »

Tristan hat geschrieben:Was bedeutet denn "stark sinkt"? Was bringt dich denn auf die Vermutung?
habe viele zahlen durchgetestet deren zusammensetzung mindestens aus 3 primteiler besteht, bei allen hatte ich diese erkenntnis...
als beispiel wären da die ersten 36 Carmichael Zahlen...

übrigens, hatte ich oben aus versehen Intervall A angegeben, B sollte eigentlich gemeint sein, habs korrigiert 8)

Edit: also noch mal klare formulierung der Vermutung: mit größer werdenden n steigt die Wahrscheinlichkeit das
sich der Primteiler p im Intervall A befinden muss, sodass man sich die überprüfungen nach der Suche der Primteiler
im Intervall B sparen kann...
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Benutzeravatar
blowfish
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 241
Registriert: 18. Okt 2006 16:00

Re: Faktorisierung mittels Probedivision --> Vermutung

Beitrag von blowfish »

wenn du davon ausgehst, dass die zahl aus 3 primteilern zusammengesetzt ist, muss für einen primteiler p gelten
\(p \leq \lfloor \sqrt[3]{n} \rfloor \leq \frac{\sqrt{n}}{2}\)

Wenn ich das also richtig sehe, hast du die Schranke für p nur etwas höher vermutet, als sie eigentlich ist.
Ein Hemd ist Einstellungssache!

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: Faktorisierung mittels Probedivision --> Vermutung

Beitrag von oren78 »

blowfish hat geschrieben:wenn du davon ausgehst, dass die zahl aus 3 primteilern zusammengesetzt ist, muss für einen primteiler p gelten
\(p \leq \lfloor \sqrt[3]{n} \rfloor \leq \frac{\sqrt{n}}{2}\)

Wenn ich das also richtig sehe, hast du die Schranke für p nur etwas höher vermutet, als sie eigentlich ist.
hmm...höhere Schranke? naja, also ich wollte nur beweisen das der primteiler wie du es in der schranke gezeigt hast darin liegen müsste,
die schranke bzw. der Intervall hierfür ist eigentlich nicht höher (besser gesagt breiter) geworden sondern eher schmaler, eben die hälfte
des ursprünglichen Intervalls...

ich wüsste nur zu gern, wie ich das formal zeigen könnte?
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Benutzeravatar
marlic
Computerversteher
Computerversteher
Beiträge: 365
Registriert: 5. Okt 2006 11:09
Wohnort: Dietesheim

Re: Faktorisierung mittels Probedivision --> Vermutung

Beitrag von marlic »

Also man kann sagen, dass für einen Primteiler gilt: \(p \le n^{\frac 1 3}\)

Aber man kann auch sagen, dass für alle Primteiler gilt: \(p \ge 2\) also bei mindestens drei Primteilern:

Für alle Primteiler \(p \le \frac n 4\)

Ich denke so eine Schranke wolltest du haben, oder?

EDIT: Ich glaube nicht - tut mir leid, dass ich quatsch rede ;)

Wieso denkst du eigentlich, dass man weniger überprüfungen braucht, nur weil es da weniger Primteiler gibt?
Oder meinst du eher, dass es sich da nicht zu suchen lohnt?

EDIT: Jetzt hab ichs doch.

Also: Der kleinste Primteiler ist auf jeden Fall bei dir, wie blowfish schon gesagt hat, kleiner der dritten wurzel aus n.

Jetzt gilt aber für \(n \ge 64: \frac {\sqrt{n}} 2 \le n^{\frac 1 3}\)

Folglich findest du den kleinsten Primteiler ab 64 nie mehr im Intervall B.
(Und den sucht man ja für gewöhnlich).

Allerdings ist das keine tolle Erkenntnis, denn wie du siehst, ist die dritte Wurzel ohnehin schon eine bessere Schranke als die hälfte der quadratwurzel.
"Copy & Passed"

Wahlspruch der Plagiatoren

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: Faktorisierung mittels Probedivision --> Vermutung

Beitrag von oren78 »

marlic hat geschrieben:Wieso denkst du eigentlich, dass man weniger überprüfungen braucht, nur weil es da weniger Primteiler gibt?
Oder meinst du eher, dass es sich da nicht zu suchen lohnt?
eher das zweitere, die Wahrscheinlichkeit da einen Primteiler zu finder wird immer geringer...warum das aber so ist, würde ich auch gern verstehen 8)
marlic hat geschrieben: Also: Der kleinste Primteiler ist auf jeden Fall bei dir, wie blowfish schon gesagt hat, kleiner der dritten wurzel aus n.

Jetzt gilt aber für \(n \ge 64: \frac {\sqrt{n}} 2 \le n^{\frac 1 3}\)

Folglich findest du den kleinsten Primteiler ab 64 nie mehr im Intervall B.
(Und den sucht man ja für gewöhnlich).
Michi, woher kommt die 64 genau her :?:
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: Faktorisierung mittels Probedivision --> Vermutung

Beitrag von bruse »

Er hat sich überlegt, wann beide Terme gleich sind. Allerdings stimmt die Aussage nicht, wie das Gegenbeispiel 729 (oder Nachdenken über das Steigungsverhalten von zweiter und dritter Wurzel) zeigen. Dreht man das Größerzeichen um, ists richtig und zeigt auch die Vermutung. Allerdings ist die Ausgangstheorie nicht wirklich brauchbar, denn: Wissen wir, dass die zu faktorisierende Zahl aus mindestens drei Primfaktoren besteht, könnne wir gleich unterhalb der dritten Wurzel suchen und brauchen keine gröbere Schranke.
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

Benutzeravatar
marlic
Computerversteher
Computerversteher
Beiträge: 365
Registriert: 5. Okt 2006 11:09
Wohnort: Dietesheim

Re: Faktorisierung mittels Probedivision --> Vermutung

Beitrag von marlic »

Jo, hab ich ja auch gesagt ;)
Hatte mich nur vertippt. \ge oder \le - ist doch fast das selbe.
"Copy & Passed"

Wahlspruch der Plagiatoren

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: Faktorisierung mittels Probedivision --> Vermutung

Beitrag von oren78 »

hmmm...ok :wink:

aber jetzt mal abgesehen von dem formalen Beweis der mir fehlt, wäre meine Vermutung bzgl. der Existenz des Primteilers \(p_1\) in der Menge A überhaupt ansatzweise richtig?
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Benutzeravatar
blowfish
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 241
Registriert: 18. Okt 2006 16:00

Re: Faktorisierung mittels Probedivision --> Vermutung

Beitrag von blowfish »

wir haben doch grad bewiesen, dass die aussage für n größer als 64 immer wahr ist, allerdings nutzlos.
Ein Hemd ist Einstellungssache!

Antworten

Zurück zu „Archiv“