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

2 次查看（过去 30 天）
fa wu
fa wu 2024-3-24
回答： 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 个评论
Dyuman Joshi
Dyuman Joshi 2024-3-24
编辑：Dyuman Joshi 2024-3-24
Ran in:
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

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Walter Roberson
Walter Roberson 2024-3-24
Ran in:
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

更多回答（2 个）

Voss
Voss 2024-3-24
编辑：Voss 2024-3-24
Ran in:
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
fa wu 2024-3-24
Thank you for providing the Wikipedia link. It’s very helpful and inspiring!
Bruno Luong
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

请先登录，再进行评论。

John D'Errico
John D'Errico 2024-3-24
Ran in:
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.

类别

在 Help Center 和 File Exchange 中查找有关 Number Theory 的更多信息

标签

产品


版本

R2020a

Community Treasure Hunt

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

Start Hunting!

Translated by