Frage von LarrySr, 17

"Square&Multiply"-Algorithmus bei negativen Exponenten?

Wie kann ich Aufgaben mit negativen Exponenten (Bsp: (2^-43)mod13) mithilfe des "Square&Multiply"-Algorithmus lösen?

Bei positiven Exponenten ist es kein Problem, allerdings weiß ich nicht, wie ich einen negativen Exponenten in die nötige binäre Form bringen soll.

Danke im Voraus.

Antwort
von Schachpapa, 8

2^-1 mod 13 (also das multiplikative Inverse zu 2) ist 7, denn (7*2) mod 13 = 1

Bin mir nicht ganz sicher, ob man  dann sagen darf:
2^-43 mod 13 = 7^43 mod 13 = 6

Dann müsstest du also zuerst das Inverse ausrechnen (mit dem erweiterten Euklid) und dann Square&Multiply.

Antwort
von iokii, 10

2^-43 mod 13=2^-43, es ist ja schließlich eine Zahl, die kleiner als 1, und somit auch kleiner als 13 ist.

Keine passende Antwort gefunden?

Fragen Sie die Community