Calculate the modulus of a number at a certan power (the number at that power is quite big)

I want to calculate the RSA algorithm by myself . I need to calculate the modulus of a number at a certain power. The thing is that that number at that certain power can get quite big.

Here is what i want :

x = pow(n, p) % q

开发者_运维百科How can I efficiently determine x?

If you're using .NET 4, I suggest you look at BigInteger, which even provides the ModPow method to do it all in a single operation :)

BigInteger n = ...;
BigInteger p = ...;
BigInteger q = ...;
BigInteger x = BigInteger.ModPow(n, p, q);

This is known as the powermod function:

function modular_pow(base, exponent, modulus)
    c := 1
    for e_prime = 1 to exponent 
        c := (c * base) mod modulus
    return c

This can be made more efficient by applying exponentiation by squaring:

function modular_pow(base, exponent, modulus)
    result := 1
    while exponent > 0
        if (exponent & 1) equals 1:
           result = (result * base) mod modulus
        exponent := exponent >> 1
        base = (base * base) mod modulus
    return result

Please check this topic and this article on ways to make the mathematical function more efficient in itself.

See BigInteger.ModPow (Fx 4+), here is the MSDN.

Trivially...

x = 1
for(i = 0; i < p; i++)
   x = (x*n) % q

Theres more efficient ways such as binary exponentiation rather than this naive iteration, but this does get past the overflow problem as x is bounded by n*q

Although all the answers provided here are correct I mis the obvious square-and-multiply algorithm, which is the "classic" way to implement modular exponentiation.

If you plan to write your own version of Modpow():

You only need the power modulo q, so your calculations don't need to use any number bigger than q^2, using the fact that:

if a = b (mod q) then a*p = b*p (mod q)

Therefore, when calculating the power n^p, after every multiplication, do a (modulo q) operation on your working variable.

Additionally, if q is prime, you can use Fermat's little theorem, which states that:

a^(q-1) = 1 (mod q)
    (when a is not a multiple of q)

This can be used to shorten the calculations when p is (much) bigger than q