Gaußklammer / AKS Algorithmus |
31.10.2008, 16:56 | uffembetze | Auf diesen Beitrag antworten » | ||
Gaußklammer / AKS Algorithmus 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 |
||||
31.10.2008, 17:34 | 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 |
||||
31.10.2008, 17:37 | 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 @uffembetze Ist t denn als 'kleinstmögliches' t mit dieser Eigenschaft definiert? Wenn nicht, ist die Frage ja ziemlich trivial. air |
||||
31.10.2008, 17:44 | uffembetze | Auf diesen Beitrag antworten » | ||
RE: Gaußklammer / AKS Algorithmus
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.. |
||||
31.10.2008, 18:19 | klarsoweit | Auf diesen Beitrag antworten » | ||
RE: Gaußklammer / AKS Algorithmus
Ach herje, dieses "komische" Zeichen sollte die Gaußklammer sein. OK, man muß auch den Titel lesen. |
||||
31.10.2008, 18:23 | uffembetze | Auf diesen Beitrag antworten » | ||
Ich seh grad echt den Wald vor lauter Bäumen nicht mehr. Erkläre mir bitte diese Trivialiät |
||||
Anzeige | ||||
|
||||
31.10.2008, 21:02 | 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 |
||||
31.10.2008, 21:15 | uffembetze | Auf diesen Beitrag antworten » | ||
Ach so meinst du das. Na so kann ich das leider nicht machen 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 |
||||
31.10.2008, 22:44 | 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 |
||||
02.11.2008, 10:10 | 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 |
||||
02.11.2008, 16:57 | 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: |
||||
06.11.2008, 12:12 | uffembetze | Auf diesen Beitrag antworten » | ||
Die letzte Information war so nicht richtig .. 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 |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|