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

Question

fa wu 2024-3-24

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2098066-i-got-inf-when-calculating-13959-475-how-can-i-solve-this-problem

回答： John D'Errico 2024-3-24

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!

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Dyuman Joshi 2024-3-24

编辑：Dyuman Joshi 2024-3-24

在 MATLAB Online 中打开

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 2024-3-24

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2098066-i-got-inf-when-calculating-13959-475-how-can-i-solve-this-problem#answer_1430046

在 MATLAB Online 中打开

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

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Dyuman Joshi 2024-3-24

sym() also requires the symbolic toolbox.

请先登录，再进行评论。

Answer 2

Voss 2024-3-24

3
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2098066-i-got-inf-when-calculating-13959-475-how-can-i-solve-this-problem#answer_1430031

编辑：Voss 2024-3-24

在 MATLAB Online 中打开

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)

2 个评论
显示无隐藏无

fa wu 2024-3-24

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

Bruno Luong 2024-3-24

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 2024-3-24

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2098066-i-got-inf-when-calculating-13959-475-how-can-i-solve-this-problem#answer_1430116

在 MATLAB Online 中打开

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.