matlab wrong modulo result when the divident is raised to a power

Question

Just wondering... I tried doing by hand (with the multiply and square method) the operation (111^11)mod143 and I got the result 67. I also checked that this is correct, in many online tools. Yet, in matlab plugging:

 mod(111^11,143)

gives 127! Is there any particular reason for this? I didn't find anything in the documentation...

Answer 1

The value of 111^11 (about 3.1518e+022) exceeds the maximum integer that is guaranteed to be represented exactly as a double, which is 2^53 (about 9.0072e+015). So the result is spoilt by insufficient numerical precision.

To achieve the correct result, use symbolic computation:

>> syms x y z
>> r = mod(x^y, z);
>> subs(r, [x y z], [111 11 143])
ans =
67

Alternatively, for this specific operation (modulo of a large number that is expressed as a product of small numbers), you can do the computation very easily using the following fact (where ∗ denotes product):

mod(a∗b, z) = mod(mod(a,z)∗mod(b,z), z)

That is, you can apply the modulo operation to factors of your large number and the final result is unchanged. If you choose factors sufficiently small so that they can be represented exactly as double, you can do the computation numerically without any loss of precision.

For example: using the decomposition 111^11 = 111^4*111^4*111^3, since all factors are small enough, gives the correct result:

>> mod((mod(111^4, 143))^2 * mod(111^3, 143), 143)
ans =
    67

Similarly, using 111^2 and 111 as factors,

>> mod((mod(111^2, 143))^5 * mod(111, 143), 143)
ans =
    67

Answer 2

from the matlab website they recommend using powermod(b, e, m) (b^e mod m)

"If b and m are numbers, the modular power b^e mod m can also be computed by the direct call b^e mod m. However, powermod(b, e, m) avoids the overhead of computing the intermediate result be and computes the modular power much more efficiently." ...