Ich hebe eine Basis b zur Potenz p und nehme das Modulo m davon.

Nehmen wir an, b = 55170 oder 55172 und m = 3043839241 (was zufällig das Quadrat von 55171 ist). Der Linux-Rechnerbc gibt die Ergebnisse aus (wir brauchen diese zur Kontrolle):

echo "p=5606;b=55171;m=b*b;((b-1)^p)%m;((b+1)^p)%m" | bc
2734550616
309288627

Jetzt ergibt die Berechnung von 55170 ^ 5606 eine ziemlich große Zahl, aber da ich eine Modulooperation ausführen muss, kann ich die Verwendung von BigInt umgehen, dachte ich, weil:

(a*b) % c == ((a%c) * (b%c))%c i.e.
(9*7) % 5 == ((9%5) * (7%5))%5 =>
63 % 5    == (4     *    2) %5 =>
3         == 8 % 5

... und a ^ d = a ^ (b + c) = a ^ b * a ^ c, daher kann ich b + c durch 2 teilen, was für gerade oder ungerade ds d / 2 und d- ( d / 2), also kann ich für 8 ^ 5 8 ^ 2 * 8 ^ 3 berechnen.

So sieht meine (defekte) Methode, die den Divisor immer sofort abschneidet, so aus:

def powMod (b: Long, pot: Int, mod: Long) : Long = { 
      if (pot == 1) b % mod else {
          val pot2 = pot/2
          val pm1 = powMod (b, pot2, mod)             
          val pm2 = powMod (b, pot-pot2, mod)           
          (pm1 * pm2) % mod 
      } 
}

und mit einigen Werten gespeist,

powMod (55170, 5606, 3043839241L) 
res2: Long = 1885539617
powMod (55172, 5606, 3043839241L) 
res4: Long = 309288627

Wie wir sehen können, ist das zweite Ergebnis genau das gleiche wie das obige, aber das erste sieht ganz anders aus. Ich mache eine Menge solcher Berechnungen und sie scheinen genau zu sein, solange sie im Bereich von Int bleiben, aber ich kann keinen Fehler sehen. Die Verwendung eines BigInt funktioniert auch, ist aber viel zu langsam:

def calc2 (n: Int, pri: Long) = {
    val p: BigInt = pri
    val p3 = p * p
    val p1 = (p-1).pow (n) % (p3)
    val p2 = (p+1).pow (n) % (p3)
    print ("p1: " + p1 + " p2: " + p2)
}

calc2 (5606, 55171) 
p1: 2734550616 p2: 309288627

(gleiches Ergebnis wie bei bc) Kann jemand den Fehler in @ sehpowMod?