+1 Daumen
48 Aufrufe

Aufgabe:

Im Zuge des RSA VErfahrens soll ich eine Nachricht m = 42 für N = 221 mit dem Public KEy (23,221) verschlüsseln.

Also lautet die Verschlüsselung 42^23 ist kongruent Modulo x zu mod 221.

Das x gilt es zu bestimmen. 
Problem/Ansatz:

Meine Frage, gibt es eine Möglichkeit dies ohne Taschenrechner schnell und effizient zu rechnen? Mir fällt da nur Square und Multiply ein, wobei man dort schon im dritten Schritt dann 672*672 rechnet, was in einer Klausurzeit von 5 Min für die ganze Verschlüsselungsaufgabe utopisch ist. Danke im Voraus.

von

Wie ist man jetzt von 15*15 = 225 auf 17 und 13 als Primzahlen gekommen?

15²-2² (also 225 - 4) ist nach der dritten binomischen Formel immer noch

(15+2)(15-2).

1 Antwort

0 Daumen

Wegen 15*15=225 und 221=225-4 ist 221=17*13.

Um 4223 mod 221 zu berechnen ist es hilfreich zu wissen, was 4223 mod 17 und 4223 mod 13 ergibt.

von 10 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community