Modulus of a negative exponent in matlab?

7 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:
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

Accepted Answer

John D'Errico
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.
  3 Comments
John D'Errico
John D'Errico on 6 Jun 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.
Faraz
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

Sign in to comment.

More Answers (1)

Sid Parida
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?
  3 Comments
Sid Parida
Sid Parida on 4 Jun 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
Faraz
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

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!