Wurzeln modulo p nicht definiert

14.03.2020, 19:37

AnjaT

Wurzeln modulo p nicht definiert

Meine Frage:
Für Tschebyscheff-Polynome über $\begin{eqnarray*} F_p \end{eqnarray*}$ habe ich die folgende Darstellung gefunden:

$\begin{eqnarray*} T_n(x)=\frac{(x+\sqrt{x^2-1})^n+(x-\sqrt{x^2-1})^n}{2} \end{eqnarray*}$ .

Meine Ideen:
Nun ist aber doch $\begin{eqnarray*} \sqrt{x^2-1} \end{eqnarray*}$ über $\begin{eqnarray*} F_p \end{eqnarray*}$ 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 $\begin{eqnarray*} \mathbb F_p \end{eqnarray*}$ und nicht über p-adischen Zahlkörpern $\begin{eqnarray*} \mathbb Q_p \end{eqnarray*}$ ?

14.03.2020, 22:24

AnjaT

Auf diesen Beitrag antworten »

Nein, über $\begin{eqnarray*} F_p \end{eqnarray*}$ .

Eine Erklärung wäre, dass $\begin{eqnarray*} (a+b)^n+(a-b)^n \end{eqnarray*}$ 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 $\begin{eqnarray*} \sqrt{x^2-1} \end{eqnarray*}$ 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 $\begin{eqnarray*} a=x+\sqrt{x^2-1} \end{eqnarray*}$ ,

um dann die Formel $\begin{eqnarray*} T_n(\frac{1}{2}(a+a^{-1}))=\frac{1}{2}(a^n+a^{-n}) \end{eqnarray*}$

anzuwenden, obwohl $\begin{eqnarray*} a=x+\sqrt{x^2-1} \end{eqnarray*}$ in $\begin{eqnarray*} F_p \end{eqnarray*}$ 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 $\begin{eqnarray*} p = 2 \end{eqnarray*}$ teilt man auch durch $\begin{eqnarray*} 0 \end{eqnarray*}$ . Dass sich die $\begin{eqnarray*} 2 \end{eqnarray*}$ 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 $\begin{eqnarray*} p>2 \end{eqnarray*}$ aus. Ansonsten stimmt es jedoch. Kann jemand (beim Beweis dieser Formel) helfen?

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 $\begin{eqnarray*} \mathbb F_p \end{eqnarray*}$ 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: $\begin{eqnarray*} \pmod p \end{eqnarray*}$ .

Das sieht für mich so aus, als wenn man einfach alles über (meinetwegen) $\begin{eqnarray*} \mathbb R \end{eqnarray*}$ berechnen würde und dann am Ende modulo $\begin{eqnarray*} p \end{eqnarray*}$ reduziert (man kann natürlich auch reelle/komplexe Zahlen modulo $\begin{eqnarray*} p \end{eqnarray*}$ 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:

$\begin{eqnarray*} \mathbb R/p\mathbb Z \end{eqnarray*}$ ist eine Gruppe und $\begin{eqnarray*} e \pmod 7 \end{eqnarray*}$ 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 $\begin{eqnarray*} \mathbb F_p[x] \end{eqnarray*}$ rechnet oder zuerst in z.B. $\begin{eqnarray*} \mathbb Z[x] \end{eqnarray*}$ rechnet und dann die Abbildung $\begin{eqnarray*} \mathbb Z[x] \to \mathbb F_p[x] \end{eqnarray*}$ betrachtet. Alle Rechnungen in dem Artikel finden über $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$ 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 $\begin{eqnarray*} \mathbb F_p \end{eqnarray*}$ 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.

$\begin{eqnarray*} (A\pm B) ^n= \sum_{k=0}^n A^k \binom{n}{k}(\pm 1)^{n-k}B^{n-k} \end{eqnarray*}$
d.h. bei $\begin{eqnarray*} (A+B)^n +(A-B)^n \end{eqnarray*}$ 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 $\begin{eqnarray*} \mathbb F_p \end{eqnarray*}$ 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 $\begin{eqnarray*} \mathbb R \end{eqnarray*}$ 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 $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$ 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 $\begin{eqnarray*} \mathbb F_p[x] \end{eqnarray*}$ (oder einem Erweiterungsring) rechnen.

Kleiner Scherz am Rande: Und so komisch ist diese Gruppe übrigens nicht. Das ist nichts anderes als $\begin{eqnarray*} S^1 \end{eqnarray*}$ . Big Laugh

Edit: Good catch! Habe nur den Beweis dieser Proposition gelesen.

17.03.2020, 21:52

tatmas

Auf diesen Beitrag antworten »

Zitat:

Die mathematisch saubere Variante ist, über ℝ zu rechnen und erst am Ende alles zu reduzieren.

Da kann ich bberhaupt nicht folgen.
Die x sind hier Elemente von $\begin{eqnarray*} \mathbb F_p \end{eqnarray*}$ ,nicht der reellen Zahlen.
Mathematisch sauber ist in GF(p) zu rechnen und dann ggf. geeignete Körpererweitungen zu betrachten.

Zitat:

Frage mich aber, warum sie überall mod p schreiben, wenn sie sowieso schon in 𝔽p[x] (oder einem Erweiterungsring) rechnen.

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 $\begin{eqnarray*} x \in \mathbb F_p^* \end{eqnarray*}$ ist. Dann betrachtet man hier also von Anfang an Abbildungen $\begin{eqnarray*} \mathbb F_p \to \mathbb F_p \end{eqnarray*}$ (oder meinetwegen $\begin{eqnarray*} \mathbb F_p^* \to \mathbb F_p \end{eqnarray*}$ ) und keine Polynome mit Koeffizienten in $\begin{eqnarray*} \mathbb F_p \end{eqnarray*}$ . Dann wird der Begriff "Chebyshev Polynomials" hier schlicht falsch verwendet. (Oder, wenn $\begin{eqnarray*} x \end{eqnarray*}$ von Anfang an fixiert ist, dann ist $\begin{eqnarray*} T_n(x) \end{eqnarray*}$ ein konstantes Polynom...)

Was ich gesagt habe, ist: Betrachte $\begin{eqnarray*} x \end{eqnarray*}$ als eine Variable und die Polynome mit Einträgen in $\begin{eqnarray*} \mathbb R \end{eqnarray*}$ . Dann sind Polynome und Polynomfunktionen das gleiche, ich kann also für $\begin{eqnarray*} x \end{eqnarray*}$ 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 $\begin{eqnarray*} x \in \mathbb F_p^* \end{eqnarray*}$ 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 »

Zitat:

Original von KeinGastMehr
Dann wird der Begriff "Chebyshev Polynomials" hier schlicht falsch verwendet. (Oder, wenn $\begin{eqnarray*} x \end{eqnarray*}$ von Anfang an fixiert ist, dann ist $\begin{eqnarray*} T_n(x) \end{eqnarray*}$ ein konstantes Polynom...)

Was meinst du damit?

Zitat:

Original von KeinGastMehr
Was ich gesagt habe, ist: Betrachte $\begin{eqnarray*} x \end{eqnarray*}$ als eine Variable und die Polynome mit Einträgen in $\begin{eqnarray*} \mathbb R \end{eqnarray*}$ . Dann sind Polynome und Polynomfunktionen das gleiche, ich kann also für $\begin{eqnarray*} x \end{eqnarray*}$ eine reelle Zahl einsetzen, den Wert ausrechnen und danach modulo p reduzieren.

Aber funktioniert dann der gegebene Beweis überhaupt noch? Wenn ich z.B. $\begin{eqnarray*} \lambda_1 \end{eqnarray*}$ und $\begin{eqnarray*} \lambda_2 \end{eqnarray*}$ modulo p reduziere, gilt dann doch gar nicht mehr $\begin{eqnarray*} \lambda_1\cdot \lambda_2=1 \end{eqnarray*}$ .

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 $\begin{eqnarray*} F_{p^2} \end{eqnarray*}$ , oder einer anderen Körpererweiterung? Müsste das nicht dabeistehen? Macht das $\begin{eqnarray*} mod p \end{eqnarray*}$ da noch Sinn?

18.03.2020, 14:32

KeinGastMehr

Auf diesen Beitrag antworten »

Zitat:

Original von AnjaT
Aber funktioniert dann der gegebene Beweis überhaupt noch? Wenn ich z.B. $\begin{eqnarray*} \lambda_1 \end{eqnarray*}$ und $\begin{eqnarray*} \lambda_2 \end{eqnarray*}$ modulo p reduziere, gilt dann doch gar nicht mehr $\begin{eqnarray*} \lambda_1\cdot \lambda_2=1 \end{eqnarray*}$ .

Ich verstehe die Anmerkung nicht. Wenn $\begin{eqnarray*} \lambda_1 = x + \sqrt{x^2-1} \end{eqnarray*}$ und $\begin{eqnarray*} \lambda_2 = x - \sqrt{x^2-1} \end{eqnarray*}$ , dann gilt $\begin{eqnarray*} \lambda_1\lambda_2 = x^2 - (x^2-1) = 1 \end{eqnarray*}$ . Unabhängig davon, ob ich jetzt in $\begin{eqnarray*} \mathbb R \end{eqnarray*}$ oder einer Erweiterung von $\begin{eqnarray*} \mathbb F_p \end{eqnarray*}$ rechne, sodass die Ausdrücke definiert sind.

Zitat:

Original von tatmas
Chebyshev Polynomials ist richtig verwendet, das sind hier Polynome.

Über endlichen Körpern sind Polynome und Polynomfunktionen nicht das gleiche. (Es gibt unendlich viele Polynome mit Koeffizienten in $\begin{eqnarray*} \mathbb F_p \end{eqnarray*}$ , aber nur $\begin{eqnarray*} p^p \end{eqnarray*}$ Abbildungen $\begin{eqnarray*} \mathbb F_p \to \mathbb F_p \end{eqnarray*}$ ). Insbesondere kann man in Polynome mit Koeffizienten in $\begin{eqnarray*} \mathbb F_p \end{eqnarray*}$ 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.

Zitat:

Original von tatmas
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.

Dazu ist wohl alles gesagt. Hierauf bin ich schon mehrfach eingegangen, das wird aber weiterhin ignoriert.

Edit:

Zitat:

Original von AnjaT
Dann rechnet man hier also in $\begin{eqnarray*} F_{p^2} \end{eqnarray*}$ , oder einer anderen Körpererweiterung? Müsste das nicht dabeistehen? Macht das $\begin{eqnarray*} mod p \end{eqnarray*}$ da noch Sinn?

Ja, wobei $\begin{eqnarray*} \mathbb F_{p^2} \end{eqnarray*}$ eine geeignete Erweiterung ist, sodass $\begin{eqnarray*} x^2-1 \end{eqnarray*}$ ein Quadrat darin ist, für ein festes $\begin{eqnarray*} x \in \mathbb F_p^* \end{eqnarray*}$ .
Das $\begin{eqnarray*} \pmod p \end{eqnarray*}$ scheint nur anzudeuten, dass man in Charakteristik $\begin{eqnarray*} p \end{eqnarray*}$ 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.

Zitat:

Insbesondere kann man in Polynome mit Koeffizienten in 𝔽p nichts einsetzen

Das ist absoluter Unsinn. Natürlich kann man das, nennt sich Einsatzhomomorphismus.

Zitat:

Dazu ist wohl alles gesagt. Hierauf bin ich schon mehrfach eingegangen, das wird aber weiterhin ignoriert.

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.

Zitat:

Original von tatmas
@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 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 $\begin{eqnarray*} x \end{eqnarray*}$ wegen der Verwendung des Begriffs "polynomials" als eine Unbestimmte angesehen habe und somit dachte, man rechne in einem Polynomring. Dabei ist $\begin{eqnarray*} x \end{eqnarray*}$ 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 $\begin{eqnarray*} x \in \mathbb F_p^* \end{eqnarray*}$ 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 $\begin{eqnarray*} a \end{eqnarray*}$ statt $\begin{eqnarray*} x \end{eqnarray*}$ ?". Ähnlich mit dem Begriff "polynomials" statt "polynomial functions" o.ä.

Zitat:

Das ist absoluter Unsinn. Natürlich kann man das, nennt sich Einsatzhomomorphismus.

War falsch ausgedrückt. Meinte: Ein Polynom über $\begin{eqnarray*} \mathbb F_p \end{eqnarray*}$ ist durch seine Werte nicht eindeutig bestimmt. Typischer Fall von "gedacht", aber nicht "geschrieben". Da hast du Recht - danke für die Korrektur.

Zitat:

Dito.

Ich bin raus. Ich hab in Quarantäne besseres zu tun.
Das Paper ist aber in der Tat interessant.

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

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

Neue Frage »

Antworten »

Wurzeln modulo p nicht definiert

Verwandte Themen