# Matlab wrong modulo result when divident rises to power

Just wondering ... I tried to do the (111 ^ 11) mod143 operation manually (using the multiplication and square method) and I got the result 67. I also checked that this is correct in many online tools. However, when connecting Matlab:

`````` mod(111^11,143)
```

```

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

+3

source to share

The value `111^11`

(about `3.1518e+022`

) exceeds the maximum number that is guaranteed to be represented exactly as `double`

, which is `2^53`

(about `9.0072e+015`

). Thus, the result is spoiled 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 particular operation (modulo a large number, expressed as the product of small numbers), you can easily compute using the following fact (where `∗`

denotes the product):

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

That is, you can apply the modulo operation to the factors of your large number, and the end result will not change. If you choose coefficients small enough that they can be represented exactly as `double`

, you can perform the calculation numerically without losing 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
```

```
+2

source

"If b and m are numbers, the modular cardinality of b ^ e mod m can also be calculated directly by calling b ^ e mod m. However, `powermod(b, e, m)`

it avoids the overhead of calculating the intermediate result be and calculates the modular cardinality much more efficiently."

+2

source

Another way is to use `symfun`

``````syms x y z
f = symfun(mod(x^y,z), [x y z])
f(111,11,143)
```

```
0

source

All Articles