MATLAB Answers

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

7 views (last 30 days)
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.

  0 Comments

Sign in to comment.

Accepted Answer

Walter Roberson
Walter Roberson on 17 Sep 2020
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.

  0 Comments

Sign in to comment.

More Answers (1)

Stephen Cobeldick
Stephen Cobeldick on 17 Sep 2020
Edited: Stephen Cobeldick on 17 Sep 2020
>> 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.

  0 Comments

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by