wujiawei@HIT

ACM -- Fighting

常用链接

统计

最新评论

转载自某百度空间 “素数分解为平方和 ”


素数分解为平方和

定理:设p是素数,则p是两个数的平方和,当且仅当p≡1 (mod 4)或p=2。

要由p≡1 (mod 4)推出p是两个数的平方和需要使用费马的无限下降算法:设p≡1 (mod 4),目的是找出A2+B2=p的一组解。

1 先找出一组可行解满足A2+B2=Mp,其中M<p。可以让A取x2≡-1 (mod p)的某个解,B取1。任取一个数1<a<p,计算A≡a(p-1)/4 (mod p),则由24章的定理可知A2≡a(p-1)/2≡(a/p) (mod p),即A2不是1就是-1,而且概率都是50%。多取几次a,必定能找到A2≡-1 (mod p)的解。

2 计算u≡A,v≡B,且-0.5M<=u,v<=0.5M的u和v。

3 由于u2+v2≡A2+B2≡0 (mod M),可设u2+v2=Mr(1<=r<M)。

4 相乘,即(u2+v2)(A2+B2)=M2rp。

5 上式可化为(uA+vB)2+(vA-uB)2=M2rp。

6 左右都除以M2,得

((uA+vB)/M)2+((vA-uB)/M)2=rp。

可以证明M|uA+vB且M|vA-uB。

7 若r=1,则算法结束,否则转2.

算法每次都维护一组可行解A2+B2=Mp,且每次执行都使得M单调递减。实际上,可以证明r<=M/2,即系数至少会折半,因此总的运行次数是log级的。

对于任意整数a,如果a=p1p2,且p1,p2都是符合上一章中分解条件的素数。设p1=u2+v2,p2=A2+B2,则

a= (u2+v2)(A2+B2)=(uA+vB)2+(vA-uB)2

换句话说,只要a分解质因数后所有的因子都是可分解的素数,则a可分解为两个整数的平方和。

定理:(a) 设m是正整数,且m=p1p2…pr,其中p1…pr互不相同。则m可分解为两个整数的平方和当且仅当所有的pi≡1 (mod 4)或等于2。

(b) m可写成m=a2+b2 (其中gcd(a,b)=1)当且仅当它满足下列条件之一:

(i) m是奇数且任何m的素因数模4余1

(ii) m是偶数,m/2满足(i)。

再考虑一下勾股数,可以得出结论:

一个数c是一组本原勾股数中最大的数,当且仅当c的素因数都模4余1。

posted on 2010-08-18 08:34 wujiawei 阅读(336) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理