3

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

Cobe
  • 161
  • 15

3 Answers3

2

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
Community
  • 1
  • 1
Luis Mendo
  • 110,752
  • 13
  • 76
  • 147
  • I see... I just thought that since there is an immediate result, matlab performs some kind of fast exponentiation inside mod() for cases like that... – Cobe Oct 01 '14 at 20:43
  • Exponentiation *is* fast. In very few cases would MATLAB or any other numerical computation engine actually multiply a number by itself N times to compute x^N. That has no bearing on the size of the number you're trying to `mod`. – Peter Oct 01 '14 at 20:49
  • I don't know if the operation in your question was just an example. But if you really need to compute the _modulo of a large number that is expressed as a product of small numbers_, you can apply the modulo operation to the factors and thus avoid the numerical errors. I've edited my answer with this – Luis Mendo Oct 01 '14 at 22:15
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." ...

LHIOUI
  • 3,287
  • 2
  • 24
  • 37
  • and I just checked that powermod() is only available in 2014b version! too bad I don't have it :P Anyway, thanks! – Cobe Oct 01 '14 at 20:54
0

Another way is to use symfun

syms x y z
f = symfun(mod(x^y,z), [x y z])
f(111,11,143)
Autonomous
  • 8,935
  • 1
  • 38
  • 77