(转)费马小定理,积模分解公式,高效幂,快速幂模 及 米勒-拉宾检验

[ ]

The content is recoverd from Wordpress Blog, for more details please check HERE

December 19, 2014

VOID001 Comments 0 Comment

好文章,整理收藏。1.费马小定理:

有N为任意正整数,P为素数,且N不能被P整除(显然N和P互质),则有:

N^P%P=N(即:N的P次方除以P的余数是N)   或  (N^(P-1))%P=1

互相变形

原式可化为:

(N^P-N)%P=0

(N*(N^(P-1)-1))%P=0

所以,N*(N^(P-1)-1)是N和P的公倍数

又因为 N与P互质,而互质数的最小公倍数为它们的乘积

所以一定存在正整数M使得等式成立:N(N^(P-1)-1)=MN*P

所以N^(P-1)-1=M*P

因为M是整数

所以(N^(P-1)-1)%P=0

即:

N^(P-1)%P=1

2.积模分解公式

引理,若:X%Z=0,则(X+Y)%Z=Y%Z

设有X、Y和Z三个正整数,则必有:(XY)%Z=((X%Z)(Y%Z))%Z

证明:

1. 当X和Y都比Z大时,必有整数A和B使下面的等式成立:

X=Z*I+A(1)

Y=Z*J+B(2)除模运算的性质

将(1)和(2)代入(X*Y)modZ得:

((ZI+A)(ZJ+B))%Z

所以 (Z(ZIJ+IA+IB)+AB)%Z(3)

所以 Z(ZIJ+IA+I*B)能被Z整除

概据引理,(3)式可化简为:(A*B)%Z

又因为:A=X%Z,B=Y%Z,代入上式,成为原式右边。

2. 当X比Z大而Y比Z小时:

X=Z*I+A

代入(X*Y)%Z得:

(ZIY+A*Y)%Z

根据引理,转化得:(A*Y)%Z

因为A=X%Z,又因为Y=Y%Z,代入上式,即得到原式右边。

同理,当X比Z小而Y比Z大时,原式也成立。

3. 当X比Z小,且Y也比Z小时,X=X%Z,Y=Y%Z,所以原式成立。

3.快速乘方算法

可参见http://www.cnblogs.com/bl4nk/archive/2011/04/20/2022998.html  中的power函数

unsigned Power(unsigned n, unsigned p)  //n^p
{
    unsigned ans = 1;
    while (p > 1)
    {
      if (( p & 1 )!=0)  ans *= n;
      n *= n; 
      p /= 2;
     }
    return n * ans;
}

4.”蒙格马利”快速幂模算法

\_int64 Montgomery(\_\_int64 n, \_\_int64 p, \_\_int64 m)
{ // 快速计算 (n ^ p) % m 的值,与power算法极类似
    \_\_int64 r = n % m; // 这里的r可不能省
    \_\_int64 k = 1;
    while (p > 1)
    {
        if ((p & 1)!=0)
        {
            k = (k * r) % m; // 直接取模
        }
        r = (r * r) % m; // 同上
        p /= 2;
    }
    return (r * k) % m; // 还是同上 
}

蒙格马利极速版:

unsigned Montgomery(unsigned n,unsigned p,unsigned m)
{ //快速计算(n^p)%m的值
      unsignedk=1;
      n%=m;
     while(p!=1)
     {
         if(0!=(p&1))k=(k*n)%m;
         n=(n*n)%m;
         p>>=1;
    }
    return(n*k)%m;
}

5.素数判断

根据费马小定理,对于两个互质的素数N和P,必有:N^(P-1)%P=1 费马测试  算法思路是这样的:

对于N,从素数表中取出任意的素数对其进行费马测试,如果取了很多个素数,N仍未测试失败,那么则认为N是素数。当然,测试次数越多越准确,但一般来讲50次就足够了。费马测试并不完全可靠。

现在我们发现了重要的一点,费马定理是素数的必要条件而非充分条件。这种不是素数,但又能通过费马测试的数字还有不少,数学上把它们称为Carmichael数,现在数学家们已经找到所有10 ^ 16以内的Carmichael数,最大的一个是9585921133193329。我们必须寻找更为有效的测试方法。数学家们通过对费马小定理的研究,并加以扩展,总结出了多种快速有效的素数测试方法,目前最快的算法是米勒-拉宾检验算法。米勒-拉宾检验 wikipedia : Miller–Rabin primality test

米勒-拉宾检验是一个不确定的算法,只能从概率意义上判定一个数可能是素数,测试用的素数表越多,准确率越高,但并不能确保。算法流程如下:

1.选择T个随机数A,并且有A<N成立。

2.找到R和M,使得N=2RM+1成立。

快速得到R和M的方式:N用二进制数B来表示,令C=B-1。因为N为奇数(素数都是奇数),所以C的最低位为0,从C的最低位的0开始向高位统计,一直到遇到第一个1。这时0的个数即为R,M为B右移R位的值。

3.如果A^M%N=1,则通过A对于N的测试,然后进行下一个A的测试

4.如果A^M%N!=1,那么令i由0迭代至R,进行下面的测试

5.如果A^((2^i)*M)%N=N-1则通过A对于N的测试,否则进行下一个i的测试

6.如果i=r,且尚未通过测试,则此A对于N的测试失败,说明N为合数。

7.进行下一个A对N的测试,直到测试完指定个数的A

通过验证得知,当T为素数,并且A是平均分布的随机数,那么测试有效率为1 / ( 4 ^ T )。如果T > 8那么测试失误的机率就会小于10^(-5),这对于一般的应用是足够了。如果需要求的素数极大,或着要求更高的保障度,可以适当调高T的值。

下面是代码:

bool RabbinMillerTest( unsigned n ) 
{
    if (n<2)
    { // 小于2的数即不是合数也不是素数
        throw 0;
    }

    const unsigned nPrimeListSize=sizeof(g\_aPrimeList)/sizeof(unsigned);//求素数表元素个数
    for(int i=0;i<nPrimeListSize;++i)
    {// 按照素数表中的数对当前素数进行判断
        if (n/2+1<=g\_aPrimeList[i])
        {// 如果已经小于当前素数表的数,则一定是素数
            return true;
        }
        if (0The content is recoverd from Wordpress Blog, for more details please check [HERE](recover-my-blog)n%g\_aPrimeList[i])
        {// 余数为0则说明一定不是素数
            return false;
        }
    }
    // 找到r和m,使得n = 2^r * m + 1;
    int r = 0, m = n - 1; // ( n - 1 ) 一定是合数
    while ( 0 The content is recoverd from Wordpress Blog, for more details please check [HERE](recover-my-blog) ( m & 1 ) )
    {
        m >>= 1; // 右移一位
        r++; // 统计右移的次数
    }
    const unsigned nTestCnt = 8; // 表示进行测试的次数
    for ( unsigned i = 0; i < nTestCnt; ++i )
    { // 利用随机数进行测试,
        int a = g\_aPrimeList[ rand() % nPrimeListSize ];
        if ( 1 != Montgomery( a, m, n ) )
        {
            int j = 0;
            int e = 1;
            for ( ; j < r; ++j )
            {
                if ( n - 1 The content is recoverd from Wordpress Blog, for more details please check [HERE](recover-my-blog) Montgomery( a, m * e, n ) )
                {
                    break;
                }
                e <<= 1;
            }
            if (j The content is recoverd from Wordpress Blog, for more details please check [HERE](recover-my-blog) r)
            {
                return false;
            }
        }
    }
    return true;
}

在2^31-1以下,有一些伪素数可以通过{2,3,5,7,11}的测试,已知的有 29341 = 13 * 37 * 61 , 3215031751 = 151 * 751 * 28351


Uncategorized C. Linux, kernel, Laravel, PHP, Python, Shell, Web, wine


Historical Comments

Post navigation ————— NEXT
快速幂算法 NEU 1391
PREVIOUS [转] 35 BEST PLACES TO LEARN HOW TO CODE QUICKLY

Back