Kongruenz Potenz für Generatoren einer Gruppe

19.01.2013, 13:15

barracuda317

Kongruenz Potenz für Generatoren einer Gruppe

Sei $\begin{eqnarray*} p \end{eqnarray*}$ eine Primzahl, $\begin{eqnarray*} g \end{eqnarray*}$ Generator von ( $\begin{eqnarray*} \mathbb{Z}_p^* \end{eqnarray*}$ )

Es gilt $\begin{eqnarray*} x \end{eqnarray*}$ kongruent $\begin{eqnarray*} y \end{eqnarray*}$ mod ( $\begin{eqnarray*} p-1 \end{eqnarray*}$ )

Zu zeigen ist:

$\begin{eqnarray*} g^x \end{eqnarray*}$ kongruent $\begin{eqnarray*} g^y \end{eqnarray*}$ mod $\begin{eqnarray*} p \end{eqnarray*}$

Soweit habe ich die Aufgabe nun schon auseinandergefriemelt. Aber irgendwie seh ich nicht, wie ich das begründen kann. Jemand einen Tip?

20.01.2013, 12:33

tmo

Auf diesen Beitrag antworten »

Was bedeutet denn $\begin{eqnarray*} x \equiv y \mod{p-1} \end{eqnarray*}$ per Definition?

Und was kannst du basierend darauf über $\begin{eqnarray*} g^{x-y} \mod p \end{eqnarray*}$ aussagen?

PS: Die Information, dass $\begin{eqnarray*} g \end{eqnarray*}$ Erzeuger ist, ist übrigens redundant. Dies ist eher für die (hier nicht gefragte) Rückrichtung interessant.

21.01.2013, 09:16

barracuda317

Auf diesen Beitrag antworten »

Zitat:

Original von tmo
Was bedeutet denn $\begin{eqnarray*} x \equiv y \mod{p-1} \end{eqnarray*}$ per Definition?

Und was kannst du basierend darauf über $\begin{eqnarray*} g^{x-y} \mod p \end{eqnarray*}$ aussagen?

PS: Die Information, dass $\begin{eqnarray*} g \end{eqnarray*}$ Erzeuger ist, ist übrigens redundant. Dies ist eher für die (hier nicht gefragte) Rückrichtung interessant.

Per Definition gilt

$\begin{eqnarray*} x \equiv y \mod{p-1} \Rightarrow \exists k \in \mathbb{Z}: x-y = k (p-1) \end{eqnarray*}$

Aber was mit das bei $\begin{eqnarray*} g^{x-y} \mod p \end{eqnarray*}$ leuchtet mir noch nicht an.

21.01.2013, 12:30

barracuda317

Auf diesen Beitrag antworten »

Zitat:

Original von barracuda317

Zitat:

Da wir wissen, dass $\begin{eqnarray*} b*h \equiv a \mod{p-1} \Rightarrow \exists k \in \mathbb{Z}: bh-a = k (p-1) \end{eqnarray*}$

$\begin{eqnarray*} bh-a = k (p-1) \iff bh = k (p-1) + a \end{eqnarray*}$

Dann erhalten wir

$\begin{eqnarray*} (g^b)^h \equiv g^a \mod p \end{eqnarray*}$

$\begin{eqnarray*} \iff g^{bh} \equiv g^a \mod p \end{eqnarray*}$

$\begin{eqnarray*} \iff g^{k*(p-1)+a} \equiv g^a \mod p \end{eqnarray*}$

$\begin{eqnarray*} \iff (g^{p-1})^k * g^a\equiv g^a \mod p \end{eqnarray*}$

$\begin{eqnarray*} \iff 1^k*g^a \equiv g^a \mod p \end{eqnarray*}$

$\begin{eqnarray*} \iff g^a \equiv g^a \mod p \end{eqnarray*}$

Neue Frage »

Antworten »

Kongruenz Potenz für Generatoren einer Gruppe

Verwandte Themen