Modulus of a negative exponent in matlab?
17 views (last 30 days)
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:
and am provided with the errors:
D must be a non-negative integer smaller than flintmax.
vpi2bin only works on non-negative vpi integers
Java has a solution for this, "modPow" which accepts negative exponents as explained here
How will I make this possible in Matlab?
John D'Errico on 5 Jun 2018
Edited: John D'Errico on 5 Jun 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;
Did it work? Of course.
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:
1×0 empty double row vector
The failure will arise when the two are not relatively co-prime, as I recall.
More Answers (1)
Sid Parida on 4 Jun 2018
Edited: Sid Parida on 4 Jun 2018
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)
>> result = modPow(2, -1, 7)
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?