Reduktion

[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]

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)