Teilbarkeit einer Funktion - Seite 2

10.05.2016, 17:51	Nicht_Adam_Ries	Auf diesen Beitrag antworten »
Auf diese Weise erhält man offensichtlich das kleinstmögliche x, damit die Kongruenz f(x) = 0 (mod p^2) passt Bei aller Hilfe, die ich schon erhalten hab , traue ich mich kaum zu fragen, ob es noch eine schnellere Variante gibt, eine modulare Nullstelle zu berechnen, als bloßes Probieren, was man auch in anderen Veröffentlichungen bspw auf stackoverflow findet.
16.05.2016, 16:01	Nicht_Adam_Ries	Auf diesen Beitrag antworten »
Für diejenigen, die sich ebenfalls für diese Thematik interessieren: Ich denke ich habe eine Lösung gefunden. Auf Stackexchange nach "modular zero of a function" suchen (ich kann leider keine Links posten). Es geht hierbei um eine quadratische Funktion f(n), die durch eine Primzahl "geteilt" werden soll, so dass gilt $\begin{eqnarray} f(n) = 0 (mod p) \end{eqnarray}$ . Es läuft darauf hinaus, die Diskriminante von f durch $\begin{eqnarray} b^{2} - 4ac \end{eqnarray}$ zu bestimmen und dann das Legendre-Symbol L(a\|p) zu nutzen, wobei -a- die Diskriminante ist und p die Primzahl. Ergibt sich hierbei L(a\|p) = 1, so kann man den Tonelli-Shanks-Algorithmus benutzen um x zu finden, so dass $\begin{eqnarray} x^{2} = a (mod p) \end{eqnarray}$ gilt. Für kleinere Primzahlen ist das u. U. Overkill. Erhält man hier eine Lösung x, dann ist (p - x) ebenfalls eine Lösung. Mögliche Lösungen n, dass $\begin{eqnarray} f(n) = 0 (mod p) \end{eqnarray}$ ist, bestimmt man durch $\begin{eqnarray} n = \frac{b + x}{2a} \end{eqnarray}$ bzw. $\begin{eqnarray} n = \frac{b + p - x}{2a} \end{eqnarray}$ . Für $\begin{eqnarray} p^{2} \end{eqnarray}$ kann man dann auf Hensel's Lemma zurückgreifen, wie tatmas schon gesagt hatte. Ich hoffe, ich habe das halbwegs korrekt wiedergegeben. Evtl. könnten HAL9000 oder tatmas oder andere Wissende korrigieren oder ergänzen.
09.12.2016, 18:45	Hosenschlange	Auf diesen Beitrag antworten »
Interessante Geschichte. Aber im finalen Kommentar komme ich durcheinander: Die Diskriminante D berechne ich mittels b^2- 4ac. Dann berechne ich das Legendre Symbol L(a\|p), hier ist a die Diskriminante. Ich berechne also L(D\|p). Wenn das Legendre Symbol ungleich 1 ist --> Abbruch. Danach kommt Shanks Tonelli für x^2 = a (mod p). Und hier taucht eigentlich die erste Frage auf: Welches a ist das? Das a mit dem ich auch die Diskriminante D berechne, oder ist das die Diskriminante? Ich vermute letzteres. Aber es geht ja noch weiter. x und p-x ergeben dann Lösungen der Kongruenz. Mit denen kann ich n berechnen und zwar mit den Gleichungen, die im Kommentar am Ende stehen. Hier stellt sich wieder die Frage, was dieses a sein soll. Ist das das a aus der Ausgangsfunktions f(n), mit dem ich die Diskriminante berechnet habe? Oder ist es die Diskriminante? Ein Beispiel: f(n) = n^2 - 3n - 1 => a = 1, b = -3, c = -1, D = 13, p = 17 Damit berechne ich mit Shanks Tonelli --> x = 8, (p-x) = 9. 1) Verwende ich nun für a nicht die Diskriminante, sondern das a aus der Ausgangsfunktion erhalte ich: n1 = (-3 + 8) / 2 = 2,5 und n2 = (-3 + 17 - 8) / 2 = 3. Setze ich n1 oder n2 in f(n) ein, ergibt das keinen Divisionsrest 0. 2) Wenn ich für a die Diskriminante D benutze erhalte ich: n1 = (-3 + 8) / 26 = 0,19... und n2 = (-3 + 17 - 8) / 26 = 0,23... Den Rest kann man sich denken. Könnte hier bitte nochmal jemand aufklären?

« vorherige Seite 12

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »