Power and modulo on the fly for large numbers

Question

I raise some basis b to the power of p and take modulo m of this.

Suppose that b = 55170 or 55172 and m = 3043839241 (which turns out to be square 55171). Linux bc calculator gives the results (this is necessary for management):

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

Now calculating 55170 ^ 5606 gives a somewhat large amount, but since I have to do a modular operation, I can get around using BigInt, I thought, because:

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

... and a ^ d = a ^ (b + c) = a ^ b * a ^ c, so I can divide b + c by 2, which gives for even or odd ds d / 2 and d - (d / 2), so for 8 ^ 5 I can calculate 8 ^ 2 * 8 ^ 3.

So, my (defective) method, which always disables the divider on the fly, looks like this:

 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 } } 

and with some meanings,

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

As we see, the second result is exactly the same as above, but the first looks completely different. I do a lot of such calculations and they seem accurate as long as they stay in the Int range, but I don't see any error. Using BigInt also works, but is too slow:

 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 

(same result as with bc) Can anyone see the error in powMod ?

Answer 1

I think the answer is here:

 scala> math.sqrt(Long.MaxValue).toLong < 3043839241L res9: Boolean = true 

This means that you may have a long overflow even for numbers that are less than the specified module value. Let's try to catch him:

 scala> 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) | val partial = ((pm1 % mod) * (pm2 % mod)).ensuring(res => | res > pm1 % mod && res > pm2 % mod, "Long overflow multiplying "+pm1+" by "+pm2) | partial % mod | } | } powMod: (b: Long,pot: Int,mod: Long)Long scala> powMod (55170, 5606, 3043839241L) java.lang.AssertionError: assertion failed: Long overflow multiplying 3042625480 by 3042625480 

There you have it.

Answer 2

Not familiar with Scala, but ...

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

You meant

  val pm1 = powMod (b, pot2, mod) 

Pay attention to pot2 instead of the pot.

Strange, it seems like this should loop forever / overflow the stack, but who knows what Scala is doing.

Answer 3

Well, it took me some time and finally destroyed a long but never-proven assumption, namely: if you multiply two 64-bit positive integral values ​​(aka: Longs and almost only 63-bit, after all), you can intercept and get negative values, but not get overflow, to get positive (but wrong) values ​​again.

So, I tried to put a guard in my code to calculate my value with BigInt, which is too big, but the protection was insufficient because I tested for res < 0 . res < pm1 && res < pm2 also not enough.

To increase speed, I used mutable.HashMap, and now the code looks like this:

 val MVL : Long = Integer.MAX_VALUE var modPow = new scala.collection.mutable.HashMap [(Long, Int, Long), Long ] () def powMod (b: Long, pot: Int, mod: Long) : Long = { if (pot == 1) b % mod else modPow.getOrElseUpdate ((b, pot, mod), { val pot2= pot/2 val pm1 = powMod (b, pot2, mod) val pm2 = powMod (b, pot-pot2, mod) val res = (pm1 * pm2) // avoid Long-overrun if (pm1 < MVL && pm2 < MVL) res % mod else { val f1: BigInt = pm1 val f2: BigInt = pm2 val erg = (f1 * f2) % mod erg.longValue } }) } 

You may ask yourself if a long-term MVL is really required, or

 if (pm1 < Integer.MAX_VALUE && ... 

would also work. Not. This is not so. :) Another trap to avoid. :)

Finally, this is pretty quick and correct, and I learned two lessons about cost overruns and MAX_VALUE - a comparison.