Multiplikativ Inverse in Ringen

02.01.2006, 20:03

sannies

Multiplikativ Inverse in Ringen

Hallo Matheboard,

im Rahmen einer Arbeit für die Uni muss ich an mehreren Stellen multiplikativ Inverse berechnen. Da ich den betreffenden Teil in Hardware baue ist es mir nur schwer möglich den euklidschen Algorhitmus umzusetzen. Ich rechne mit drei Ringen:

1: Zn1 (rechnet im Ring Z mod n1)
2: Zn2 (rechnet im Ring Z mod n2)
3: Zn3 (rechnet im Ring Z mod n3).

zu Zn1 brauch ich das multiplikativ Inverse (n2 * n3) modulo n1
zu Zn2 brauch ich das multiplikativ Inverse (n1 * n3) modulo n2
zu Zn3 brauch ich das multiplikativ Inverse (n1 * n2) modulo n3

Wenn ich jetzt die Zahlen benachbart wähle d.h. n1 = n2 -1; n3 = n2+1 und n2 = 2^n, kommen für mich recht günstige Zahlen heraus (zumindest bei meinen Tests):

für Zn1: n2 / 2
für Zn2: n2 - 1
für Zn3: n2 / 2 + 1

Das funktioniert - soweit ich sehen kann - auch für alle anderen geraden n2 (dadurch werden n1 und n3 teilerfremd), für mich interessant sind allerdings nur die n2 = 2^n (wegen der Einfachkeit in Hardware).
Ich scheiter da auch nur einen Ansatz für den Beweis zu finden, ob es hier jemanden mit eine Idee gibt?

Beste Grüße,
Sebastian

02.01.2006, 20:11

JochenX

Auf diesen Beitrag antworten »

Zitat:

1: Zn1 (rechnet im Ring 0 - n1)

kannst du das näher erläutern?
n1 ist eine natürliche zahl nehme ich an?

geht es dann tatsächlich um den (i.A. Einslosen!) ring n1*Z?
oder eher um Z/(n1*Z)?

verwirrt

02.01.2006, 21:08

sannies

Auf diesen Beitrag antworten »

Ich hab es gerade versucht die Sache in meinem Posting richtigzustellen.

Ich meine einen Ring (zum Teufel - das ist doch ein Ring, Restklassenring!?) von Ganzzahlen mod n.

also Z mod n( = 8):

1 + 3 = 4
4 + 2 = 6
6 + 2 = 0
0 + 8 = 0.
n + 8 = n

Bin mit den Begrifflichkeiten nicht so gut ...

02.01.2006, 23:39

Abakus

Auf diesen Beitrag antworten »

Ich bin nicht sicher, ob ich es richtig verstanden habe. Deine erste Behauptung ist beispielsweise:

$\begin{eqnarray*} 2^{n} * (2^{n} + 1) * \frac{2^{n}}{2}~ mod~ (2^{n} -1) \equiv 1 \end{eqnarray*}$

Das ist für $\begin{eqnarray*} n \ge 2 \end{eqnarray*}$ richtig.

Beweisen läßt sich das durch modulo-Rechnen, du darfst wie folgt rechnen:

$\begin{eqnarray*} (a * b)~ mod~ c \equiv ((a~ mod~ c) * (b~ mod~ c))~ mod~ c \end{eqnarray*}$

Das führt hier zum Ziel:

$\begin{eqnarray*} ((2^{n}~ mod~ (2^{n} -1)) * ((2^{n} + 1)~ mod~ (2^{n} -1)) * \frac{2^{n}}{2})~mod~ (2^{n} -1) \end{eqnarray*}$

$\begin{eqnarray*} = 1 * 2 * \frac{2^{n}}{2}~ mod~ (2^{n} -1) \equiv ... \equiv 1 \end{eqnarray*}$ .

Grüße smile

Abakus

EDIT: die anderen beiden müssten ähnlich überprüfbar sein (ich habe es nicht gemacht).

07.01.2006, 21:36

sannies

Auf diesen Beitrag antworten »

Danke, ich war schon betriebsblind. Hab schon überlegt wie man das mit volständiger Induktion und erweitertem Euklidschen Algorithmus etc ...

Neue Frage »

Antworten »

Multiplikativ Inverse in Ringen

Verwandte Themen