Gaußklammer / AKS Algorithmus

Neue Frage »

uffembetze Auf diesen Beitrag antworten »
Gaußklammer / AKS Algorithmus
Hallo zusammen,

ich lese gerade ein Paper über den AKS Primzahltest, und kann eine Stelle nicht ganz nochvollziehen. Damit ihr euch das Paper jetzt nicht angucken müsst, gebe ich mal die wesentlichen Informationen.

Gegeben ist:



Daraus ergibt sich laut Paper:



Was ich einsehe ist, dass natürlich



gilt. Aber die "echte" Ungleichheit bekomme ich nicht hin. Und es ist wesentlich, dass dort die echte Ungleichheit steht.

Vielleicht hat sich ja schon jemand mit dem Thema beschäftigt, und ich überseh vielleicht nur eine zusätliche Information.

Gruß,
uffembetze
klarsoweit Auf diesen Beitrag antworten »
RE: Gaußklammer / AKS Algorithmus
Habe dein Problem nicht so ganz verstanden.

Also allgemein gilt: wenn a > b und c > 0, dann ist a*c > b*c
Airblader Auf diesen Beitrag antworten »

@klarsoweit
Die Multiplikation mit lg n ist nicht das Problem. Aber man kann eine Ungleichung mit echter Ungleichheit nicht ohne Weiteres mit der Gaußklammer versehen:



bzw. allgemein



Denn 3 > 3 stimmt sicherlich nicht, obwohl 3,1 > 3 wohl eindeutig richtig ist Augenzwinkern

@uffembetze

Ist t denn als 'kleinstmögliches' t mit dieser Eigenschaft definiert?
Wenn nicht, ist die Frage ja ziemlich trivial.

air
uffembetze Auf diesen Beitrag antworten »
RE: Gaußklammer / AKS Algorithmus
Zitat:
Original von klarsoweit
Habe dein Problem nicht so ganz verstanden.

Also allgemein gilt: wenn a > b und c > 0, dann ist a*c > b*c


Mit deinen Worten ausgedrückt ist mein Problem, dass aus nicht folgt.

Das wird in dem Paper aber so gefolgert. Ich hatte gehofft, dass vielleicht noch jemand das Paper gelesen hat, da es ja recht berühmt ist.

Ich bin aber in den letzten Minuten einer Lösung deutlich näher gekommen. Da ich bisher tatsächlich eine zusätzliche Information noch nicht genutzt habe. Wenn ich die Lösung entgültig habe, schreibe ich sie hier. Für den Fall, dass nochmal jemand an der Stelle hängen bleibt..
klarsoweit Auf diesen Beitrag antworten »
RE: Gaußklammer / AKS Algorithmus
Zitat:
Original von uffembetze
Mit deinen Worten ausgedrückt ist mein Problem, dass aus nicht folgt.

Ach herje, dieses "komische" Zeichen sollte die Gaußklammer sein. OK, man muß auch den Titel lesen. Hammer
uffembetze Auf diesen Beitrag antworten »

Zitat:
Original von Airblader

Ist t denn als 'kleinstmögliches' t mit dieser Eigenschaft definiert?
Wenn nicht, ist die Frage ja ziemlich trivial.

air


Ich seh grad echt den Wald vor lauter Bäumen nicht mehr. Erkläre mir bitte diese Trivialiät Big Laugh
 
 
Airblader Auf diesen Beitrag antworten »

Wenn es ein beliebiges t ist, das der ersten Ungleichung gerecht wird, dann kannst du es einfach so groß wählen, dass es auch der fraglichen Ungleichung genügt.

air
uffembetze Auf diesen Beitrag antworten »

Ach so meinst du das. Na so kann ich das leider nicht machen Augenzwinkern Gerade weil es ersteinmal ein beliebiges t ist, das der ersten Ungleichung gerecht wird, kann ich nicht einfach ein t nehmen, bis es passt.

Es muss halt für ein beliebiges t passen..

Ich werd mir morgen weiter Gedanken darüber machen. Jetzt erstmal Danke für deine Beteiligung..

uffembetze
Airblader Auf diesen Beitrag antworten »

Dann müssen schlicht und ergreifend noch andere Faktoren eine Rolle spielen, die du nun nicht genannt hast.
Da ich den AKS-Primzahltest aber nicht kenne, kann ich da nicht viel zu sagen.
Eventuell kann sich der Arthur da ja besser zu äußern?

air
Huggy Auf diesen Beitrag antworten »
RE: Gaußklammer / AKS Algorithmus
Da sehe ich ein echtes Problem, weil sich leicht ein Gegenbeispiel konstruieren lässt. Es ist ja log hier der Logarithmus zur Basis 2. Sei z. B.



Dann ist



Es ist aber

uffembetze Auf diesen Beitrag antworten »

Also ich habe noch eine zusätzliche Information, die mir bis jetzt aber auch noch nicht entscheidend weiterhilft:



Damit kann man also sogar abschätzen:

uffembetze Auf diesen Beitrag antworten »

Zitat:
Original von uffembetze
Also ich habe noch eine zusätzliche Information, die mir bis jetzt aber auch noch nicht entscheidend weiterhilft:



Damit kann man also sogar abschätzen:



Die letzte Information war so nicht richtig Hammer .. das Problem ist aber gelöst.

Die echt Ungleichheit gilt u.a. für die Fälle n=2 unt t=2,3 nicht. Das Lemma, welches hier aber bewiesen werden soll, ist auch für diese Fälle gültig.

Alle anderen Fälle, für die die Ungleichheit nicht gilt, sind irrelevant.

Das war jetzt nur für Leute, die das vielleicht interessiert. Ist klar Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »