Modulo Rechnung

Für (a) suchen wir ja quasi das multiplikative Inverse von 17, also eine Zahl a, sodass a*17=1 mod71. Man kann das theoretisch durch Ausprobieren lösen, schließlich kommen nur 70 Zahlen in Frage. Was wahrscheinlich "erwünschter" ist, ist der euklidische Algorithmus.

Dieser findet die Zahlen s&t für die Gleichung

ggt(a,b)=sa+tb (wobei a und b irgendwelche natürlichen Zahlen sind und der ggt der größte, gemeinsame Teiler).

 

Den Euklid-Algorithmus hier ganz zu erklären wär evtl. etwas viel, du findest eine ganz nette Erklärung auf Wiki:

https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus

und wahrscheinlich auch in eurem Skript zur Vorlesung, falls da eins existiert.

 

Da 71 eine Primzahl ist, ist ggt(71,17)=1. Der Euklid-Algorithmus liefert

1 = 6*71-25*17

(Ehrlicherweise habe ich das einen Online-Rechner machen lassen, diesen hier: https://de.planetcalc.com/3299/)

 

Modulo 71 sieht das dann so aus:

1 = 6*71 -25*17

1 = 46*17

 

Also ist 46 das gesuchte multiplikative Inverse.

 

Für die (b) sei das Stichwort "square&multiply" genannt. Man könnte natürlich mit 21 starten, mit 21 multiplizieren, das dann mod 43, dann mit 21 multiplizieren etc. - einfacher und effizienter ist folgendes Vorgehen:

 

\(21^{35} = 21 \cdot 21^{34} = 21 \cdot (21^2)^{17} = \\ 21 \cdot 441^{17} = 21 \cdot 11^{17} = 21 \cdot 11 \cdot 11^{16} = \\ 231 \cdot (11^2)^8 = 16 \cdot 121^8 = 16 \cdot 35^8 = 16 \cdot (35^2)^4 = \\ 16 \cdot 1225^4 = 16 \cdot 21^4 = 16 \cdot (21^2)^2 =16 \cdot 441^2 = 16 \cdot 11^2 = 16 \cdot 121 = 16 \cdot 35 = 560 = 1\)

 

Man erkennt: ist der Exponent ungerade, so ziehe ich die Zahl einmal als Faktor davor. Ist der Exponent gerade, so wird erstmal quadriert. Sobald eine Zahl größer 43 vorkommt, wird mod43 reduziert.

 

Ich hoff' das hilft weiter! Frag gern nochmal nach falls noch Wünsche offen sind ;)

Auf alle Fälle schonmal vielen dank für deine Antwort,

kannst du mir bitte noch erkläre wie du bei der (b) in der zweiten zeile auf 11^17 gekommen bist?