How to calculate mod(188^80, 34969) in matlab.
1 vue (au cours des 30 derniers jours)
Afficher commentaires plus anciens
I am new to Matlab and I was running the Paillier cryptosystem. For that, I need to calculate mod(188^80,34969) but matlab is giving the wrong result.
How can solve this with vpi or symbolic tools?
0 commentaires
Réponses (1)
John D'Errico
le 29 Avr 2018
Modifié(e) : John D'Errico
le 29 Avr 2018
(This is actually a fairly common homework problem, thus how to compute such a modulus of a power too large to compute directly using doubles.)
Since you asked about vpi, it is simple. Use powermod, the tool designed to solve exactly that problem.
powermod(188,80,34969)
ans =
14961
As a test:
mod(vpi(188)^80,34969)
ans =
14961
Of course, the second solution is much slower, since there vpi was forced to compute the full number, then compute the modulus.
Note that you COULD have done the computation using nothing more than doubles.
B = flip(dec2bin(80))
B =
'0000101'
Bi = find(B == '1') - 1
Bi =
4 6
So we see that 80 (the exponent) can be written as 80=16+64.
Therefore, 188^80=188^16*188^64
Eventually, you would compute the modulus as:
mod(2993*11969,modulus)
ans =
14961
So you can actually compute a powermod in double precision as long as the modulus is no larger than sqrt(2^53 - 1).
0 commentaires
Voir également
Catégories
En savoir plus sur Number Theory dans Help Center et File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!