费马数乘积形式与平方和形式转换研究
2021-11-28周利荣胡天磊
周利荣 胡天磊



摘要:该文分析了费马数素因子乘积形式转换为平方和形式的算法,费马数平方和形式转换为素因子乘积形式的算法。利用转换算法2在极短的时间内(0.02 s)将62位素数934616397153579777691635581996068965840512375416381885802 80321分解成平方和形式。综合利用两种算法部分分解费马数F12。
关键词:费马数;费马平方和定理;吕卡定理
中图分类号:TP312 文献标识码:A
文章编号:1009-3044(2021)28-0114-03
开放科学(资源服务)标识码(OSID):
1 背景
表达式Fn=[22n]+1称为费马数,当n取0、l、2、3、4时的值分别为3、5、17、257、65537,并均为素数。由此,费马提出一个猜想:形如Fn=[22n]+l的数一定为素数。数学家欧拉发现,当n取5时,F5=4294967297=641*6700417不为素数。费马素数除了被费马本人所证实的那五个外竟然没有再发现一个。费马数问题促进素性判定算法和整数的分解算法的研究。
2 费马数性质
有关定理及性质:
1)费马平方和定理:任何一个4p+1型素数可表成两个整数的平方和,且表示方法是唯一的。
2)吕卡定理:费马数Fn=[22n]+1的素因数必具p=k.[2n+2]+l的形式,其中k为正整数[1]。
3)性质1:当n≥2时,费马数Fn=[22n]+1的末位数为7[2]。
4)性质2:([u2+v2])*([a2+b2])=[(ua+vb)2] +([va-ub)2]。
5)性质3:([u2+v2])*([a2+b2])=[(ua-vb)2] +([va+ub)2]。
3 费马数素因子乘积形式转换成平方和形式
3.1 转换的依据
由吕卡定理可知费马数的素因数必具k.[2n+2]+l的形式,即为4p+1型的素数。由费马平方和定理可知任何一个4p+1型素数可表成两个整数的平方和,且表示方法是唯一的。由性质2:([u2+v2])*([a2+b2])= [(ua+vb)2] +([va-ub)2],可知整数的平方和的乘积仍为平方和。因此,费马数一定可以转换成整数的平方和形式。
3.2 转换算法1(穷举法)
输入:费马数的素因数pi(1≤i≤k)。
输出:费马数的平方和形式。
1)i=1;
2)tmp=pi ,t=[pi]-1;
3)tm=tmp-[t2];
4)如果tm 是完全平方数,转(5),否则 t--,转(3);
5)保存pi的平方和形式;……p>
