Modulus of a negative exponent in matlab?

17 views (last 30 days)
Faraz on 4 Jun 2018
Commented: Faraz on 6 Jun 2018
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
Java has a solution for this, "modPow" which accepts negative exponents as explained here
How will I make this possible in Matlab?
Thank you

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;
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.
Faraz on 6 Jun 2018
hi John since you wrote vpi, I hope you can answer my question here as well: https://uk.mathworks.com/matlabcentral/answers/404365-matlab-taking-forever-to-give-a-simple-result-something-that-java-does-in-seconds
Thanks

Sid Parida on 4 Jun 2018
Edited: Sid Parida on 4 Jun 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?
Faraz on 5 Jun 2018
Hi Sid, Thanks for the efforts but unfortunately it is still not working..
I get the error:
Error using modsolve (line 128)
p must be scalar, integer, and prime
Error in modPow (line 8)
result = powermod(modsolve(base, [], modulus), abs(exponent), modulus);
I was wondering, would it be easier to call the java library that does this as I read somewhere that Matlab supports it?
Thanks