Borrar filtros
Borrar filtros

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

7 visualizaciones (últimos 30 días)
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 comentario
Dyuman Joshi
Dyuman Joshi el 24 de Mzo. de 2024
Editada: Dyuman Joshi el 24 de Mzo. de 2024
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

Iniciar sesión para comentar.

Respuesta aceptada

Walter Roberson
Walter Roberson el 24 de Mzo. de 2024
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

Más respuestas (2)

Voss
Voss el 24 de Mzo. de 2024
Editada: Voss el 24 de Mzo. de 2024
c=13959; d=475; n=20711;
r = 1;
for ii = 1:d
r = mod(r*c,n);
end
r
r = 1217
(Particularly the "Memory-efficient method" section)
  2 comentarios
fa wu
fa wu el 24 de Mzo. de 2024
Thank you for providing the Wikipedia link. It’s very helpful and inspiring!
Bruno Luong
Bruno Luong el 24 de Mzo. de 2024
This answer shows the right way to calculate in modular ring/field. It is better than the other accepted answer

Iniciar sesión para comentar.


John D'Errico
John D'Errico el 24 de Mzo. de 2024
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.

Productos


Versión

R2020a

Community Treasure Hunt

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

Start Hunting!

Translated by