Kann man den Satz von Euler-Fermat auch anders schreiben?

Erste Frage Aufrufe: 62     Aktiv: 08.01.2023 um 00:29

0
Hallo zusammen. Meine Frage ist, ob ich den Satz von Euler-Fermat auch anders schreiben kann. Korrekt lautet er ja: a^ϕ(n) ≡ 1 mod n. Ich wollte fragen, ob ich in nicht auch so: a^ϕ(n) mod m = 1 , oder ob ich so: a^ϕ(n) mod m = 1 mod n schreiben darf.
Vielen Dank im voraus.
Diese Frage melden
gefragt

Punkte: 10

 
Kommentar schreiben
1 Antwort
0
Was hat denn das $m$ da zu suchen? Es sind beide Schreibweisen, also $a^{\varphi(n)}\equiv 1\mod n$ und $a^{\varphi(n)}\mod n = 1$, üblich. Man sollte allerdings nicht zwischen den Schreibweisen hin und her springen.
Diese Antwort melden
geantwortet

Selbstständig, Punkte: 26.64K

 

Wollte n schreiben   ─   astroboy187 07.01.2023 um 23:25

Du hast mir damit sehr geholfen. Ich habe noch eine Frage und zwar kann ich dann mit a^ϕ(n) mod n = 1 einfach, dort wo (m^φ(N) mod N)^k steht, es damit ersetzen oder? Dabei handelt es sich um den RSA-Beweis. Vielen Dank im Voraus.

c^d mod N = (m^e mod N)^d mod N
= (m^e)^d mod N
= m^ed mod N

Das „e*d“ können wir ersetzten durch die Gleichung des multiplikativen Inversen. Diese lautet, da ein k aus den ganzen Zahlen existiert, folgendermaßen: e*d = k * φ(N) + 1.

Also folgt:
= m^k•φ(N)+1 mod N
= m^k•φ(N) • m mod N
= (m^φ(N))^k • m mod N
= ((m^φ(N))^k mod N) • (m mod N) mod N
= (m^φ(N) mod N)^k • (m mod N) mod N
= (1^k mod N) • (m mod N) mod N => wegen des Satzes Euler-Fermat
= 1 • m mod N
= m => wegen m < N
  ─   astroboy187 07.01.2023 um 23:39

Es fehlt zur korrekten Angabe des Satzes von EF auch noch der Vorspann "für alle $a,n$ mit $ggt(a,n)=1$ gilt".
Und in den obigen Überlegungen fehlen auch wieder Angaben zu $m, N$. Diese Dinge sind genauso wichtig wie die Gleichungen selbst.
  ─   mikn 07.01.2023 um 23:43

Ich habe vergessen zu erwähnen, dass vorausgesetzt wird, dass m und N teilerfremd sind. Somit kann ich es doch ersetzen durch die Gleichung: a^ϕ(n) mod n = 1, sodass (1^k mod N) ensteht.   ─   astroboy187 08.01.2023 um 00:07

Kommentar schreiben