Hey,
kann mir jemand sagen wie ich den Wert “13^15 mod 17” in Java berechnen kann?
Ich habe folgenden Ausdruck benutzt “double res=Math.pow(13, 15) % 17;”, aber es kommt ein falsches Ergebnis (res=7.0) raus…
Das richtige Ergebnis ist 4.0.
Danke!
Rechnungen mit primitiven Gleitkomma-Zahlen sind per se ungenau. Rechne mit BigDecimals.
bye
TT
Für so große Zahlen kannst du BigInteger nutzen:
BigInteger thirteen = BigInteger.valueOf(13);
BigInteger seventeen = BigInteger.valueOf(17);
BigInteger res = thirteen.pow(15).mod(seventeen);
Es gibt auch die Methode BigInteger.modPow(BigInteger, BigInteger) welche dafür genutzt wird. Der Unterschied zur Variante von EikeB ist das modPow() zwei BigInteger-Objekte nimmt wogegen BigInteger.pow() nur mit einem int arbeitet was (wenn auch unwahrscheinlich da es dann schon wirklich eine extre riesige Zahl wäre) dann bei 2^31-1 (2,1Mrd) wieder ans Limit kommt.
Spontan erinnert mich die Formel “m^e mod n” an RSA, hats damit was zu tun ?
int res = 1;
for(int i=1;i<=15;i++){
res = (13 * res) % 17;
}
oder eben ausnutzen, dass
13=-4 (mod 17), also
13^2=16=-1 (mod 17), also
13^14=(13^2)^7=-1 mod 17, also
13^15=(-1)(-4) mod 17 = 4
Der Hauptunterschied ist, dass modPow wesentlich schneller ist, weil auch alle Zwischenergebnisse beim Potenzieren modulo genommen werden können, während bei der Nacheinanderausführung erst mal eine riesige Zahl berechnet werden muss. Deshalb können mit modPow auch höhere Potenzen berechnet werden, weshalb auch der Exponent ein BigInteger sein darf.
Gut, so genau kenn ich mich nicht aus was da intern so abläuft da mir das ganze Bit-Rumgeschubse in dieser Strict-irgendwas-Klasse zu hoch ist, aber das da schon irgendwie effektiver gerechnet werden kann weil ja nicht erst eine riesige Potenz berechnet werden muss sondern wie du schon sagtest auch schon gleich die Zwischenschritte verarbeitet werden macht schon durchaus Sinn.
Kannst du auch “per Hand” machen. Was sind z.B. die letzten 2 Ziffern von 2^123?
Modulo 100:
2^10 === 1024 === 24
2^20 === (2^10)^2 === 24^2 === 576 === 76
2^40 === (2^20)^2 === 76^2 === 5776 === 76
2^80 === (2^40)^2 === 76^2 === 5776 === 76
2^120 === 2^80 * 2^40 = 76 * 76 === 5776 === 76
2^123 === 2^120 * 2^3 = 76 * 8 === 608 === 08
2^123 endet auf 08
Volles Ergebnis: 10633823966279326983230456482242756608
[ot]interessantes System bei den Zweierpotenzen, man kann immer ganze ^20 als einen Kreis streichen und dann wie bei 0 anfangen:
2^23 -> 2^3 ~ 08
2^46 -> 2^6 ~ 64
mit einer Ausnahme:
der erste Wert jeder neuen Runde, etwa bei 2^61 ist nicht genau 2^1 ~ 02, sondern ~52,
bei 2^1 an sich ohne zu streichende ^20 dann natürlich doch ~02 [/ot]
Wenn die Basis zum Modul teilerfremd ist, kann man direkt den kleinen Fermat benutzen: a^phi(n) === 1 | mod n. Bei 100 = 2² * 5² wäre phi(100) = 2 * (2-1) * 5 * (5-1) = 2 * 20 = 40, also a^40 == 1 | mod 100, unabhängig von der Basis a (solange sie teilerfremd zu n ist):
3^40 = 12157665459056928801
7^40 = 6366805760909027985741435139224001
11^40 = 452592555681759518058893560348969204658401
13^40 = 361188648084531445929920877641340156544317601
Für solche Basen kann man also den Exponenten in unserem Beispiel gleich mod 40 nehmen: 3^123 === 3^3 === 27 | mod 100 (Gegenprobe: 3^123 = 48519278097689642681155855396759336072749841943521979872827)
Zum Ausgansbeispiel:
13^15 === (13^3)^5 === ((-4)^3)^5 === (-64)^5 === (-13)^5 === 4^5 === (2*2)^5 === 2^5 * 2^5 === (2^5)^2 === 32^2 === 15^2 === (-2)^2 === 4 | mod 17