How can I differentiate between powermod(a,b,c) and mod(a^b,c)

Please I need a help.

I'm trying to calculate the modular exponent of 104^45 mod 181 using matlab. I tried it using mod(104^45,181) and the answer was 16 and I used powermod(104,45,181) and the answer was 19. I need the answer of 19 but I cannot understand what is the difference of using mod(104^45,181) or powermod(104,45,181) and why they gave me different results.

Answer 1

[Walter Roberson]

104^45 exceeds 2^53, which is the largest number for which double precision is able to distinguish between adjacent integers. 2^53+1 and 2^53+2 are stored the same way in double precision.

So taking mod() of such a large number is going to be inaccurate, because double precision is not storing the actual number, just the closest approximation it can get.

powermod computes in a way that avoids the overflow problem.

Answer 2

[Stephen23]

>> 104^45
ans =
   5.8412e+90

is well above flintmax, so it is very unlikely to exactly represent the integer that you think it does. Basically you are operating outside the range of values for which binary floating point numbers can return exact results.

Out of curiosity, lets have a look at its exact value:

>> sprintf('%.0f',val)
ans =
5841175681461396100000000000000000000000000000000000000000000000000000000000000000000000000
>> num2strexact(val)
ans =
5.841175681461396139743188451945227599878334793277611533585380091992728127111004870833864704e90

Hmm... according to some online tools I tried just now, the actual value would be:

5841175681461396078978021080682091600471472844189578473133182011317053645880726656567476224

You can see that the floating point number is correct to around 16 significant figures, just as we would expect. But any digits after that are just noise and have no sgnificant meaning.