15^12 mod 13 mit binärer Exponentiation rechnen |
| 10.12.2016, 11:35 | ominös | Auf diesen Beitrag antworten » |
| 15^12 mod 13 mit binärer Exponentiation rechnen Hallo ich möchte mittels Binärer Exponentation 15 ^ 12 mod 13 schriftlich rechnen. Meine Ideen: ich rechne die 12 binär um -> 1 1 0 0 Bei 1 quadriere und multipliziere ich und bei 0 multipliziere ich nur. also QM QM M M 1^2 mod 15 = 1 1*15 = 15, 15 mod 13 = 2 2^2 = 4, 4 mod 13 = 4 4*15 = 60, 60 mod 13 = 8 8*15 = 120, 120 mod 13 = 3 3*15 = 45, 45 mod 13 = 6 !! Ich bekomm 6 raus aber das Ergebnis müsste doch 1 sein. Was mache ich denn Falsch, bei anderen Zahlen klappt diese Rechenweise meist. Vielen Dank für eure Bemühungen. Gruß Ominös |
||
| 10.12.2016, 11:48 | Elvis | Auf diesen Beitrag antworten » |
Das sieht interessant aus. Kannst Du diesen Algorithmus allgemein beschreiben, begründen, seine Richtigkeit beweisen ? Wenn eine Rechenweise "meist" klappt, heißt das, dass sie nicht allgemein gültig ist ? |
||
| 10.12.2016, 12:02 | ominös | Auf diesen Beitrag antworten » |
Mein Fehler, ich habe es soeben bemerkt, natürlich geht der Algorithmus nicht QM QM M M sondern statt M muss man Quadrieren also QM QM Q Q . So passt es auch: 1^2 mod 15 = 1 1*15 = 15, 15 mod 13 = 2 2^2 = 4, 4 mod 13 = 4 4*15 = 60, 60 mod 13 = 8 8^2 = 64 , 64 mod 13 = 12 12^2 = 144, 144 mod 13 = 1!!! !! Oh Oh Oh, ich sollte aufhören für heut 
sorry 
|
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
