模乘运算和模幂运算

unsigned __int64 MulMod(unsigned __int64 a,unsigned __int64 b,unsigned __int64 m)  // (a*b)%n = (a%n)*(b%n)%n
{
    // return (a % n)*(b % n )% n; will overflow!so...
    unsigned __int64 s = 0, i;
    a %= m; 
    b %= m;
    for (i=b; i>0; a = (a<<1)%m,i>>=1)
        if (i&1) 
            s = (s+a) % m;
        return s;
}

unsigned __int64 PowMod(unsigned __int64 base,unsigned __int64 pow,unsigned __int64 n)//a^b mod n
{
    unsigned __int64  a=base, b=pow, c=1;
    while (b)
    {
        while( !(b & 1) )
        {
            b>>=1;
            a= MulMod(a, a, n);
        }
        b--;
        c=MulMod(a, c, n);
    }
    return c;
}

posted on 2011-06-05 11:13 ylka 阅读(975) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年6月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

导航

统计

常用链接

留言簿

随笔分类

随笔档案

技术博客

技术站点

搜索

最新评论

阅读排行榜