APP下载

费马数乘积形式与平方和形式转换研究

2021-11-28周利荣胡天磊

电脑知识与技术 2021年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的平方和形式;

登录APP查看全文