根据k与3的同余得到二次剩余值与3的同余
本次文介绍n=4k-1，费马分解的两个值与后序序列的连续两个整数枳的关系，以及在k≡0(mod 3)、k≢0(mod 3)时，a^2≡b(mod n)，√n<a<√(2n)，b与3的整除关系。
一、后序序列连续两个整数积与费马分解值的关系
设n=4k-1，n=ab，1<a<b，根据费马分解有:t^2≡s^2(mod n)，其中:
t=(a+b)/2，s=(b-a)/2
因n=4k-1，则a=4ka+1，b=4kb-1，或者a=4ka-1，b=4kb+1
n=ab=(4ka+1)(4kb-1)=16ka*kb-4ka+4kb-1=4(4ka*kb-ka+kb)-1，即
k=4ka*kb-ka+kb，上式必为4k-1型
又因为根据后序序列有:
c^2-k=i(i-1) ⅰ≥1 ①
=﹥ (2c)^2≡(2ⅰ-1)^2(mod n)
此时2c、2ⅰ-1与t、s的关系为
2c=t，2ⅰ-1=s
以下来证明
∵ k=4ka*kb-ka+kb，要想①式的右边为连续整数积，则:
c=ka+kb，代入上式左边有:
(ka+kb)^2-(4ka*kb-ka+kb) =
(ka)^2+2ka*kb+(kb)^2-4ka*kb+ka-kb =
(ka-kb)^2-(kb-kba ) =
(kb-ka)(kb-ka-1)为连继两个整数积
∴ (2(ka+kb))^2≡2(kb-ka)-1)^2(mod n)
∵t=(a+b)/2=(4ka+1+4kb-1)/2=2(ka+kb)
s=(b-a)/2=(4kb-1-4ka-1)/2=2(kb-ka)-1
也即2c=t ， 2i-1=s
二、k≡0(mod 3)及k≢0(mod 3)时，t与s和3的整除关系
㈠ 、从后序序列证明t、s与3的同余关系
设n=4k-1，n=ab，1<a<b，根据费马分解有: t^2≡s^2(mod n)，其中:
t=(a+b)/2 s=(b-a)/2
再设定(n，3)=1，(t，s)=1，有
如果k≡0(mod 3)，则t≡0(mod 3)
如果k≢0(mod 3)，则s≡0(mod 3)
证明如下:
1、当k≡0(mod 3)，可表示为k=3d
则c可表示为3g、3g±1，分别代入①式中有:
⑴、c≡0(mod 3)，即c=3g有
(3g)^2-3d，可知①式右边必为3的倍数3f，即:
(3g)^2-3d=3f(3f±1)，等式两边都存在3的倍数，上式成立
根据笫一段可得: (6g)^2≡(6f±1)^2(mod n)，也即:
t=6g => t≡0(mod 3)
⑵、c≢0(mod 3)，可令c=3g±1，代入①式可表示为:
(3g±1)^2-3d=(9g^2±6g-3d)+1，该式不为3的倍数，而ⅰ不为3的倍数连续两个整数积的表达为:
(3f+1)(3f+2)=9f^2+9f+2 =>
(9g^2±6g-3d)+1≠9f^2+9f+2 =>
9g^2±6g-3d≠9f^2+9f+1
左边为3的倍数，右边不是3的倍数，该等式不成立
∴ 根据上述情况可知:
当k≡0(mod 3)，则t≡0(mod 3)
2、当k≢0(mod 3)时，s≡0(mod 3)
此时k分别表示为3d+1，3d-1，
⑴、当 k=3d+1，代入n得:
4(3d+1)-1=12d+3，n必为3的倍数，与题设(n，3)=1不符，舍去。
⑵、当k=3d-1时，根据c与3是否能整除，可分为以下情况:
Ⅰ、当c≡0(mod 3)时，可令c=3g，代入①式得:
(3g)^2-(3d-1)，结果不是3的倍数，等式右边必为(3f+1)(3f+2)，可得:
9g^2-3d=9f^2+9f+3，该式可以成立。根据第一段可得
(6g)^2≡(6f+3)^2(mod n)
此时(t，s)=3，与题设不符，舍去。
Ⅱ、当c≢0(mod 3)时，可令c=3g±1，代入①式
(3g±1)^2-(3d-1)=9g^2±6g-3d+2
结果不为3的倍数，等式右边只能为(3f+1)(3f+2)=9f^2+9f+2，即:
9g^2±6g-3d+2=9f^2+9f+2，该结果成立
根据笫一段可得:
(6g±2)^2≡(6f+3)″2 (mod n)
此时:s=6f+3 => s≡0(mod 3)
∴∴综上述可知:
当k≢0(mod 3)，则s≡0(mod 3)
㈡、从前序序列证明c^2≡d(mod n)中d与3的同余关系
设n=4k-1，n=ab，1<a<b，(n，3)=1，c^2≡d(mod n)，√n<c<√(2n)
以下分别讨论当d≥0和d<0这两种情况下，d与3的整除结果。
⑴ 、当d≥0时
Ⅰ、如果 k≡0(mod 3)， 则有d≢0(mod 3)
Ⅱ、如果k≢0(mod 3)，根据c与3的整关系，有以下两种结果:
当c≡0(mod 3)，有d≢0(mod 3)
当c≢0(mod 3)，有d≡0(mod 3)
下面来分别证明。
二次剩余值: d=c^2-n=c^2-(4k-1) ②
1、当k≡0(mod 3)，可设k=3f
Ⅰ、当c≡0(mod 3)，令c=3g，代入②式得:
(3g)^2-(12f-1)=3(3g^2-4f)+1，即
c^2-(4k-1)≡1(mod 3) =>
d≡1(mod 3) 即:
d≢0(mod 3)
Ⅱ、当c≢0(mod 3)时，令c=3g±1，代入②式得
(3g±1)^2-(12f-1)=3(3g^2±2g-4f)+2，即
c^2-(4k-1)≡2(mod 3) =>
d≡2(mod 3)， 即:
d≢0(mod 3)
综合上述两种情况，得:
当k≡0(mod 3)时， 有d≢0(mod 3)
当k≢0(mod 3) 时， k可分别表示为:3f-1和3f+1，以下分别证明
2、当k=3f-1时，即k≡-1(mod 3)
Ⅰ、当c≡0(mod 3时，令c=3g，代入②式得:
(3g)^2-(12f-5)=3(3g^2-4f)+5，即
c^2-(4k-1)≡2(mod 3)
即 d≢0(mod 3)
Ⅱ、当c≢0(mod 3)时， c=3g±1，代入②式得
(3g±1)^2-(12f-5)≢=3(3g^2±2g-4f+2) 即
c^2-(4k-1)≡0(mod 3)
即 d≡0(mod 3)
3、当k=3f+1，即k≡1(mod 3)，4(3f+1)-1=12f-3，此时(n，3)=3，与题设不符，舍去。
根据上述可知:
当k≢0(mod 3) 时，分为以下两种情况:
当c≡0(mod 3)时，有d≢0(mod 3)
当c≢0(mod 3)时，有d≡0(mod 3)
⑵、当d<0时，则有:
Ⅰ、如果k≡0(mod 3)，有以下两种结果:
当c≢0(mod 3)，有d≡0(mod 3)
当c≡0(mod 3)，有d≢0(mod 3)
Ⅱ、如果k≢0(mod 3)，则d≢0(mod 3)
证明略。
三、小结
以上分别就n=4k-1型整数时，说明了k与3的整除关系，可得到二次剩值与3的整除结果，当然上述论述也会存在不足，欢迎大家批评指正。
[培训]Windows内核深度攻防：从Hook技术到Rootkit实战！
