Polynom faktorisieren modulo

14.07.2023, 15:35	PolyFact	Auf diesen Beitrag antworten »
Polynom faktorisieren modulo Wenn ich ein quadratisches Polynom mit einer Konstanten habe $\begin{eqnarray} X^2 + c \end{eqnarray}$ und dies faktorisieren möchte $\begin{eqnarray} X^2 + c = (X-a)(X+a) \end{eqnarray}$ , wobei das hier alles in $\begin{eqnarray} \mathbb{Z}_q \end{eqnarray}$ zu betrachten ist. Wie geht man sowas an, ohne, dass man Werte "durchprobiert". Ein Beispiel: In $\begin{eqnarray} \mathbb{Z}_{17} \end{eqnarray}$ komme ich auf $\begin{eqnarray} X^2 + 4 = (X^2 + 8)(X^2 - 8) \end{eqnarray}$ , indem ich die Werte hier durchprobiert habe, aber geht das auch über eine Rechnung? Wenn der Ring größer wird, wird es ja auch schwieriger alles durchzuprobieren... Man müsste also $\begin{eqnarray} a(-a) = c \text{ mod } 17 \end{eqnarray}$ lösen.
14.07.2023, 16:22	Elvis	Auf diesen Beitrag antworten »
Man kann auch $\begin{eqnarray} X^2 +c=(X+a) (X+b) \end{eqnarray}$ faktorisieren. Es muss nicht immer $\begin{eqnarray} a+b=0 \end{eqnarray}$ sein.
14.07.2023, 16:51	PolyFact	Auf diesen Beitrag antworten »
Richtig Aber ich hatte ausgelassen, dass genau so eine Faktorisierung $\begin{eqnarray} X^2 + c = (X-a)(X+a) \end{eqnarray}$ entstehen soll.
14.07.2023, 17:53	Elvis	Auf diesen Beitrag antworten »
$\begin{eqnarray} -c=a^2 \end{eqnarray}$ ist dann ein Quadrat mod $\begin{eqnarray} q \end{eqnarray}$ . Bevor man probiert, kann man erst einmal das Legendre- oder Jacobi-Symbol $\begin{eqnarray} (\frac {-c} q) \end{eqnarray}$ berechnen.
15.07.2023, 10:43	Elvis	Auf diesen Beitrag antworten »
In deinem Beispiel ist $\begin{eqnarray} (\frac {-4}{17})=(\frac {13}{17}) \end{eqnarray}$ . Das quadratische Reziprozitaetsgesetz sagt $\begin{eqnarray} (\frac {13}{17})\cdot (\frac {17}{13})=(-1)^{\frac {13-1}2\cdot\frac {17-1}2}=1 \end{eqnarray}$ , weil 13 und 17 kongruent 1 mod 4, also nicht beide kongruent 3 mod 4 sind. Daraus folgt $\begin{eqnarray} (\frac {13} {17}) =(\frac {17} {13}) =(\frac 4{13}) =(\frac 2{13}) ^2 =1 \end{eqnarray}$ . Dabei ist unerheblich, ob 2 mod 13 ein Quadrat ist oder nicht, denn $\begin{eqnarray} 1^2=(-1)^2=1 \end{eqnarray}$ . Also ist -4 ein Quadrat mod 17 und deine Gleichung wie gewünscht lösbar. Also faktorisiert das Polynom mod 17 wie es soll, und wir wissen das ganz ohne probieren.
15.07.2023, 22:03	Elvis	Auf diesen Beitrag antworten »
Zum quadratischen Reziprozitaetsgesetz sollte man wissen, dass die Vermutung von L.Euler und der Beweis von C.F.Gauß stammt. (Dankeschön für die Erinnerung, war nett, mal wieder eine Kleinigkeit zu rechnen.) Wenn man weiß, dass $\begin{eqnarray} 4=2\cdot 2 \end{eqnarray}$ in natürlichen Zahlen ein Quadrat ist, genügt schon der erste Ergänzungssatz $\begin{eqnarray} (\frac {-1}p)=(-1)^{\frac {p-1}2} \end{eqnarray}$ , um wegen $\begin{eqnarray} (\frac {-4}{17}) =(\frac {-1}{17}) =1 \end{eqnarray}$ als Quadrat modulo 17 zu erkennen. Und nach dem zweiten Ergänzungssatz ist auch 2 ein Quadrat modulo 17, was wir gestern noch nicht wussten. Das quadratische Reziprozitaetsgesetz ist sehr schön dargestellt z.B. bei biancahoegel.de 'Mathematik' 'Zahlentheorie' 'Algebraische Zahlentheorie und arithmetische Geometrie' (https://www.biancahoegel.de/mathe/rechne...aetsgesetz.html).
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »