RSA: Müssen p und q identisch sein?

08.12.2010, 15:13

lajao

Auf diesen Beitrag antworten »

RSA: Müssen p und q identisch sein?

Hallo

Wir hatten die Aufgabe, ein Programm zu schreiben, dass mittels RSA einen Text verschlüsselt, danach ein zweites, das mittels RSA entschlüsselt.

Nun hat sich herausgestellt, dass die Verschlüsselung nur funktioniert, wenn p ungleich q ist.
Ist hier ein Fehler in meinem Programm oder ist dies allgemein gültig, dass RSA nicht klappt, wenn p und q identisch sind?

Falls ja, kann das irgendjemand mathematich begründen?
Wieso RSA funktionieren muss, kann man ja mathematisch zeigen. Allerdings sehe ich nicht, wo der vorgang für p=q scheitert.

Vielen Dank für eure Hilfe

btw: glaube, das gehört zu Numerik, falls nicht, bitte an den richtigen Ort verschieben..

lg lajao

08.12.2010, 15:28

René Gruber

Auf diesen Beitrag antworten »

Nur ein Grund: Für zwei Primzahlen $\begin{eqnarray*} p,q \end{eqnarray*}$ ist

$\begin{eqnarray*} \varphi(pq) = \begin{cases} (p-1)(q-1) & \;\mbox{falls}\; p\neq q \\ p(p-1) & \;\mbox{falls}\; p=q \end{cases} \end{eqnarray*}$ .

Damit ist bereits allen weiteren Betrachtungen zum normalen RSA-System im Fall $\begin{eqnarray*} p=q \end{eqnarray*}$ die Basis entzogen.

08.12.2010, 16:06

lajao

Auf diesen Beitrag antworten »

unterscheidet man also beim Berechnen des Schlüssels, ob p=q ist oder eben nicht?

Wir haben den einen Teil des öffentlichen schlüssels mit (p-1)(q-1) definiert. Für p=q wäre dies aber (p^2-2p+1)?

Dehalb vertehe ich nicht ganz, was du meinst smile

smile

08.12.2010, 16:33

René Gruber

Auf diesen Beitrag antworten »

Nochmal:

Zitat:

Original von René Gruber
Damit ist bereits allen weiteren Betrachtungen zum normalen RSA-System im Fall $\begin{eqnarray*} p=q \end{eqnarray*}$ die Basis entzogen.

Ich halte es also für sinnlos, dieses tote Pferd noch weiter zu reiten.

08.12.2010, 16:37

lajao

Auf diesen Beitrag antworten »

Nochmal:

Zitat:

Original von lajao
Deshalb vertehe ich nicht ganz, was du meinst

Reines kopieren hilft mir nicht. Du kannst davon ausgehen, dass ich Antworten lese smile

smile

Aber vlt. gibts ja ein User, der sich zur sinnlosen Tat herablässt, mir die verständlich zu erklären..

08.12.2010, 16:41

René Gruber

Auf diesen Beitrag antworten »

Du scheinst aber nicht die geringste Ahnung davon zu haben, worauf das RSA-Verfahren beruht: Modul $\begin{eqnarray*} N=pq \end{eqnarray*}$ und $\begin{eqnarray*} \varphi(N) \end{eqnarray*}$ müssen teilerfremd sein, sonst geht GAR NIX. Und das sind sie aber im Fall $\begin{eqnarray*} p=q \end{eqnarray*}$ nicht.

Es bringt überhaupt nichts, über das RSA-Verfahren zu fabulieren, wenn man nicht den geringsten Willen zeigt, sich mit dessen Grundlagen auseinanderzusetzen.

Anzeige

08.12.2010, 17:15

lajao

Auf diesen Beitrag antworten »

Nur mal grundsätzlich:
Wenn du jemandem etwas erklärst, ist es schlecht, mit "du bist dumm und verstehst es sowieso nicht, es ist sinnlos, dir das erklären zu wollen" zu argumentieren. Dadurch zeigt man Ignoranz gegenüber der Tatsache, dass man auch mal am Anfang stand, und Arroganz gegenüber seinen Mitmenschen, weil man sich einbildet, was besseres zu sein.

Also bitte, wenn du so denkst, überlass doch das antworten sozialeren Menschen mit Verständnis für die Probleme von Anfängern!

Zitat:

Original von René Gruber
Es bringt überhaupt nichts, über das RSA-Verfahren zu fabulieren, wenn man nicht den geringsten Willen zeigt, sich mit dessen Grundlagen auseinanderzusetzen.

Wodurch unterscheidet sich eine Frage mit ehrlichem Interesse an der Antwort vom Willen, sich mit etwas auseinander zu setzen?
Verzeih mir, wenn ich nicht ausgesprochen autoritätsgläubig bin, aber nur weil etwas auf etwas basiert, fress ich das nicht einfach in mich rein. Als Mathematiker interessiert einen IMMER das wieso, weil es in der Mathematik KEINE Naturgesetze gibt, die man einfach AKZEPTIEREN muss. Dass die beiden Dinger teilerfremd sein müssen, ist KEIN Axiom und KANN und MUSS demnach begründet werden.
Ist so weil ist so ist eine Begründung, die höchstens im Militär Gültigkeit findet!

Zitat:

Du scheinst aber nicht die geringste Ahnung davon zu haben, worauf das RSA-Verfahren beruht

Da liegst du schwer richtig. Deshalb stelle ich FRAGEN und hoffe auf ANTWORTEN, die nicht "du bist sowieso zu dumm" lauten.

Wir haben folgende Beilage erhalten:

Seien p und q beliebige Primzahlen.
Sei m=p*q
Sei f=(p-1)(q-1)
Sei e derart, dass ggT(e,f)=1
Sei d derart, dass e*d=1 mod f

Verschlüsselung: y=x^e mod m, x<m
Entschlüsselung: x=y^d mod m

Die dazugehörige Begründung:

y^d mod m
=(x^e)^d mod m
=x^(d*e) mod m
=x^(k*f+1) mod m
=(x^f)^k*x mod m
=(1^k) * x mod m
=x mod m
=x (weil 0<x<m)

HIER kann ich nicht sehen, wieso p ungleich q sein soll, da wir das eigentlich nirgends explizit vorausgesetzt haben (zumindest nicht so offensichtlich, dass ich es sehen würde). Die einzige Vorausetzung ist 0<x<m, was bei einem genügend grossen p mit m=p^2 erfüllt wäre..

Meine Frage ist nun nicht, wie wenig Ahnung ich habe, wie dumm ich bin, oder wie einfach das Problem ist!
Mir würde reichen, wenn mir jemand sagen könnte, in welcher Zeile sich die Voraussetzung p ungleich q versteckt.

vlt. findet sich ja jemand, dem dies nicht sinnlos erscheint..

lg lajao

PS: Ich entschuldige mich, dass ich mich für was interessiere, was ich noch nicht verstehe. Vlt. wärs besser, dumm zu bleiben verwirrt

verwirrt

08.12.2010, 18:01

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von René Gruber
Wodurch unterscheidet sich eine Frage mit ehrlichem Interesse an der Antwort vom Willen, sich mit etwas auseinander zu setzen?

Z.B. darin, dass du das obige $\begin{eqnarray*} \varphi(p^2) = p(p-1) \end{eqnarray*}$ ignoriert hast und weiter mit dem falschen $\begin{eqnarray*} \varphi(p^2) = (p-1)^2 = p^2-2p+1 \end{eqnarray*}$ argumentierst (das ist es nämlich, womit du im Fall p=q operierst).

Du musst dich tiefer mit der Eulerschen Phi-Funktion $\begin{eqnarray*} \varphi \end{eqnarray*}$ befassen, wenn du die Interna des RSA-Verfahrens verstehen willst. Und schon bei diesen Grundlagen wird klar, dass ein auf $\begin{eqnarray*} N=pq \end{eqnarray*}$ basierendes RSA-Verfahren nur funktionieren kann, wenn $\begin{eqnarray*} N \end{eqnarray*}$ und $\begin{eqnarray*} \varphi(N) \end{eqnarray*}$ teilerfremd sind. Ja, ich weiß, ich wiederhole mich schon wieder - glaub mir, ich mach das nicht gern. unglücklich

unglücklich

08.12.2010, 18:20

Math1986

Auf diesen Beitrag antworten »

Es hat keiner gesagt, dass du dumm bist oder so etwas in der Richtung, es ist also allein dein Problem wenn du da so etwas hereininterpretierst

Die Begründung steht im ersten Beitrag von René Gruber:

Zitat:

Original von René Gruber
Nur ein Grund: Für zwei Primzahlen $\begin{eqnarray*} p,q \end{eqnarray*}$ ist

$\begin{eqnarray*} \varphi(pq) = \begin{cases} (p-1)(q-1) & \;\mbox{falls}\; p\neq q \\ p(p-1) & \;\mbox{falls}\; p=q \end{cases} \end{eqnarray*}$ .

Damit ist bereits allen weiteren Betrachtungen zum normalen RSA-System im Fall $\begin{eqnarray*} p=q \end{eqnarray*}$ die Basis entzogen.

das geht bei dir in deiner Argumentation an folgender Stelle ein:

Zitat:

Original von lajao
Seien p und q beliebige Primzahlen.
Sei m=p*q
Sei f=(p-1)(q-1)
Sei e derart, dass ggT(e,f)=1
Sei d derart, dass e*d=1 mod f

Falls p=q, dann wäre f=p(q-1)

Des Weiteren

Zitat:

Original von René Gruber
Modul $\begin{eqnarray*} N=pq \end{eqnarray*}$ und $\begin{eqnarray*} \varphi(N) \end{eqnarray*}$ müssen teilerfremd sein, sonst geht GAR NIX. Und das sind sie aber im Fall $\begin{eqnarray*} p=q \end{eqnarray*}$ nicht.

Für p=q sind $\begin{eqnarray*} \varphi(p\cdot q)=q\cdot\left(p-1\right) \end{eqnarray*}$ und $\begin{eqnarray*} q\cdot p \end{eqnarray*}$ offenbar NICHT teilerfremd, da beides Vielfache von q sind.

, und damit fällt deine Argumentation

Bevor du auch nur damit anfängst, ein Programm zu schreiben, solltest du den dahinterstehenden Algorythmus verstanden haben, sonst kommst du nicht weit

08.12.2010, 18:32

lajao

Auf diesen Beitrag antworten »

Zitat:

unterscheidet man also beim Berechnen des Schlüssels, ob p=q ist oder eben nicht?

Demnach kann man nun endlich diese Frage mit Ja beantworten smile

smile

Wenn ich dich richtig verstanden hab.

f wird also mittels Eulersche Phi-Funktion berechnet? Demnach wäre in unsrem skript ein Fehler, aber das ist ja nicht unmöglich.

In unsrem Skript wird Eulersche Phi-Fkt nicht erwähnt. Weder im Zusammenhang mit Schlüsselsuche noch im Zusammenhang mit Begründung der Entschlüsslung.

Allerdings sehe ich immer noch nicht, wo in der oberen Beweiskette dies eine Rolle spielt. Ich mein, wenn ich m so berechne, wie es in unsrer Beilage stand, ist es ja anscheinend falsch. Demnach sollte ich einen Widerspruch erzeugen können, also iwo zwischen y^d mod m und =x mod m ist ein Gleichzeichen falsch. Zwar entsprechen meine Versuche dieser Theorie, doch Versuche sind keine Beweise.

Oder sehe ich dies komplett falsch und f hat gar nix mit Phi zu tun?

Hab mir mal den Wikipedia-Eintrag angeguckt und sehe nicht, wieso f die Anzahl teilerfremder Zahlen sein soll. Den Zusammenhang zwischen der Verschlüsslung und der Anzahl teilerfremder Zahlen ist mir suspekt.

Zitat:

Z.B. darin, dass du das obige $\begin{eqnarray*} \varphi(p^2) = p(p-1) \end{eqnarray*}$ ignoriert hast und weiter mit dem falschen $\begin{eqnarray*} \varphi(p^2) = (p-1)^2 = p^2-2p+1 \end{eqnarray*}$ argumentierst (das ist es nämlich, womit du im Fall p=q operierst).

zum ersten Teil dieser Antwort:
Diese Stelle wurde von mir ignoriert, weil nach Nachfrage meinerseits statt einer Erklärung nur ein copy paste kam. Das ist im allgemeinen NICHT HILFREICH
Ausserdem zeigt schon das Stellen der Frage, dass jemand WILLEN zeigt. (und das wäre das Gegenteil von NICHT den geringsten Willen zeigen)

du sagst, ich operiere im Fall von p=q mit dem falschen Phi. Weisst du auch wo, resp. wo der Fehler entsteht? Denn das ist eigentlich die Frage, die ich schon seit Anfang Thread stelle, wenn zu Beginn zugegebenermassen auch etwas unklar, doch die Hauptfrage bleibt: Wo entsteht der Fehler bei p=q?
Mir ist egal, ob p ungleich q eine Voraussetzung ist. Mir ist auch egal, was du von meinem Wissensstand denkst, denn arrogante herablassende Menschen hab ich noch nie gemocht. Du scheinst anscheinend meine Fragen falsch zu verstehen, denn du bringst immer dasselbe, was aber an der Frage vorbeizielt. Es ist egal, ob du die Frage absichtlich oder nicht absichtlich falsch verstehst, du verstehst sie nicht und das ist, was zählt.

Das Matheboard ist eine Community mit vielen sozialen Menschen, die sich auch die Mühe machen, auf eine Frage so zu antworten, wie sie gestellt wurde. Vlt. sollten wir unsere Diskussion unterbrechen und auf eine Drittmeinung warten? Denn mit deinem Erklärstil komm ich einfach nicht zurecht.

Nix für ungut, aber ich mags nicht, von jemandem als dumm bezeichnet zu werden, der nicht mal meine Fragen versteht!

lg lajao

edit: Danke Math, ich hab das Gefühl, ich nähere mich langsam dem Problem.

Mal grundsätzlich, ich hab den Algorithmus nicht entworfen oder sonst was. Die Anweisungen, die ich oben aufgeschrieben hab, stammen von unserem Prof.

Zwei Aussagen von Gruber, die mich störten:
1. Es bring nix, dieses tote Pferd weiterzureiten
2. Es bringt überhaupt nix, [...] nicht den geringsten Willen zeigt [...]

Die erste Aussage bleibt Interpretationssache, für mich ist sie einfach arrogant. Die zweite heisst eigentlich, es bringt nix, mit dir zu argumentieren, weil du sowieso keine Ahnung von den Grundlagen hast.

Doch du hast recht, vlt. ist unwissend das bessere Wort als dumm smile

smile

Fakt bleibt, dass sein Erklärungsstil arrogant und wenig hilfreich ist. Das bin ich mir aus dem Matheboard einfach nicht gewöhnt, also entschuldige meine Ausdrucksweise.

Nachdem ich nun weiss, dass unser Prof f falsch definiert hat, möchte ich nur noch wissen, wo beim Beweis für die Entschlüsslung der Trugschluss liegt. Schliesslich muss man doch iwo verwenden, dass f Phi(pq) ist? Ich seh aber nicht wo

Zitat:

Die dazugehörige Begründung:

y^d mod m
=(x^e)^d mod m
=x^(d*e) mod m
=x^(k*f+1) mod m
=(x^f)^k*x mod m
=(1^k) * x mod m
=x mod m
=x (weil 0<x<m)

08.12.2010, 18:39

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von lajao
Nix für ungut, aber ich mags nicht, von jemandem als dumm bezeichnet zu werden, der nicht mal meine Fragen versteht!

Und ich mag es nicht, wenn Leute mit diesem dämlichen sozialen Gelaber daherkommen, wo sie sich stundenlang Zeit nehmen, das seitenlang auszubreiten - statt die Zeit lieber auf die mathematische Inhalte zu verwenden. Und jetzt kannst du dich gern empört auch darüber echauffieren, mir egal - meine Zeit hier im Thread ist beendet. Wink

Wink

08.12.2010, 18:42

Math1986

Auf diesen Beitrag antworten »

Hast du meinen Beitrag oben nicht gelesen oder ihn nicht verstanden?

Zitat:

Original von lajao

Zitat:

Z.B. darin, dass du das obige $\begin{eqnarray*} \varphi(p^2) = p(p-1) \end{eqnarray*}$ ignoriert hast und weiter mit dem falschen $\begin{eqnarray*} \varphi(p^2) = (p-1)^2 = p^2-2p+1 \end{eqnarray*}$ argumentierst (das ist es nämlich, womit du im Fall p=q operierst).

zum ersten Teil dieser Antwort:
Diese Stelle wurde von mir ignoriert, weil nach Nachfrage meinerseits statt einer Erklärung nur ein copy paste kam. Das ist im allgemeinen NICHT HILFREICH

Okay, das kannst du sehr einfach selbst überprüfen und etwas Eigeninitiative zeigen:

Zitat:

Original von René Gruber
Nur ein Grund: Für zwei Primzahlen $\begin{eqnarray*} p,q \end{eqnarray*}$ ist

$\begin{eqnarray*} \varphi(pq) = \begin{cases} (p-1)(q-1) & \;\mbox{falls}\; p\neq q \\ p(p-1) & \;\mbox{falls}\; p=q \end{cases} \end{eqnarray*}$ .

Damit ist bereits allen weiteren Betrachtungen zum normalen RSA-System im Fall $\begin{eqnarray*} p=q \end{eqnarray*}$ die Basis entzogen.

Nimm mal p=q=2,p=q=5,p=q=7,p=q=11.... was fällt dir auf?

Zitat:

Original von lajao
Hab mir mal den Wikipedia-Eintrag angeguckt und sehe nicht, wieso f die Anzahl teilerfremder Zahlen sein soll.

Komisch, das steht direkt in der ersten Zeile: Eulerschen Phi-Funktion
Das ist exakt die Definition der Phi-Funktion

Solltest du deinen Ton nicht ändern dann bin ich auch gleich weg

08.12.2010, 18:43

lajao

Auf diesen Beitrag antworten »

Zitat:

dämlichen sozialen Gelaber daherkommen, wo sie sich stundenlang Zeit nehmen, das seitenlang auszubreiten - statt die Zeit lieber auf die mathematische Inhalte zu verwenden.

sowas nennt man erklären. Allgemein macht man das, wenn man einer Person helfen möchte.

Das mag vlt. in einer Doktorarbeit unnötig sein, doch im REALEN Leben ist es echt hilfreich smile

smile

Trotzdem Danke für deine "Hilfe". Immerhin hast du dir Zeit genommen, auch wenns nix gebracht hat smile

smile

lg

edit:

Zitat:

Zitat:
Original von lajao
Hab mir mal den Wikipedia-Eintrag angeguckt und sehe nicht, wieso f die Anzahl teilerfremder Zahlen sein soll.
Komisch, das steht direkt in der ersten Zeile: Eulerschen Phi-Funktion
Das ist exakt die Definition der Phi-Funktion

Jo, ich weiss dass das die Definition der Phi Fkt ist. Die Frage ist nur, was das in unsrer Definition unseres RSA-Algorithmus zu suchen hat. Mit f mein ich nicht die Phi-Fkt. Sondern das f, dass auf unserem Skript stand, mit dem auch gerechnet wird.

Mir ist auch BEWUSST, dass die Phi Funktion anders aussehen muss, wenn p=q ist. Allerdings sehe ich den Zusammenhang zwischen Phi und unsrem RSA NICHT und genau das ist mein Problem. In unserem gesamten Skript steht nix von wegen Phi-Fkt.

PS: Sry, wenn ich mich im ton vergriffen habe, doch ich mags nicht, schlecht behandelt zu werden. Auch wenn mir jemand hilft..
Zudem bin ich nicht der einzige, der sich so fühlt, wie eine PN bestätigt, die ich kurz nach meiner zweiten Antwort erhielt ...

08.12.2010, 18:55

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von lajao

Zitat:

Zitat:
Original von lajao
Hab mir mal den Wikipedia-Eintrag angeguckt und sehe nicht, wieso f die Anzahl teilerfremder Zahlen sein soll.
Komisch, das steht direkt in der ersten Zeile: Eulerschen Phi-Funktion
Das ist exakt die Definition der Phi-Funktion

Jo, ich weiss dass das die Definition der Phi Fkt ist. Die Frage ist nur, was das in unsrer Definition unseres RSA-Algorithmus zu suchen hat. Mit f mein ich nicht die Phi-Fkt. Sondern das f, dass auf unserem Skript stand, mit dem auch gerechnet wird.

Mir ist auch BEWUSST, dass die Phi Funktion anders aussehen muss, wenn p=q ist. Allerdings sehe ich den Zusammenhang zwischen Phi und unsrem RSA NICHT und genau das ist mein Problem. In unserem gesamten Skript steht nix von wegen Phi-Fkt.

Schau dich in der Literatur um: Du MUSST diese Phi-Funktion verwenden, weil die Anzahl der teilerfremden Zahlen entscheident ist, und du die brauchst
Wenn dein Skript das nicht erwähnt (und das gehört zu den Grundlagen), dann ist es einfach nur grottenschlecht

08.12.2010, 19:06

lajao

Auf diesen Beitrag antworten »

Zitat:

Wenn dein Skript das nicht erwähnt (und das gehört zu den Grundlagen), dann ist es einfach nur grottenschlecht

es ist auch keine wirkliche Numerikvorlesung. Eigentlich sollte uns der Umgang mit Matlab beigebracht werden. Die Begründung war einfach noch dazugelegt. Dementsprechend wurde sie auch nicht richtig erklärt. (zumindest ohne Phi)

Zitat:

Schau dich in der Literatur um: Du MUSST diese Phi-Funktion verwenden, weil die Anzahl der teilerfremden Zahlen entscheident ist, und du die brauchst

aber wo?
Ich habe hier eine vollständige Begründung, wieso die Entschlüsselung funkioniert :

Zitat:

y^d mod m
=(x^e)^d mod m
=x^(d*e) mod m
=x^(k*f+1) mod m
=(x^f)^k*x mod m
=(1^k) * x mod m
=x mod m
=x (weil 0<x<m)

wo mach ich hier die Annahme, dass f die Anzahl teilerfremder Zahlen ist?

08.12.2010, 19:26

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von lajao
Ich habe hier eine vollständige Begründung, wieso die Entschlüsselung funkioniert :

Zitat:

y^d mod m
=(x^e)^d mod m
=x^(d*e) mod m
=x^(k*f+1) mod m
=(x^f)^k*x mod m
=(1^k) * x mod m
=x mod m
=x (weil 0<x<m)

wo mach ich hier die Annahme, dass f die Anzahl teilerfremder Zahlen ist?

Die Begründung scheitert schon vorher:

Zitat:

Sei e derart, dass ggT(e,f)=1
Sei d derart, dass e*d=1 mod f

Wo hast du gezeigt, dass derartige d und e existieren?

08.12.2010, 19:47

Cugu

Auf diesen Beitrag antworten »

Zitat:

wo mach ich hier die Annahme, dass f die Anzahl teilerfremder Zahlen ist?

Warum sollte $\begin{eqnarray*} (x^f)^k\cdot x \equiv 1^k \cdot x \mod m \end{eqnarray*}$ gelten, wenn $\begin{eqnarray*} f \end{eqnarray*}$ nicht die Phi-Funktion ist?

08.12.2010, 19:50

lajao

Auf diesen Beitrag antworten »

Zitat:

Die Begründung scheitert schon vorher:

Zitat:
Sei e derart, dass ggT(e,f)=1
Sei d derart, dass e*d=1 mod f

Wo hast du gezeigt, dass derartige d und e existieren?

Beispiel: Ich nehme e=1 und d=f+1

Dann gilt: ggT(e,f)=1 und e*d=1*d=f+1=1 mod f

Also existieren immer solche e und d, unabhängig von f?

oder hab ich irgendwo einen Fehler drin?

08.12.2010, 19:54

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von lajao

Zitat:

Die Begründung scheitert schon vorher:

Zitat:
Sei e derart, dass ggT(e,f)=1
Sei d derart, dass e*d=1 mod f

Wo hast du gezeigt, dass derartige d und e existieren?

Beispiel: Ich nehme e=1 und d=f+1

Dann gilt: ggT(e,f)=1 und e*d=1*d=f+1=1 mod f

Also existieren immer solche e und d, unabhängig von f?

oder hab ich irgendwo einen Fehler drin?

Ja, es muss e>1 gelten...

08.12.2010, 19:58

Cugu

Auf diesen Beitrag antworten »

Sonst wird trivial...

Das viel größere Problem ist aber, dass im Allgemeinen $\begin{eqnarray*} (x^f)^k\cdot x \equiv 1^k \cdot x \mod m \end{eqnarray*}$ nicht gilt!

08.12.2010, 20:08

lajao

Auf diesen Beitrag antworten »

e>1 stand nicht auf unsrem Blatt, aber das wundert mich mittlerweilen auch nicht mehr.

Die oben beschriebene Umformung wurde bei uns mit Euler-Satz erklärt. Hab natürlich angenommen, dass unser Prof Sätze richtig anwendet, doch anscheinend hat er gedacht, Phis würden uns das Gehirn verderben.
Jo, Wikipedia meint, Eulersatz gilt für Phi(N) und nicht für x^(q-1)(p-1) -.-

Dadurch hat sich mein Problem erledigt.

Vielen Dank an alle smile

smile

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »