Math.Pow (31, 43)% 77 gives the wrong value

31^43 is a number with 64 decimal places, decimal or double type cannot store as much. You can use long arithmetic to calculate this. For example, the built-in BigInteger type with System.Numerics.dll :

 Console.WriteLine(BigInteger.ModPow(31, 43, 77)); 

Displays 3 . Moreover, this method is well optimized.

The fact is that Math.Pow works with the double type, and it has limited accuracy: it stores the number with an accuracy of 52 bits , which means that for large numbers the lower digits are inaccurate. And for the module, it is the minor digits that are needed, and the older ones are not needed at all.

If Math.Pow worked with int , the problem would be the same: an int more than two kopecks of billions would be taken modulo 2 ^ 32, and this is clearly not what you need.

What to do? And you need to perform operations not so in the forehead. You must present the exponentiation as several multiplications, and with each multiplication take the module from the result.

It turns out something like this:

 uint multmod(uint a, uint b, uint mod) => (uint)(((ulong)a * b) % mod); uint powermod(uint n, uint pow, uint mod) { uint result = 1; uint npow = n; while (pow != 0) { if (pow % 2 == 1) result = multmod(result, npow, mod); pow = pow / 2; npow = multmod(npow, npow, mod); } return result; } 

Which method is better: read manually or use the BigInteger.ModPow library method? The question is not so trivial.

On the one hand, if there is little computation, then it is better to use the tried and tested library method. The execution speed is on the order of several hundred nanoseconds, it is really very fast, so you can not worry about it.

On the other hand, if there are really a lot of calculations, more than a million per second, then nano-optimizations start to matter. Which method is faster: library or manual? The library method is supported by the fact that it was written and debugged by professionals, and the fact that in new versions of the framework it will probably still be improved. The manual method is that the library method is too general (it counts arbitrary numbers!), And due to this it can do too much. We are testing!

I wrote this test on BenchmarkDotNet :

 class Program { static void Main(string[] args) { Console.ReadKey(); var summary = BenchmarkRunner.Run<ModPowComparison>(); Console.ReadKey(); } } public class ModPowComparison { [Params(3, 31, 8181818)] public uint A; [Params(3, 43, 243)] public uint B; [Params(2, 77, 1024, 100000)] public uint C; [Benchmark(Baseline=true)] public BigInteger BigNum() => BigInteger.ModPow(A, B, C); [Benchmark] public BigInteger Manual() => powermod(A, B, C); uint multmod(uint a, uint b, uint mod) => (uint)(((ulong)a * b) % mod); uint powermod(uint n, uint pow, uint mod) { uint result = 1; uint npow = n; while (pow != 0) { if (pow % 2 == 1) result = multmod(result, npow, mod); pow = pow / 2; npow = multmod(npow, npow, mod); } return result; } } 

I took some small numbers and some more numbers. Here is the resulting table:

 BenchmarkDotNet=v0.10.10, OS=Windows 7 SP1 (6.1.7601.0) Processor=Intel Core i7-2600K CPU 3.40GHz (Sandy Bridge), ProcessorCount=8 Frequency=3320371 Hz, Resolution=301.1712 ns, Timer=TSC [Host] : .NET Framework 4.7 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.2053.0 DefaultJob : .NET Framework 4.7 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.2053.0 Method | A | B | C | Mean | Error | StdDev | Median | Scaled | ------- |-------- |---- |------- |----------:|-----------:|-----------:|----------:|-------:| BigNum | 3 | 3 | 2 | 149.01 ns | 0.3356 ns | 0.2975 ns | 149.08 ns | 1.00 | Manual | 3 | 3 | 2 | 32.51 ns | 0.0581 ns | 0.0544 ns | 32.52 ns | 0.22 | BigNum | 3 | 3 | 77 | 149.08 ns | 0.4919 ns | 0.4602 ns | 149.17 ns | 1.00 | Manual | 3 | 3 | 77 | 33.00 ns | 0.1314 ns | 0.1229 ns | 32.99 ns | 0.22 | BigNum | 3 | 3 | 1024 | 149.17 ns | 0.2275 ns | 0.2128 ns | 149.15 ns | 1.00 | Manual | 3 | 3 | 1024 | 33.18 ns | 0.0888 ns | 0.0831 ns | 33.17 ns | 0.22 | BigNum | 3 | 3 | 100000 | 149.02 ns | 0.5999 ns | 0.5318 ns | 148.99 ns | 1.00 | Manual | 3 | 3 | 100000 | 33.17 ns | 0.0549 ns | 0.0514 ns | 33.18 ns | 0.22 | BigNum | 3 | 43 | 2 | 262.27 ns | 0.5958 ns | 0.5573 ns | 262.23 ns | 1.00 | Manual | 3 | 43 | 2 | 76.55 ns | 0.1985 ns | 0.1856 ns | 76.56 ns | 0.29 | BigNum | 3 | 43 | 77 | 262.12 ns | 0.5056 ns | 0.4729 ns | 262.14 ns | 1.00 | Manual | 3 | 43 | 77 | 78.53 ns | 0.2021 ns | 0.1791 ns | 78.56 ns | 0.30 | BigNum | 3 | 43 | 1024 | 262.48 ns | 0.7268 ns | 0.6798 ns | 262.42 ns | 1.00 | Manual | 3 | 43 | 1024 | 78.66 ns | 0.2674 ns | 0.2502 ns | 78.67 ns | 0.30 | BigNum | 3 | 43 | 100000 | 262.35 ns | 0.7756 ns | 0.7255 ns | 262.26 ns | 1.00 | Manual | 3 | 43 | 100000 | 79.13 ns | 0.1902 ns | 0.1779 ns | 79.21 ns | 0.30 | BigNum | 3 | 243 | 2 | 337.59 ns | 0.8698 ns | 0.8136 ns | 337.52 ns | 1.00 | Manual | 3 | 243 | 2 | 114.33 ns | 10.2557 ns | 16.2666 ns | 104.97 ns | 0.34 | BigNum | 3 | 243 | 77 | 337.43 ns | 0.8991 ns | 0.8410 ns | 337.53 ns | 1.00 | Manual | 3 | 243 | 77 | 106.63 ns | 0.2987 ns | 0.2648 ns | 106.62 ns | 0.32 | BigNum | 3 | 243 | 1024 | 337.65 ns | 0.5805 ns | 0.5430 ns | 337.59 ns | 1.00 | Manual | 3 | 243 | 1024 | 107.24 ns | 0.1823 ns | 0.1705 ns | 107.24 ns | 0.32 | BigNum | 3 | 243 | 100000 | 362.40 ns | 0.9287 ns | 0.7755 ns | 362.21 ns | 1.00 | Manual | 3 | 243 | 100000 | 106.85 ns | 0.1600 ns | 0.1419 ns | 106.86 ns | 0.29 | BigNum | 31 | 3 | 2 | 149.07 ns | 0.5325 ns | 0.4720 ns | 149.04 ns | 1.00 | Manual | 31 | 3 | 2 | 32.54 ns | 0.0861 ns | 0.0805 ns | 32.53 ns | 0.22 | BigNum | 31 | 3 | 77 | 149.45 ns | 0.5391 ns | 0.4779 ns | 149.47 ns | 1.00 | Manual | 31 | 3 | 77 | 32.73 ns | 0.1518 ns | 0.1420 ns | 32.71 ns | 0.22 | BigNum | 31 | 3 | 1024 | 150.40 ns | 0.4437 ns | 0.3934 ns | 150.32 ns | 1.00 | Manual | 31 | 3 | 1024 | 33.11 ns | 0.0672 ns | 0.0628 ns | 33.12 ns | 0.22 | BigNum | 31 | 3 | 100000 | 150.89 ns | 0.7241 ns | 0.6047 ns | 150.65 ns | 1.00 | Manual | 31 | 3 | 100000 | 33.42 ns | 0.3659 ns | 0.3422 ns | 33.25 ns | 0.22 | BigNum | 31 | 43 | 2 | 264.31 ns | 1.2552 ns | 1.1741 ns | 264.45 ns | 1.00 | Manual | 31 | 43 | 2 | 76.87 ns | 0.2282 ns | 0.2134 ns | 76.91 ns | 0.29 | BigNum | 31 | 43 | 77 | 262.70 ns | 1.0268 ns | 0.9605 ns | 262.56 ns | 1.00 | Manual | 31 | 43 | 77 | 79.13 ns | 0.2694 ns | 0.2520 ns | 79.08 ns | 0.30 | BigNum | 31 | 43 | 1024 | 263.40 ns | 1.3053 ns | 1.2209 ns | 262.74 ns | 1.00 | Manual | 31 | 43 | 1024 | 78.98 ns | 0.1876 ns | 0.1755 ns | 78.94 ns | 0.30 | BigNum | 31 | 43 | 100000 | 262.73 ns | 0.7095 ns | 0.6290 ns | 262.66 ns | 1.00 | Manual | 31 | 43 | 100000 | 78.99 ns | 0.1747 ns | 0.1634 ns | 78.95 ns | 0.30 | BigNum | 31 | 243 | 2 | 338.05 ns | 1.4928 ns | 1.3964 ns | 337.56 ns | 1.00 | Manual | 31 | 243 | 2 | 105.00 ns | 0.1658 ns | 0.1551 ns | 104.97 ns | 0.31 | BigNum | 31 | 243 | 77 | 337.59 ns | 0.7197 ns | 0.6732 ns | 337.53 ns | 1.00 | Manual | 31 | 243 | 77 | 106.78 ns | 0.2404 ns | 0.2131 ns | 106.76 ns | 0.32 | BigNum | 31 | 243 | 1024 | 338.06 ns | 0.6610 ns | 0.6183 ns | 337.81 ns | 1.00 | Manual | 31 | 243 | 1024 | 106.51 ns | 0.3239 ns | 0.3030 ns | 106.44 ns | 0.32 | BigNum | 31 | 243 | 100000 | 385.20 ns | 0.7483 ns | 0.7000 ns | 385.16 ns | 1.00 | Manual | 31 | 243 | 100000 | 107.31 ns | 0.2380 ns | 0.2227 ns | 107.27 ns | 0.28 | BigNum | 8181818 | 3 | 2 | 173.17 ns | 0.4454 ns | 0.4166 ns | 173.23 ns | 1.00 | Manual | 8181818 | 3 | 2 | 34.74 ns | 0.0799 ns | 0.0747 ns | 34.75 ns | 0.20 | BigNum | 8181818 | 3 | 77 | 172.74 ns | 0.1622 ns | 0.1267 ns | 172.76 ns | 1.00 | Manual | 8181818 | 3 | 77 | 33.24 ns | 0.0937 ns | 0.0876 ns | 33.24 ns | 0.19 | BigNum | 8181818 | 3 | 1024 | 172.72 ns | 0.3758 ns | 0.3515 ns | 172.73 ns | 1.00 | Manual | 8181818 | 3 | 1024 | 32.68 ns | 0.0712 ns | 0.0631 ns | 32.68 ns | 0.19 | BigNum | 8181818 | 3 | 100000 | 197.96 ns | 0.4350 ns | 0.4069 ns | 197.88 ns | 1.00 | Manual | 8181818 | 3 | 100000 | 33.12 ns | 0.1025 ns | 0.0959 ns | 33.11 ns | 0.17 | BigNum | 8181818 | 43 | 2 | 287.34 ns | 0.6073 ns | 0.5681 ns | 287.18 ns | 1.00 | Manual | 8181818 | 43 | 2 | 77.66 ns | 0.1319 ns | 0.1233 ns | 77.66 ns | 0.27 | BigNum | 8181818 | 43 | 77 | 287.11 ns | 0.9016 ns | 0.8434 ns | 287.30 ns | 1.00 | Manual | 8181818 | 43 | 77 | 80.28 ns | 0.1037 ns | 0.0919 ns | 80.28 ns | 0.28 | BigNum | 8181818 | 43 | 1024 | 287.15 ns | 0.7190 ns | 0.6725 ns | 287.25 ns | 1.00 | Manual | 8181818 | 43 | 1024 | 78.77 ns | 0.1394 ns | 0.1304 ns | 78.79 ns | 0.27 | BigNum | 8181818 | 43 | 100000 | 401.59 ns | 0.7218 ns | 0.6398 ns | 401.37 ns | 1.00 | Manual | 8181818 | 43 | 100000 | 79.45 ns | 0.1356 ns | 0.1202 ns | 79.39 ns | 0.20 | BigNum | 8181818 | 243 | 2 | 362.07 ns | 0.6777 ns | 0.6339 ns | 361.93 ns | 1.00 | Manual | 8181818 | 243 | 2 | 105.72 ns | 0.2266 ns | 0.2119 ns | 105.77 ns | 0.29 | BigNum | 8181818 | 243 | 77 | 362.05 ns | 0.4713 ns | 0.3936 ns | 362.06 ns | 1.00 | Manual | 8181818 | 243 | 77 | 108.33 ns | 0.1698 ns | 0.1589 ns | 108.29 ns | 0.30 | BigNum | 8181818 | 243 | 1024 | 362.43 ns | 0.8363 ns | 0.7823 ns | 362.21 ns | 1.00 | Manual | 8181818 | 243 | 1024 | 104.96 ns | 0.2377 ns | 0.2224 ns | 104.95 ns | 0.29 | BigNum | 8181818 | 243 | 100000 | 506.07 ns | 1.1124 ns | 0.9289 ns | 506.21 ns | 1.00 | Manual | 8181818 | 243 | 100000 | 107.34 ns | 0.3394 ns | 0.3175 ns | 107.37 ns | 0.21 | 

Here the last column is interesting, which shows the relative speed. It shows that in the given test conditions the manual method takes from 17 to 32% of the time required for the library method.

In other conditions, the results will, of course, be different.