Ronzii's Blog

Just your average geek's blog

Modular Exponentiation

long long modulo(long long a,long long b,long long c)
{
    long long result=1;
    for(int i=0; i<b; i++)
    {
        result = result*a;
        result = result%c;
    }
    return result;
}

long long mulmod(long long a, long long b , long long c)
{
    long long x=0,y=a%c;
    while(b>0)
    {
        if(b & 1)
        {
            x = (x+y)%c;
        }
        y=(y*2)%c;
        b>>=1;
    }
    return x%c;
}
long long modulo2(long long a,long long b,long long c)
{
    long long y=a,x=1;
    printf("%lld %lld %lld\n",b,x,y);
    while(b>0)
    {
        if(b & 1)
        {
            x = mulmod(x,y,c);
        }
        y = mulmod(y,y,c);
        b>>=1;
    }
    return x%c;
}
Advertisements

March 30, 2012 - Posted by | C++ | , , ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s