Reduktion

Moderator: Einführung in die Kryptographie

LucasR
Kernelcompilierer
Kernelcompilierer
Beiträge: 474
Registriert: 9. Jun 2009 09:55

Reduktion

Beitrag von LucasR »

Aus meiner Mitschrift der Vorlesung am 15.12.2010:
Reduktion: Um Problem A zu Lösen, genügt es, Problem B zu lösen.
z.B.: "Um den RSA-Modul zu faktorisieren, genügt es, RSA entschlüsseln zu können."
Wenn dies Stimmen würde, wäre RSA sicher, solange es unmöglich ist, den RSA-Modul zu faktorisieren.
Sorum gilt nach meinem Verständniss die Reduktion an dieser Stelle nicht. Andersrum würde die Reduktion allerdings gelten, oder? Also genau genommen:
"Um RSA entschlüsseln zu können, genügt es, den RSA-Modul faktorisieren zu können."

bashFish
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 3. Okt 2007 17:38

Re: Reduktion

Beitrag von bashFish »

Vor allem gab es in diesem Kontext noch die Formel
A => B <=> not B => not A

In dieser Vorlesung wurde gezeigt, dass man n faktorisieren kann, wenn man Schluesseltexte entschluesseln kann.

D.h. es gilt : "entschluesseln koennen => n faktorisieren koennen" oder eben die Formulierung mit Negaten:
"nicht n faktorisieren koennen => nicht entschluesseln koennen" (was zu zeigen war)

Antworten

Zurück zu „Einführung in die Kryptographie“