Kongruenzgleichung lösen

02.05.2024, 15:46

ärig

Kongruenzgleichung lösen

Meine Frage:
Hallo könnt ihr mir bei meiner Kongruenzgleichung helfen?
Sie ist wie folgt:
x^7 kongruent zu 10 (mod19)

Meine Ideen:
Was wir bisher wissen: Eine primitive Wurzel findet man, indem man die primitiven Restklassen einer Zahl sich anschaut, und dann über Brute Force durchprobieren eine Zahl findet, deren Ordnung gleich Phi von der Zahl ist.
Das habe ich bei 2^18 mod (19)=1 gefunden. Denn die Ordnung ist ja dann 18, und Phi von 19 ist auch 18.

Doch nun fehlt es uns an einem Ansatz wie wir weiter vorgehen können. Könntet ihr uns da helfen, wir hängen schon sehr lange daran...
LG

02.05.2024, 16:35

Elvis

Auf diesen Beitrag antworten »

Berechne y=x^2 mod 19 für x von 0 bis 18.
Berechne z=(y mod 19)^3 mod 19.
Berechne (x mod 19)*(z mod 19) mod 19.

02.05.2024, 20:03

HAL 9000

Auf diesen Beitrag antworten »

Sehe ich auch so: Mag zwar nicht elegant aussehen, aber Brute force ist doch bei Modul 19 völlig Ok.

Einfach alle Werte $\begin{eqnarray*} x^7\bmod 19 \end{eqnarray*}$ für $\begin{eqnarray*} x=0,1,\ldots,9 \end{eqnarray*}$ ausrechnen, dann bekommt man auch leicht $\begin{eqnarray*} \left(-x\right)^7 = -x^7\bmod 19 \end{eqnarray*}$ und kann dann raussuchen, wo $\begin{eqnarray*} 10\equiv -9\bmod 19 \end{eqnarray*}$ rauskommt.

P.S.: Der Verweis auf Primitivwurzeln $\begin{eqnarray*} g \end{eqnarray*}$ modulo $\begin{eqnarray*} p \end{eqnarray*}$ spielt vermutlich auf den damit verbundenen diskreten Logarithmus an, der auf

$\begin{eqnarray*} g^i\equiv k\bmod p \quad\Leftrightarrow\quad \operatorname{ind}_g(k)\equiv i\bmod (p-1) \end{eqnarray*}$

beruht. Damit kann man $\begin{eqnarray*} x^7\equiv 10\bmod 19 \end{eqnarray*}$ durch "diskretes Logarithmieren" umwandeln in

$\begin{eqnarray*} 7\cdot \operatorname{ind}_2(x)\equiv \operatorname{ind}_2(10)\bmod 18 \end{eqnarray*}$ .

Nun ist $\begin{eqnarray*} 0 = \operatorname{ind}_2(1) = \operatorname{ind}_2(20) \equiv \operatorname{ind}_2(2) + \operatorname{ind}_2(10) = 1+\operatorname{ind}_2(10)\bmod 18 \end{eqnarray*}$ , also $\begin{eqnarray*} \operatorname{ind}_2(10)=17 \end{eqnarray*}$ . Es folgt $\begin{eqnarray*} \operatorname{ind}_2(x)\equiv \frac{17+18}{7} = 5\bmod 18 \end{eqnarray*}$ , und daraus schließlich $\begin{eqnarray*} x\equiv 2^5=32\equiv 13\bmod 19 \end{eqnarray*}$ .

Ich hab hier den benötigten diskreten Logarithmuswert für 10 schnell von Hand ausgerechnet - i.a. wird man da aber eher eine Tabelle vorberechnen.

EDIT: Modul 9 an einer Stelle war Verschreiber, es muss 19 heißen.

04.05.2024, 08:14

aerig

Auf diesen Beitrag antworten »

Kongruenzgleichung lösen
Heißt das es ist gar nicht nötig in diesem Fall die Primitivwurzel zu berechnen?
War denn meine "Erklärung" im Beitrag richtig, also haben wir es richtig verstanden was seine Primitivwurzel ist?

Das heißt wir müssen jetzt einfach alle Werte ausrechnen und schauen wann unser Ergebnis rauskommt?
Wie kommt man auf (-x) ^7 =-x^7 mod 9 Also warum durften wir hier das Modulo von 19 auf 9 ändern?
Danke für die schnelle Antwort!

04.05.2024, 08:30

HAL 9000

Auf diesen Beitrag antworten »

RE: Kongruenzgleichung lösen

Zitat:

Original von aerig
Wie kommt man auf (-x) ^7 =-x^7 mod 9 Also warum durften wir hier das Modulo von 19 auf 9 ändern?

Da muss ich mich entschuldigen (Tastaturklemmer), hier muss selbstverständlich auch Modul 19 stehen.

04.05.2024, 08:45

Elvis

Auf diesen Beitrag antworten »

Einfach alle 7. Potenzen und deren Reste modulo 19 berechnen ist mir nicht einfach genug, deshalb habe ich eine Möglichkeit vorgeschlagen, wie man den Rechenaufwand etwas reduzieren kann. Per Hand mache ich das auch nicht, aber mit Excel ist man da ganz schnell durch.

06.05.2024, 07:48

HAL 9000

Auf diesen Beitrag antworten »

> Einfach alle 7. Potenzen und deren Reste modulo 19 berechnen ist mir nicht einfach genug,

Nun ja, man muss ja nicht jedes Mal die Erfindung des Rades ausführlich erläutern. Ich bin davon ausgegangen, dass die folgende Berechnungsweise von $\begin{eqnarray*} x^n\bmod m \end{eqnarray*}$ für "große $\begin{eqnarray*} n \end{eqnarray*}$ " bekannt ist:

Man betrachtet die Binärdarstellung von Exponent $\begin{eqnarray*} n \end{eqnarray*}$ , d.h. $\begin{eqnarray*} n = \sum_{k=0}^r a_k 2^k \end{eqnarray*}$ mit $\begin{eqnarray*} a_k\in\{0,1\} \end{eqnarray*}$ und insbesondere dann $\begin{eqnarray*} a_r=1 \end{eqnarray*}$

Nun startet man mit $\begin{eqnarray*} x_0 = x \end{eqnarray*}$ und berechnet für $\begin{eqnarray*} k=1,\ldots, r \end{eqnarray*}$ sukzessive $\begin{eqnarray*} x_k = x_{k-1}^2\bmod m \end{eqnarray*}$ . Anschließend multipliziert man all diejenigen $\begin{eqnarray*} x_k \end{eqnarray*}$ miteinander, für die $\begin{eqnarray*} a_k=1 \end{eqnarray*}$ gilt - diese Multiplikationen geschehen ebenfalls wieder modulo $\begin{eqnarray*} m \end{eqnarray*}$ (muss zwischendurch nicht sein, am Ende aber schon).

Kann man z.B. auch für $\begin{eqnarray*} n=7 = \left[111\right]_2 \end{eqnarray*}$ so anwenden. Benötigt insgesamt vier Modulo-Multiplikationen pro $\begin{eqnarray*} x \end{eqnarray*}$ (zwei für die Berechnung der $\begin{eqnarray*} x_k \end{eqnarray*}$ , und zwei für die Multiplikationen der verschiedenen $\begin{eqnarray*} x_k \end{eqnarray*}$ ), genausoviel wie bei Elvis. Mag nicht für jeden Exponenten $\begin{eqnarray*} n \end{eqnarray*}$ die optimale Vorgehensweise hinsichtlich Minimierung der Multiplikationsanzahl sein, liegt aber mit Größenordnung $\begin{eqnarray*} \log_2(n) \end{eqnarray*}$ in einem Bereich, der ganz Ok ist.

Und das $\begin{eqnarray*} \left(-x\right)^7 = -x^7 \end{eqnarray*}$ spart schon mal nahezu den gesamten Rechenaufwand für die Hälfte aller Restklassen.

Neue Frage »

Antworten »

Kongruenzgleichung lösen

Verwandte Themen