费马小定理 素数判定 蒙哥马利算法
玛丽莲梦兔
715次浏览
2021年01月29日 04:15
最佳经验
本文由作者推荐
食品安全工作总结-word目录生成
费马小定理
素数
判定
蒙哥马利
算法
(
强烈推荐）
2009-11-07
12:42
费马小定理
素数判定
蒙哥马利算法
约定：
x%y
为
x
取模
y
，即
x
除以
y
所得的余数，当
x
x%y=x
，所有取模的运算对象都为整数。
x^y
表示
x
的
y
次方。
乘方运算的优先级高于乘除和取模，加减的优先级最低。
见到
x^y/z
这样，就先算乘方，再算除法。
A/B
， 称为
A
除以
B
，也称为
B
除
A
。
若
A%B=0
，即称为
A
可以被
B
整除，也称B
可以整除
A
。
A
*B
表示
A乘以
B
或称
A
乘
B
，
B
乘
A
，
B
乘以
A
……都
TMD
的一样，靠！
复习一下小学数学
公因数：两个不同的自然数
A
和
B，若有自然数
C
可以整除
A
也可以整除
B
，那么
C
就是
A
和
B
的公因数。
公倍数：两个不同的 自然数
A
和
B
，若有自然数
C
可以被
A
整 除也可以被
B
整除，那么
C
就是
A
和
B
的 公倍数。
互质数：两个不同的自然数，它们只有一个公因数
1
，则称它们互质。
费马是法国数学家，又译“费尔马”
，此人巨牛，他的简介请看下面。不看不知道，一看吓一跳。< br>
http://www
./BasicStudy/LearnColumn/Mat hs/shuxuejiashi/
费马小定理：
有
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
的
P
次方减
N
可以被< br>P
整除，因为由费马小定理知道
N
的
P
次方除以
P< br>的余数是
N)
把
N
提出来一个，
N^P
就成了你< br>N*(N^(P-1))
，那么
(N^P-N)%P=0
可化为：
(N *(N^(P-1)-1))%P=0
请注意上式，含义是：
N*(N^(P-1)-1)< br>可以被
P
整除
又因为
N*(N^(P-1)-1)
必能整除
N
（这不费话么
!
）
所以，
N*(N^ (P-1)-1)
是
N
和
P
的公倍数，小学知识了
^_^
又因为前提是
N
与
P
互质，而互质数的最小公倍数为它们的乘积，所 以一定存在正整数
M
使得等式成立：
N*(N^(P-1)-1)=M*N*P
两边约去
N
，化简之：
N^(P-1)-1=M*P
因为
M
是整数，显然：
(N^(P-1)-1)%P=0
即：
N^(P-1)%P=1
============================================
积模分解公式
先有一个引理，如果有：
X%Z=0
，即
X
能被
Z
整除，则有：
(X+Y)%Z=Y%Z
这个不用证了吧
...
设有
X
、
Y
和
Z
三个正整数，则必有：
(X*Y)%Z=((X%Z)*(Y%Z))%Z
想了很长时间才证出来，要分情况讨论才行：
1.
当
X
和
Y
都比
Z
大时，必有整数
A
和
B
使下面的 等式成立：
X=Z*I+A
（
1
）
Y=Z*
J+B
（
2
）
不用多说了吧，这是除模运算的性质！
将（
1
）和（
2< br>）代入
(X*Y)modZ
得：
((Z*I+A)(Z*
J+B))% Z
乘开，再把前三项的
Z
提一个出来，变形为：
(Z*(Z*I*
J+I*
A+I*B)+A*B)%Z
（
3
）
因为
Z*(Z*I*
J+I*
A+I*B)
是
Z
的整数倍……晕，又来 了。
概据引理，
（
3
）式可化简为：
(A
*B)%Z
又因为：
A=X%Z
，
B=Y%Z
，代入上面的式子，就成了原式了。
2.
当
X
比
Z
大而
Y
比
Z< br>小时，一样的转化：
X=Z*I+A
代入
(X*Y)%Z
得：
(Z*I*Y+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
，所以原式成立。
====== ===============================================
快速计算乘方的算法
如计算
2^13
，则传统做法需要进行
12
次乘法。
/*
计算
n^p*/
unsigned power(unsigned n,unsigned p)
{
for(int i=0;i
return n;
}
该死的乘法，是时候优化一下了！把
2*2
的结果保存起来看看，是不是成了：
4*4*4*4*4*4*2
再把
4*4
的结果保存起来：
16*16*16*2
一 共
5
次运算，分别是
2*2
、
4*4
和
16*16 *16*2
这样分析，我们算法因该是只需要计算一半都不到的乘法了。
为了讲清这个算法，再举一个例子
2^7
：
2*2*2*2*2*2*2
两两分开：
(2*2)*(2*2)*(2*2)*2
如果用
2*2
来计算，那么指数就可以除以
2
了，不过剩了一个，稍后再单独乘上它 。
再次两两分开，指数除以
2
：
((2*2)*(2*2))*(2*2)*2
实际上最后一个括号里的
2 * 2
是这回又剩下的，那么，稍后再单独乘上它
现在指数已经为
1
了，可以计算最终结果了：
16*4*2=128
优化后的算法如下：
unsigned Power(unsigned n,unsigned p)
{
unsigned main=n; //
用
main
保存结果
unsigned odd=1; //odd
用来计算“剩下的”乘积
while (p>1)
{//
一直计算，直到指数小于或等于
1
if((p%2)!=0)
{//
如果指数
p
是奇数，则说明计算后 会剩一个多余的数，那么在这里把它乘到结果中
odd*=main; //
把“剩下的”乘起来
}
main*=main; //
主体乘方
p/=2; //
指数除以
2
}
return main*
odd; //
最后把主体和“剩下的”乘起来作为结果
} < br>够完美了吗？不，还不够！看出来了吗？
main
是没有必要的，并且我们可以有更快的 代码来判断奇数。要知道除法或取模运算的效率很
低，所以我们可以利用偶数的一个性质来优化代码，那 就是偶数的二进制表示法中的最低位一定为
0!
完美版：
unsigned Power(unsigned n, unsigned p)
{ //
计算
n
的
p
次方
unsigned odd = 1; //oddk
用来计算“剩下的”乘积
while (p > 1)
{ //
一直计算到指数小于或等于
1
if (( p & 1 )!=0)
{ //
判断
p
是否奇数，偶数的最低位必为
0
odd *= n; //
若
odd
为奇数，则把“剩下的”乘起来
}
n *= n; //
主体乘方
p /= 2; //
指数除以
2
}
return n * odd; //
最后把主体和“剩下的”乘起来作为结果
}
======================================== ================
蒙格马利”快速幂模算法
后面我们会用到这样一种运算：
(X^Y)%Z
问题是当
X
和Y
很大时，只有
32
位的整型变量如何能够有效的计算出结果？
考虑上面那份最终的优化代码和再上面提到过的积模分解公式，我想你也许会猛拍一下脑门，吸口气说：
“哦，我懂了！
”
。
下面的讲解是给尚没有做出这样动作的同学们准备的 。
X^Y
可以看作
Y
个
X
相乘，即然有积模分解公式，那么 我们就可以把
Y
个
X
相乘
再取模的过程分解开来，比如：
( 17^25)%29
则可分解为：
( ( 17 * 17 ) % 29 * ( 17 * 17 ) % 29 *
……
如果用上面的代码将这个过程优化，那么我们就得到了著名的“蒙格马利”快速幂模算法：
unsigned Montgomery(unsigned n, unsigned p, unsigned m)
{ //
快速计算
(n ^ e) % m
的值，与
power
算法极类似
unsigned r = n % m; //
这里的
r
可不能省
unsigned 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^e)%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;
}
======================================== =============
怎么判断一个数是否为素数？
笨蛋的作法：
bool IsPrime(unsigned n)
{
if (n<2)
{ //
小于
2
的数即不是合数也不是素数
throw 0;
}
for (unsigned i=2;i
{ //
和比它小的所有的数相除，如果都除不尽，证明素数
if (n%i==0)
{//
除尽了，则是合数
return false;
}
}
return true;
}
一个数去除以比它的一半还要大的数，一定除不尽，所以还用判断吗？？
下面是小学生的做法：
bool IsPrime(unsigned n)
{
if (n<2)
{//
小于
2
的数即不是合数也不是素数
throw 0;
}
for(unsigned i=2;i
{ //
和比它的一半小数相除，如果都除不尽，证明素数
if ( 0 == n % i )
{ //
除尽了，合数
return false;
}
}
return true; //
都没除尽，素数
}