Modulus of a negative exponent in matlab?

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

Answer 1

[John D'Errico]

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]

You wrote powermod for Matlab? It cant get any more authoritative than that :)

Thanks for the great answer :)

[John D'Errico]

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]

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

Answer 2

[Sid Parida]

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]

Hi Sid, Thanks for the answer, but unfortunately gcd is not working with variables of type vpi or vpa.

The syntax for gcd used by you only supports double, single, and signed integer inputs as per the help documentation.

I have to use vpi type for the encryption to work.

Thanks

[Sid Parida]

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]

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