Chinesischer Restesatz

20/03/2008 - 00:37 von Bernd Schneider | Report spam
Hi,

ich habe mal eine ganz einfache Frage zum chinesischen Restsatz und seiner
Anwendung zur Entschlüsslung im Falle von RSA. Seien p,q prim und
m^{ed-1} = 1 (mod p)
m^{ed-1} = 1 (mod q)

Wieso gilt jetzt nach dem Chinesischen Restsatz:
m^{ed-1} = 1 (mod pq)
Muss ich dazu nicht wie folg berechnen:
m^{ed-1} = 1 * q * (q^{-1} mod p) + 1 * p * (p^{-1} mod q) (mod n)

Aber wieso sollte der zweite Teil jetzt = 1 sein?

Grüsse,
Bernd
 

Lesen sie die antworten

#1 Jens Voß
20/03/2008 - 09:15 | Warnen spam
On 20 Mrz., 00:37, Bernd Schneider wrote:
Hi,

ich habe mal eine ganz einfache Frage zum chinesischen Restsatz und seiner
Anwendung zur Entschlüsslung im Falle von RSA. Seien p,q prim und
m^{ed-1} = 1 (mod p)
m^{ed-1} = 1 (mod q)

Wieso gilt jetzt nach dem Chinesischen Restsatz:
m^{ed-1} = 1 (mod pq)



Das ist ein viel allgemeinerer Sachverhalt:

Ist

a = 1 (mod p)
a = 1 (mod q)

so ist dies gleichbedeutend mit

a - 1 = 0 (mod p)
a - 1 = 0 (mod q)

Mit anderen Worten, sowohl p als auch q sind Teiler von a - 1.
Sind nun p und q *verschiedene* Primzahlen (hast Du zwar oben nicht
vorausgesetzt, sollte aber besser gelten), so ist auch pq ein Teiler
von a - 1 (grundlegende Eigenschaft von Primzahlen), d.h.

a - 1 = 0 (mod pq)

oder

a = 1 (mod pq)

qed.

Schönen Gruß,
Jens

Ähnliche fragen