Geek Answers Handbook

Calculate the module of the number at the power of certan (the number at this power is quite large)

I want to calculate the RSA algorithm myself. I need to calculate the modulus of a number at a certain power. The fact is that this number at a certain power can become quite large.

Here is what I want:

x = pow(n, p) % q

How can I efficiently determine x?

+2
source share
7 answers

If you are using .NET 4, I suggest you look BigInteger, which even provides ModPow, to do all this in one operation :)

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

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

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

, .

+2

...

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

, , , , x n * q

+1

. BigInteger.ModPow (Fx 4+), MSDN.

+1

Modpow():

q, , , q^2, , :

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

n^p ( q) .

, q , , , :

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

, p () q

0

, , , "" .

0

More articles:


All Articles