I got Inf when calculating 13959^475, how can I solve this problem?
3 views (last 30 days)
Show older comments
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 Comment
Dyuman Joshi
on 24 Mar 2024
Edited: Dyuman Joshi
on 24 Mar 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)
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)
You could also try tools like - https://in.mathworks.com/matlabcentral/fileexchange/36534-hpf-a-big-decimal-class?s_tid=prof_contriblnk
Accepted Answer
Walter Roberson
on 24 Mar 2024
c=13959;
mod(sym(c)^475, 20711)
powermod(c, 475, 20711)
which powermod
powermod() needs the symbolic toolbox
More Answers (2)
Voss
on 24 Mar 2024
Edited: Voss
on 24 Mar 2024
c=13959; d=475; n=20711;
r = 1;
for ii = 1:d
r = mod(r*c,n);
end
r
(Particularly the "Memory-efficient method" section)
2 Comments
Bruno Luong
on 24 Mar 2024
This answer shows the right way to calculate in modular ring/field. It is better than the other accepted answer
John D'Errico
on 24 Mar 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
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))
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.
0 Comments
See Also
Categories
Find more on Number Theory in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!