Wurzeln modulo p nicht definiert |
14.03.2020, 19:37 | AnjaT | Auf diesen Beitrag antworten » | ||||||||
Wurzeln modulo p nicht definiert Für Tschebyscheff-Polynome über habe ich die folgende Darstellung gefunden: . Meine Ideen: Nun ist aber doch über für manche x überhaupt nicht definiert. Wie kann die obige Formel dann eine korrekte Repräsentation der Tschebyscheff-Polynome sein? |
||||||||||
14.03.2020, 19:50 | Elvis | Auf diesen Beitrag antworten » | ||||||||
Wirklich über endlichen Primkörpern und nicht über p-adischen Zahlkörpern ? |
||||||||||
14.03.2020, 22:24 | AnjaT | Auf diesen Beitrag antworten » | ||||||||
Nein, über . Eine Erklärung wäre, dass am Ende keine ungeradzahligen Potenzen von b enthält, sodass die Wurzeln doch immer definiert werden. Dann habe ich aber das Problem, dass ich beim Versuch, das zu beweisen, leider nie einen Ausdruck mit für sich verwenden kann, da mir dann wieder die Möglichkeit in die Quere käme, dass die Wurzel nicht definiert ist... Hat da jemand eine Lösung? |
||||||||||
15.03.2020, 10:07 | AnjaT | Auf diesen Beitrag antworten » | ||||||||
Darf ich zum Beispiel beim Beweis anfangen mit Setze , um dann die Formel anzuwenden, obwohl in für manche x doch gar nicht definiert wäre? Was wäre eine andere Möglichkeit, das zu beweisen? |
||||||||||
15.03.2020, 20:43 | KeinGastMehr | Auf diesen Beitrag antworten » | ||||||||
Die Frage ist, wo du das gefunden hast und was da genau steht. Ich habe da Zweifel; für teilt man auch durch . Dass sich die am Ende wegkürzt, ist mir klar, aber wieso sollte man das so schreiben? |
||||||||||
15.03.2020, 22:10 | AnjaT | Auf diesen Beitrag antworten » | ||||||||
Da hast du Recht; wir gehen von aus. Ansonsten stimmt es jedoch. Kann jemand (beim Beweis dieser Formel) helfen? |
||||||||||
Anzeige | ||||||||||
|
||||||||||
15.03.2020, 22:15 | KeinGastMehr | Auf diesen Beitrag antworten » | ||||||||
Die Frage ist immer noch, wo du diese Formel gelesen hast. Ich möchte nachprüfen, ob diese Formel explizit für die Polynome über angegeben wurde. Und wenn du diese Formel beweisen möchtest, muss man zuerst sagen, wie denn die Tschebyscheff-Polynome eigentlich definiert sind - erst dann kann man überhaupt zeigen, dass beide Ausdrücke gleich sind. |
||||||||||
17.03.2020, 15:55 | AnjaT | Auf diesen Beitrag antworten » | ||||||||
Bspw. hier: pdfs.semanticscholar.org/6b40/318a2664cd1bfa7ffdbb48bd7ccb5922c114 . pdf findet sich diese Darstellung. Man geht von der rekursiven Definition aus. |
||||||||||
17.03.2020, 19:30 | KeinGastMehr | Auf diesen Beitrag antworten » | ||||||||
Du hast ein kleines aber feines Detail unterschlagen, nämlich:. Das sieht für mich so aus, als wenn man einfach alles über (meinetwegen) berechnen würde und dann am Ende modulo reduziert (man kann natürlich auch reelle/komplexe Zahlen modulo reduzieren). Ein Beweis ist dort ja angegeben, ab welcher Stelle verstehst du ihn nicht mehr? Da, wo die Formel einfach vom Himmel fällt, verwendet man Induktion. Probier es mal. |
||||||||||
17.03.2020, 20:54 | tatmas | Auf diesen Beitrag antworten » | ||||||||
Hallo, @KeinGastmehr: Wie soll eine reelle zahlmodulo p zu reduzieren funktioneren? Was ist denn z.B. e mod 7? Und TE hat kein Detail unterschlagen, dass das modulo p gerechnet wird steht im Ausgangspost, und ist in der Tat die Frage hier: die Wurzeln sind a priori mod p nicht definiert. |
||||||||||
17.03.2020, 21:12 | KeinGastMehr | Auf diesen Beitrag antworten » | ||||||||
@tatmas: ist eine Gruppe und ist die Klasse darin. Ist eine etwas ungünstige Notation, aber man kann natürlich sagen, wann zwei reelle Zahlen kongruent modulo einer Zahl sind. Und es macht einen Unterschied, ob man direkt in rechnet oder zuerst in z.B. rechnet und dann die Abbildung betrachtet. Alle Rechnungen in dem Artikel finden über statt und dann wird reduziert. Warum das so gemacht wird, kann ich nicht mit 100%iger Sicherheit sagen, weil ich von Kryptographie wenig Ahnung habe. Vermutlich, um das Problem mit den Wurzeln zu umgehen und vermutlich auch, weil natürlich mehr Informationen in den Polynomen mit ganzzahligen Koeffizienten stecken (und vielleicht, weil Polynome und Polynomfunktionen über nicht das gleiche sind?) |
||||||||||
17.03.2020, 21:25 | tatmas | Auf diesen Beitrag antworten » | ||||||||
Um auf die eigentliche Frage zurückzukommen: Wenn man mit dem Wurzelausdruck rechnen muss (hab das Paper nicht gelesen, kommt drauf an wie langweilig mir die nächsten tage ist), einfach in algebraischen Abschluss von GF(p) arbeiten, das dürfte nicht zu viel Unterschied machen. Für die Identität hebt sich die Wurzel aber in der Tat raus, wie du richtig anmerkst. d.h. bei heben sich alle ungeraden Potenzen (n-k) raus, und da B hier die Wurzel ist kann die jeweils dank der geraden potenz aufgelöst werden. @KeinGastMehr: An die komische Gruppenkonstruktion hatte ich nicht gedacht. Die bringt aber auch gar nichts, da hier mindestens eine Ringstruktur notig ist (Potenzen und Division) |
||||||||||
17.03.2020, 21:36 | tatmas | Auf diesen Beitrag antworten » | ||||||||
Im weiteren Verlauf gibt es Aussagen die davon abhängen ob die Wurzel in liegt oder nicht. D.h. hier wird höchstwahrscheinlich in einer geeigneten Körpererweiterung (normaler Abschluss o.ä., algebraischer Abschluss) gerechnet in dem die Wurzel existieren. |
||||||||||
17.03.2020, 21:37 | KeinGastMehr | Auf diesen Beitrag antworten » | ||||||||
@tatmas: Eine Ringstruktur braucht man hier nicht wirklich, man muss nicht unbedingt zwei Restklassen reeller Zahlen miteinander multiplizieren. Die mathematisch saubere Variante ist, über zu rechnen und erst am Ende alles zu reduzieren. Hatte auch daran gedacht, über einem Erweiterungskörper zu rechnen. Man kann auch wie gesagt über rechnen und erst dann reduzieren. Kommt auf das gleiche raus. Unabhängig von der Methode sollten wir dahingehend übereinstimmen, dass von den Autoren wohl ein Wort in die Richtung nötig gewesen wäre. Frage mich aber, warum sie überall mod p schreiben, wenn sie sowieso schon in (oder einem Erweiterungsring) rechnen. Kleiner Scherz am Rande: Und so komisch ist diese Gruppe übrigens nicht. Das ist nichts anderes als . Edit: Good catch! Habe nur den Beweis dieser Proposition gelesen. |
||||||||||
17.03.2020, 21:52 | tatmas | Auf diesen Beitrag antworten » | ||||||||
Da kann ich bberhaupt nicht folgen. Die x sind hier Elemente von ,nicht der reellen Zahlen. Mathematisch sauber ist in GF(p) zu rechnen und dann ggf. geeignete Körpererweitungen zu betrachten.
Wohl das alles (endliche) Körper mit Charakteristik p sind. Und hier wird in Körpern gerechnet, nicht in Polynomringen. |
||||||||||
17.03.2020, 21:59 | KeinGastMehr | Auf diesen Beitrag antworten » | ||||||||
Ui, jetzt kommen wir ins Details! Also, ja, da steht, dass ist. Dann betrachtet man hier also von Anfang an Abbildungen (oder meinetwegen ) und keine Polynome mit Koeffizienten in . Dann wird der Begriff "Chebyshev Polynomials" hier schlicht falsch verwendet. (Oder, wenn von Anfang an fixiert ist, dann ist ein konstantes Polynom...) Was ich gesagt habe, ist: Betrachte als eine Variable und die Polynome mit Einträgen in . Dann sind Polynome und Polynomfunktionen das gleiche, ich kann also für eine reelle Zahl einsetzen, den Wert ausrechnen und danach modulo p reduzieren. Das ist genau so sauber, wie ggf. Erweiterungen zu betrachten und läuft letztendlich auf dasselbe hinaus. Wenn man von Anfang an fixiert, dass ist, muss (oder: meiner Meinung nach, sollte) man nicht überall "mod p" hinschreiben. Das erweckt für mich eher den Anschein, als dass man es mit reellen/ganzen Zahlen zu tun hat und dann reduziert. |
||||||||||
18.03.2020, 13:42 | AnjaT | Auf diesen Beitrag antworten » | ||||||||
Was meinst du damit?
Aber funktioniert dann der gegebene Beweis überhaupt noch? Wenn ich z.B. und modulo p reduziere, gilt dann doch gar nicht mehr . |
||||||||||
18.03.2020, 14:15 | tatmas | Auf diesen Beitrag antworten » | ||||||||
@AnjaT: Ich bin komplett anderer Meinung als KeinGastMehr in seinem letzten Post. Chebyshev Polynomials ist richtig verwendet, das sind hier Polynome. Hier irgendwas in den reellen Zahlen zu rechnen finde ich sehr seltsam, ich sehe darin keinerlei Wert. Ich sehe nur dass man sich massiv einschränkt, man verliert hier die Ring/Körperstruktur. |
||||||||||
18.03.2020, 14:32 | AnjaT | Auf diesen Beitrag antworten » | ||||||||
Danke dir tatmas für die Rückmeldung. Dann rechnet man hier also in , oder einer anderen Körpererweiterung? Müsste das nicht dabeistehen? Macht das da noch Sinn? |
||||||||||
18.03.2020, 14:32 | KeinGastMehr | Auf diesen Beitrag antworten » | ||||||||
Ich verstehe die Anmerkung nicht. Wenn und , dann gilt . Unabhängig davon, ob ich jetzt in oder einer Erweiterung von rechne, sodass die Ausdrücke definiert sind.
Über endlichen Körpern sind Polynome und Polynomfunktionen nicht das gleiche. (Es gibt unendlich viele Polynome mit Koeffizienten in , aber nur Abbildungen ). Insbesondere kann man in Polynome mit Koeffizienten in nichts einsetzen. Bin auf deine Begründung gespannt, wieso das jetzt Polynome (und keine Polynomfunktionen oder sogar einfach nur Zahlen) sein sollen - du hast selbst gesagt, dass nur in einem Körper gerechnet wird und nicht in einem Polynomring oder etwas ähnlichem. Dass es einen Unterschied macht, habe ich gerade erklärt.
Dazu ist wohl alles gesagt. Hierauf bin ich schon mehrfach eingegangen, das wird aber weiterhin ignoriert. Edit:
Ja, wobei eine geeignete Erweiterung ist, sodass ein Quadrat darin ist, für ein festes . Das scheint nur anzudeuten, dass man in Charakteristik ist. Finde, dass es eine schreckliche Notation ist. |
||||||||||
18.03.2020, 15:19 | tatmas | Auf diesen Beitrag antworten » | ||||||||
@KeinGastMehr: Ich hab keine Ahnung warum du so auf dem Unterschied zwischen Polynom und Polynomfunktion rumreitest. Keine Ahnung was das mit dem Thema hier überhaupt zu tun hat. Und das ist jetztn auch keine weltbewegende Erkenntnis.
Das ist absoluter Unsinn. Natürlich kann man das, nennt sich Einsatzhomomorphismus.
Dito. Ich bin raus. Ich hab in Quarantäne besseres zu tun. Das Paper ist aber in der Tat interessant. |
||||||||||
18.03.2020, 15:56 | KeinGastMehr | Auf diesen Beitrag antworten » | ||||||||
Darauf gehe ich noch kurz ein, und dann lass ich es auch gut sein.
Das habe ich auch nicht behauptet. Du hingegen hast behauptet, der Begriff "Chebyshev Polynomials" würde hier richtig verwendet und hast das nicht begründet. Ich habe klar gemacht, dass mich das verwirrt hat und ich wegen der Verwendung des Begriffs "polynomials" als eine Unbestimmte angesehen habe und somit dachte, man rechne in einem Polynomring. Dabei ist von Anfang an fest und man hat es von Anfang an nur mit Zahlen (oder, wenn überhaupt, Polynomfunktionen) zu tun. Dass ich nicht genau gelesen habe, gebe ich zu. Ich kritisiere nur die Ungenauigkeiten des Artikels. Ich will nicht, dass diese Diskussion ausartet, aber wann immer Vorträge gehalten habe (oder bei der handvoll Paper, die ich bisher eingereicht habe), wurde ich für solche kleinen Ungenauigkeiten und schlechte Notation zerfleischt. Wenn ich entgegnet habe: "da steht doch, dass sei", zählte die Ausrede nicht; daraufhin wurde mir einfach gesagt "diese Sache verwirrt, also ist es nicht gut geschrieben. Warum nennst du es nicht statt ?". Ähnlich mit dem Begriff "polynomials" statt "polynomial functions" o.ä.
War falsch ausgedrückt. Meinte: Ein Polynom über ist durch seine Werte nicht eindeutig bestimmt. Typischer Fall von "gedacht", aber nicht "geschrieben". Da hast du Recht - danke für die Korrektur.
Wüsste nicht, wo ich etwas von dir ignoriert habe; du hingegen bist nicht darauf eingegangen, was ich zu deiner Anmerkung, man verliere die Ringstruktur (was auch stimmt) gesagt habe: Nämlich, dass - wenn man es richtig angeht - nur eine abelsche Gruppe bzgl. der Addition benötigt. Letztendlich ist es egal, wie man vorgeht. Wie auch schon mehrmals gesagt: Am Ende läuft es auf's Gleiche hinaus. Ich wünsche dir viel Erholung und hoffe, dass die Quarantäne nicht zu schlimm ist. Finde den Artikel auch interessant, aber komisch geschrieben (nicht nur aufgrund der sprachlichen Fehler). |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|