I got Inf when calculating 13959^475, how can I solve this problem?

I want to verify the RSA encryption algorithm. But I encountered a numerical calculation problem during the decryption operation. The first step is to calculate the result of k=c^d. Then calculate the remainder of k/n.

c=13959, d=475, n=20711.

The result of calculating k is Inf, and I found that the type of k is double.

I tried to directly calculate the remainder, mod(c^475, 20711). The result is NaN.

I can get the result when calculating 13959^475 in the Windows calculator. How should I solve this problem?

Windows 10 64-bit operating system Home Edition ，Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz 3.40 ，8G RAM

I’m not sure if the tags set for this question are correct. If you think it’s necessary, you can correct or supplement the classification tags for this question. Thank you!

[Dyuman Joshi]

The answers below have provided how to circumvent this problem.

As for the reason why the output to the power operation is Inf - it is because of the limits of double-precision.

The value of c^d can not be represented with floating point precision.

You need to use higher precision to get the value of the that operation.

c=13959; d=475; n=20711;

One options is to use infinite precision via symbolic numbers (requires Symbolic Math Toolbox) -

val = sym(c)^sym(d)

val = 

6394343243228618172612065193112066658701389585559282803333533185428108579924691787926630120622772007135379142250230094920792897480451658554492848218710758824130325645837536307196537174515332716131716960903651016806296129131092114032080705139600718346602330333466751576171340808628802210214902224893660240161318888297262030115875399376115096135724117001559215570581998080320992627706762978644745903104056806758257262270929883893649592163963684322436933504039747289003962354821575230391106346107280961511778757263230499090214095012300021697733285027942061103525106623175450515143473273013172466927202458423872975094214165852941685347184006205761807699316824030281643895467353544106083329751153118855307952183820421080487071307408930165265593486131309063743980825295217500574817714085995829317582459764305983316814352233248409062522492775675761575273077672727612130782425909023937148338631772832223039420991325524814771040498130257951942199608377388899698364333098706609672397149006416934717329602846953195467991979302766784544656624483591593358730080775805815767866366456620985863084733381501837421316635318092185377920335734983139160778889903212272667365606073179041121713171245092530990462515720510826832162893314351681856878791609183103658976767302061595553826975221080448062284554495536450752768618018567519096850442892801215364032505946716616655044294191848533351066718139872891251085521588262412439865164970243515049425359201277998456373773351283771588323533718377596746029677091283467090833744586941646119008916405508066564091627910221406021264274091865657849121266210484542567064458965544474220783404666369391619165283534723189424904276821670924037302360874069444790406288381228804384693593870780471483209064264736327454243180059953254120965768635294490704088102894844241148667553828928712114909922436574679870069116567671742335833653112881666927118100768384921240309881793277561348413584898882338534170192784629936669046328664301485026740891933308138542069710999

Another option is to use Java BigDecimal (note that TMW has issued a notice that they will remove the support for Java in future versions) -

import java.math.*

BigDecimal(c).pow(d)

ans =

6394343243228618172612065193112066658701389585559282803333533185428108579924691787926630120622772007135379142250230094920792897480451658554492848218710758824130325645837536307196537174515332716131716960903651016806296129131092114032080705139600718346602330333466751576171340808628802210214902224893660240161318888297262030115875399376115096135724117001559215570581998080320992627706762978644745903104056806758257262270929883893649592163963684322436933504039747289003962354821575230391106346107280961511778757263230499090214095012300021697733285027942061103525106623175450515143473273013172466927202458423872975094214165852941685347184006205761807699316824030281643895467353544106083329751153118855307952183820421080487071307408930165265593486131309063743980825295217500574817714085995829317582459764305983316814352233248409062522492775675761575273077672727612130782425909023937148338631772832223039420991325524814771040498130257951942199608377388899698364333098706609672397149006416934717329602846953195467991979302766784544656624483591593358730080775805815767866366456620985863084733381501837421316635318092185377920335734983139160778889903212272667365606073179041121713171245092530990462515720510826832162893314351681856878791609183103658976767302061595553826975221080448062284554495536450752768618018567519096850442892801215364032505946716616655044294191848533351066718139872891251085521588262412439865164970243515049425359201277998456373773351283771588323533718377596746029677091283467090833744586941646119008916405508066564091627910221406021264274091865657849121266210484542567064458965544474220783404666369391619165283534723189424904276821670924037302360874069444790406288381228804384693593870780471483209064264736327454243180059953254120965768635294490704088102894844241148667553828928712114909922436574679870069116567671742335833653112881666927118100768384921240309881793277561348413584898882338534170192784629936669046328664301485026740891933308138542069710999

You could also try tools like - https://in.mathworks.com/matlabcentral/fileexchange/36534-hpf-a-big-decimal-class?s_tid=prof_contriblnk

Answer 1

[Walter Roberson]

c=13959;
mod(sym(c)^475, 20711)

ans = 

1217

powermod(c, 475, 20711)

ans = 1217

which powermod

/MATLAB/toolbox/symbolic/symbolic/powermod.m

powermod() needs the symbolic toolbox

[Dyuman Joshi]

sym() also requires the symbolic toolbox.

Answer 2

[Voss]

c=13959; d=475; n=20711;

r = 1;
for ii = 1:d
    r = mod(r*c,n);
end

r

r = 1217

Reference: https://en.m.wikipedia.org/wiki/Modular_exponentiation

(Particularly the "Memory-efficient method" section)

[fa wu]

Thank you for providing the Wikipedia link. It’s very helpful and inspiring!

[Bruno Luong]

This answer shows the right way to calculate in modular ring/field. It is better than the other accepted answer

Answer 3

[John D'Errico]

Yes, you can use syms. However, you do NOT want to compute a huge power using syms directly, and THEN compute a modulus. Just computing some immense number may be too large to work with. For example, what is this result?

mod(1234567890987654321^232434352546463,453364647421)

Just computing the number 1234567890987654321^232434352546463 is impossible as a double. And even as a sym, that number will be truly immense. Something like

log10(1234567890987654321)*232434352546463

ans = 4.2051e+15

So roughly 4e15 decimal digits. You can't do it by computing that number even as a sym.

Can you do it using a simple loop, in a simple powermod form? Even there, you need to be careful, as the direct loop will require 232434352546463 iterations. And you cannot even store the integer 1234567890987654321 as a true integer in double precision form.

So, really, the sym powermod tool is a hugely valuable tool. Or you can use my VPIJ toolbox (my successor to my own VPI tools.). Or you could use the Java.Math.BigInteger tools (on which I buit VPIJ.)

A useful trick, IF you did want to build your own powermod, is to compute the binary expansin of the exponent. That is, if we recognize that in binary form, that exponent is...

dec2bin(uint64(232434352546463))

ans = '110100110110010111010111000001000110001010011111'

Now by repeated squaring of the base (and then taking the mod), we can compute the powermod in no more than a few dozen multiplies and modulus operations. See that wherever we find a 1 in that expansion, it corresponds to a term we want to use. Not difficult to write.