Fermat素性检验
实验环境
- 电脑：联想拯救者R9000p
- cpu：AMD Ryzen 7 5800H
- 内存：16GB
- 操作系统：windows11
- python版本：3.10
目标：
- 掌握python基本函数库的使用
- 熟悉抽象代数的基本定理如Fermat小定理的使用
- 理解Fermat素性检验的原理，并编程实现
- 测试一些大数，以一定概率检验其素性
Fermat素性检验介绍
背景
费马素性检验是一种素数判定法则，利用随机化算法判断一个数是合数还是可能是素数。
Fermat小定理
\[
对\forall(a,p)=1,p为质数\\
\exists a^{p-1} \equiv 1 \pmod{p}
\]
证明：
\(\{1,2,3,4...p-1\}\)是p的既约剩余系
\(\because a,p\)互质
\(\therefore \{a*1 , a*2 , a*3 , a*4
,\dots,a*(p-1)\}\)也为p的既约剩余系
\(\therefore 1*2*3 \dots
*(p-1)≡a*2*a*3*a......(p-1)*a \pmod{p}\)
化简得\(a^{p-1} \equiv 1
\pmod{p}\)
Fermat素性检验基本原理
根据费马小定理：如果p是素数，\(1\leq a \leq p-1\)
那么 \[
a^{p-1} \equiv 1 \pmod{p}
\]
如果我们想知道n是否是素数，我们在中间选取a，看看上面等式是否成立。
- 如果对于数值a等式不成立，那么n是合数。
- 如果有很多的a能够使等式成立，那么我们可以说n可能是素数，或者伪素数。
在我们检验过程中，有可能我们选取的a都能让等式成立，然而n却是合数，所以最终得到的结果是，我们以一定概率确定p是否为素数
Fermat素性检验流程
给定奇整数 \(m\geq3\) 和安全参数
\(k=5\) （1） 随机选取整数\(a\),令\(2\leq a
\leq m-2\) （2） 计算\(g=(a,
m)\)，如果\(g
=1\)，转（3）；否则，跳出，m为合数 （3） 计算\(r
=a^{m-1}\pmod{m}\)，如果r=1,m可能是素数，转（1）；否则，跳出，m为合数
（4） 重复上述过程k次，如果每次得到m可能为素数，则m为素数的概率为\(1- \frac1{2^k}\) 。
python代码
需要导入math模块求最大公因数
需要导入random模块来产生随机数
求\(r
=a^{m-1}\pmod{m}\)必须使用pow(a,num-1,num)函数一边乘法一边取模运算速度较快，不能先算\(a^{m-1}\)再取模，否则时间太长算不出来
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| import math
import random
def is_prime(num, k=7):
for _ in range(k):
a=random.randrange(2,num-2)
if math.gcd(a, num)!=1:
return False, 1-(0.2)**k
if pow(a,num-1,num)!=1:
return False , 1-(0.2)**k
return True , 1-(0.2)**k
m1 = 743476040059754298379331647007684224429004972336533937786799284757790400765316630522369642718204165253922832684184615021404737105614714107158733905598636152327037707290538422718453498125366750918857659068838460954633737911274770976191590193809661578032117496009853673140977556559136466107768672598883924301125589893895001253674886100289402530711221893
m2 = 5434520625653357625890820149570485819447986258433769976634917091398967074086679540928507095017715540385352266035820823142060119390272763774034231321959236056764511968630360067353876686142517564224926196131349204754111599877101485686283117193149781387816214484583521923017500621725053392290279263586984207169423800476914654441473576611460323772832328657
m3 = 876147742992673125957404768949712978720573116974723188491435550196169965040848206868200084918233743662847668000971402407461887306389122707315529364807593342507936022301657320206278702095378618110195051280478534126716517153056984269659532882692418682262081495725304483536777013188527470348249542840277926802938912332306310470632601156641005608958891
m4 = 9876147742992673125957404768949712978720573116974723188491435550196169965040848206868200084918233743662847668000971402407461887306389122707315529364807593342507936022301657320206278702095378618110195051280478534126716517153056984269659532882692418682262081495725304483536777013188527470348249542840277926802938912332306310470632601156641005608958891
result , pr = is_prime(m4)
if result:
print("该数以",pr*100,"%的概率判定为素数")
else:
print("该数不是素数")
|