How to calculate mod(188^80, 34969) in matlab.

I am new to Matlab and I was running the Paillier cryptosystem. For that, I need to calculate mod(188^80,34969) but matlab is giving the wrong result.

How can solve this with vpi or symbolic tools?

Answer 1

[John D'Errico]

(This is actually a fairly common homework problem, thus how to compute such a modulus of a power too large to compute directly using doubles.)

Since you asked about vpi, it is simple. Use powermod, the tool designed to solve exactly that problem.

powermod(188,80,34969)
ans =
       14961

As a test:

mod(vpi(188)^80,34969)
ans =
    14961

Of course, the second solution is much slower, since there vpi was forced to compute the full number, then compute the modulus.

Note that you COULD have done the computation using nothing more than doubles.

B = flip(dec2bin(80))
B =
    '0000101'

Bi = find(B == '1') - 1
Bi =
    4     6

So we see that 80 (the exponent) can be written as 80=16+64.

Therefore, 188^80=188^16*188^64

Eventually, you would compute the modulus as:

mod(2993*11969,modulus)
ans =
    14961

So you can actually compute a powermod in double precision as long as the modulus is no larger than sqrt(2^53 - 1).