Berechnungsfehler? int (a ^ b % p)

[huckleberry]

Hallo Forum,

ich habe ein kleines Problemchen...

hier im Forum habe ich ein Tipp bekommen. Eine Methode um (a ^ b % p) auszurechen:

    public int modPow(int param_base, int param_exp, int param_mod) {
        int result = 1;
        for(int e = 0; e < param_exp; e++) {
            result = ((result * param_base) % param_mod);
        }
        return result;
    }

welche ich mittlerweile in folgender Methode benutzte:

	public void signObject(Object o, int d, LogFileWriter h) {
		h.writeLog( "hash: "+o.hashCode() );		
		int hash = (o.hashCode() % this.getRsaSignModul());
		if (hash < 0) hash += this.getRsaSignModul();
// erste Ausgabe ohne =
		h.writeLog( "hash: "+hash+" ^ "+d+" % "+this.getRsaSignModul() );		
		
		int r = modPow(hash, d, this.getRsaSignModul());

// hier Ausgabe mit = 
		h.writeLog("hash: "+hash+" ^ "+d+" % "+this.getRsaSignModul()+" = "+r);
		this.signedHash = r;
	}

woanders funktioniert es super. Aber in der signObject Methode bekomme ich Mist-resultate ;(
Im folgenden seht ihr mal ein paar ausgaben

| [1000][ms] hash: 1822459128                                                                      |
| [1000][ms] hash: 53491 ^ 20579 % 113879                                                          |
| [1000][ms] hash: 53491 ^ 20579 % 113879 = 23236                                                  |
|
| [1500][ms] hash: 1418257117                                                                      |
| [1500][ms] hash: 8051 ^ 20579 % 113879                                                           |
| [1500][ms] hash: 8051 ^ 20579 % 113879 = 105119                                                  |
|
| [2000][ms] hash: 404765745                                                                       |
| [2000][ms] hash: 39779 ^ 20579 % 113879                                                          |
| [2000][ms] hash: 39779 ^ 20579 % 113879 = -37105                                                 |
|
| [2500][ms] hash: 1746807975                                                                      |
| [2500][ms] hash: 17994 ^ 20579 % 113879                                                          |
| [2500][ms] hash: 17994 ^ 20579 % 113879 = 45698                                                  |

HIER: 1. & 3. Log, Ergebnis hinter "=" Zeichen Falsch
2. & 4. Log, Ergebnis hinter "=" Zeichen korrekt.

Jemand einen Tipp woran das liegen könnte? Manchmal sieht man den Wald vor lauter Bäumen nicht.
???:L
Danke im voraus..

Mfg Huck

 

[huckleberry]

Da öfters negative Werte herauskommen, vermute ich ein Overflow...

Negative Werte dürfte mein modPow ja eig. nicht zurückgeben?

Leider kann ich den Debugger nicht wirklich benutzen, da die Main in irgendeiner jar liegt.
Debuggen tue ich also als mittels Log-Ausgaben

 

[madboy]

Du versuchst, mir 82744stelligen Zahlen zu rechnen, das geht schnell schief mit Integern (Maximalwert 2147483647)

 

[huckleberry]

Du versuchst, mir 82744stelligen Zahlen zu rechnen, das geht schnell schief mit Integern (Maximalwert 2147483647)

Jetzt sehe ich es

habe result in long umgewnadelt und die Ausgabe gecastet. Da mein Modul nie grösser als Integer.MAX_VALUE wird, dürfte das doch funktionieren oder?

    public int modPow(int param_base, int param_exp, int param_mod) {
        long result = 1;
        for(int e = 0; e < param_exp; e++) {
            result = ((result * param_base) % param_mod);
        }
        return (int) result;
    }

Scheint zu funktionieren

 

[madboy]

Oh sorry, ich habe nur die Rechnung und nicht die Rechenmethode angeschaut

EDIT: aber wenn es jetzt klappt ist ja alles ok

 

[huckleberry]

Oh sorry, ich habe nur die Rechnung und nicht die Rechenmethode angeschaut

EDIT: aber wenn es jetzt klappt ist ja alles ok

No Problem

Ursache zB im ersten log:
| [1000][ms] hash: 1822459128 |
| [1000][ms] hash: 53491 ^ 20579 % 113879 |
| [1000][ms] hash: 53491 ^ 20579 % 113879 = 23236

Zweiterschleifendurchlauf im modPow
--> 53491 * 53491
= 2861287081 was echt grösser ist als
> 2147483647

Result in long umgewandelt, jetzt gehts. Ich kann beruhigt abschliessen

 

[0x7F800000]

Ne, wirklich, wie kann das sein, man sagt den:

-die Erde ist rund, sie ist rund, RUND, EINE KUGEL!
-Guggt euch die schiffe am horizont an!
-Merkt ihr denn nicht dass man weiter sieht, je höher man raufklettert?
-Guggt euch doch den Mond und andere Planeten an!
-Hier ist das Graviatationsgesetz, ist euch jetzt klar warum die erde eine kugel sein muss?
-Der Typ hier ist dreimal um die Welt gesegelt, seht euch die Karte an, die Stücke fügen sich offensichtlich zu einer Kugel zusammen!
- hier sind die Photos aus dem Weltall, diese Kugel ist unsere Erde, hier sind Aufnahmen von allen 360°

und dann kommen die und sagen:
- Aba de erde iss doch platt alda, oda?
-Hier ist ein Satellitenphoto! Das ist Europa, hier ist deine Stadt, das ist dein Haus, hier ist sogar dein Auto zu sehen, hier gibt es eine Menge anderer Photos, die sich lückenlos zu einer Kugel zusammenfügen!!!
- Abe de erde ist doch eine Scheibe, wenn die krumm wäre, würden wir doch alle runterfallen, oda?
- WHAAAAAAAAAAAAAAAAAAAAAAAAAAAAA!

...


ich hab mir doch so viel mühe gegeben, dieses forum mit der richtigen O(n)-Variante zu überfüllen, wo hast du diesen O(exp(n))-wahnsinn ausgegraben? ;(;(;(

hier im Forum habe ich ein Tipp bekommen. Eine Methode um (a ^ b % p) auszurechen:

    public int modPow(int param_base, int param_exp, int param_mod) {
        int result = 1;
        for(int e = 0; e < param_exp; e++) {
            result = ((result * param_base) % param_mod);
        }
        return result;
    }

=> Wenn man selber keine zeit/lust hat, es richtig zu implementieren, dann sollte man wenigstens auf die korrekte implementierung aus der Standard-API zurückgreifen:
BigInteger (Java Platform SE 6)

...

omg, wird das denn jemals aufhören...