Modulus of a negative exponent in matlab?
3 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
I am basically trying to perform euclidean distance calculation in the encrypted domain (Paillier encryption). Using the homomorphic properties of Paillier, the squared euclidean distance formula can be written as:
I'm having trouble with (III) as matlab wont accept a negative exponent in mod or powermod.
Based on the above equation, Im trying to implement it as follows:
powermod(encA,(-2*vpi(B)), n*n);
mod((encA)^(-2*vpi(B)), n*n);
and am provided with the errors:
D must be a non-negative integer smaller than flintmax.
vpi2bin only works on non-negative vpi integers
How will I make this possible in Matlab?
Thank you
0 commentaires
Réponse acceptée
John D'Errico
le 5 Juin 2018
Modifié(e) : John D'Errico
le 5 Juin 2018
Um, actually your ststement is mistaken.
It is not that MATLAB won't accept a negative exponent. It is that vpi/powermod won't accept that. If powermod was not written to do so, then you cannot make it behave in that way. Ok, I'll admit that had I thought of it when I wrote that code, I should probably have done so. So sue me. :)
I wrote minv after I wrote powermod, and did not think at the time to simply wrap it into powermod.
The simple solution is to use a fix like this:
negpowermod = @(a,d,n) minv(powermod(a,abs(d),n),n);
so, for a negative exponent d, negpowermod will do the powermod computation, then compute the modular inverse.
a = 23;
d = 17;
n = 137;
negpowermod(a,d,n)
ans =
96
Did it work? Of course.
mod(96*powermod(23,17,137),137)
ans =
1
Note that not ALL integers will have a modular multiplicative inverse with respect to any given modulus, so that negative exponent can fail. In that case, the result will be empty. Thus:
minv(2,10)
ans =
1×0 empty double row vector
The failure will arise when the two are not relatively co-prime, as I recall.
3 commentaires
John D'Errico
le 6 Juin 2018
Well, I wrote vpi. Therefore I wrote the powermod computation that is in vpi. But powermod is actually pretty simple, a homework assignment sometimes. Computing a negative power is slightly more effort, but there are simple algorithms to be found for that too.
Plus de réponses (1)
Sid Parida
le 4 Juin 2018
Modifié(e) : Sid Parida
le 4 Juin 2018
Hi Faraz
I believe this function should perform the task you want. I have formatted it according to the powermod function above, except that it accepts negative values for the second argument. The MATLAB Function file is attached.
The usual call case would be:
result = modPow(base, exponent, modulus)
Example cases:
>> result = modPow(2, -1, 7)
result =
4
I am using the Extended Euclidean Algorithm to find the Modular Multiplicative Inverse first and then raising it to the absolute value of the exponent using powermod.
Does this satisfy your use case?
3 commentaires
Sid Parida
le 4 Juin 2018
Hi Faraz
I have updated the script to use the vpi toolbox function modsolve to calculate the inverse. This should fix the error. Please let me know if this works.
Thanks Sid
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!