Faktorisierung mittels Probedivision --> Vermutung

[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..?

[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?

[oren78]

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

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...

[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.

[oren78]

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?

[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.

[oren78]

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

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

[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.

[marlic]

Jo, hab ich ja auch gesagt
Hatte mich nur vertippt. \ge oder \le - ist doch fast das selbe.

[oren78]

hmmm...ok

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?

[blowfish]

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