合数中二次剩余值的正负性
二次剩余中，一般不存在正负性，因为正负性可以如下进行计算:：
(-a)^2≡(n-a)^2≡a^2 (mod n)
但在计算合数的二次剩余时，如果按一定的规则来运算，二次剩余值会出现负数情况，此时的负数是指t^2≡(-s)^2 (mod n)中s为负情况，而不是指x^2≡-d(mod n)中d为负的这种情况， 以下看看二次剩余值如何经过运算，出现负数的。
一、二次剩余值为负的情况
设n=2k+1，k≥1，n=ab，1<a<b
根据费马分解有:
t=(a+b)/2 s=(b-a)/2
可得 t+s=b t-s=a
并得:t^2≡s^2(mod n) ①
如果对①式中的左边进行t+a，右边二次剩余值为a-s，此时二项剩余才能成立:
(t+a)^2≡(a-s)^2 (mod n) =﹥
(t+a+a-s)(t+a-a+s)≡0 (mod n) =﹥
3ab≡0 (mod n) 即加a在3n的位置
如果对①式中进行t+b有:
(t+b)^2≡(s+b)^2 (mod n) =﹥
(t+b+s+b)(t+b-s-b)≡0 (mod n) =﹥
3ab≡0 (mod n) 即加b也在3n的位 置
但(t+a)^2≢(s+a)^2 (mod n) ，这种情况下是不成立的。
如果继续对①式中进行t+ua+ⅴt，u≥0 v≥0，①式中的二次剩余值会变为:ua-s-ⅴs，即左边加a，右边也加a，左边加t，右边-s，如下式:
(t+ua+vt)^2≡(ua-s-ⅴs) (mod n) ⑪
上式中，右边移位到左边得:
((1+ⅴ)lt-s)+2ua)((1+v)(t+s))≡0 (mod n) =>
(1+ⅴ+2u)(1+ⅴ)ab≡0 (mod n) 该式成立。
根据上述，可得t、s、a、b共4个参考值，其中b与s正负相同，与a正负反，即b、s为正时，a为负，b、s为负时，a为正，而ua-s-ⅴs可正可负(本文中，a定义为正，b、s定义为负)，
再给一个值： 1/2≡h(mod a)，便于下面②式的计算。
同时给出之前的一个公式(请参考之前的文章):
d^2≡d+(j-1)j (mod n) j≥0 ②
对①式的t加h，可以得到②式中连续两个整数积:
(t+h)^2≡t+h+(h-s-1)(h-s) (mod n ) ③
证:上式右边移到左边得:
(t+h-(h-s))(t+h+(h-s-1))≡0 (mod n) =﹥
(t+s)(t-s+2h-1)≡0 (mod n) =>
b*(a+a)≡0 (mod n) =>
2ab≡0 (mod n) 上式成立，t+h在2n位置，证毕。
③式中h-s可能为正，也可能为负。
以下举例来说明二次剩余值的变化，便于了解二次剩余值出现负的情况:
例1 n=299=13*23 根据费马分解有:
18^2≡5^2 (mod 299) ⑴
t=18 s=5 a=13 b=23 h=7≡1/2 (mod 13)
当然也有 13^2≡13^2 (mod 299) ⑵
现对⑴中按如下进行二次剩余计算
⑴式左边加a=13，可得二次剩余: (18+13)^2≡(13-5)^2 =>31^2≡8^2 (mod 299)
上式左边加t=18，可得二次剩余:(31+18)^2≡(8-5)^2 =>49^2≡3^2 (mod 299)
左边继续加t=18得:(49+18)^2≡(3-5)^211 =﹥ 67^2≡(-2)^2 (mod 299)，此时二次剩余值出现为负
继续加t=18得:l67+18)^2≡(-2-5)^2 => 85^2≡(-7)^2 (mod 299)
此时加a=13得: (85+13)^2≡(-7+13)^2 => 98^2≡6^2 (mod 299)
...
对⑵中按如下进行计算
⑵式左边加t=18，可得二次剩余: (13+18)^2≡(13-5)^2 =>31^2≡8^2 (mod 299)
以下与上述计算相同，这里略去
在上述的计算中，二次剩余值出现了负数。
以下为连续整数积的例:
例2：n=299时(值见上面):
(18+7)^2≡(18+7)+(7-5-1)(7-5) => 25^2≡25+1*2 (mod 299)
对上式加t=18得: (25+18)^2≡25+18+(1-5)(2-5) =>43^2≡43+(-4)(-3) (mod 299) 连续整数值为负
继续加t=18得: (43+18)^2≡43+18+(-4-5)(-3-5) =>61^2≡61+(-9)(-8) (mod 299)
此时加a=13得: (61+13)^2≡61+13+(-9+13)(-8+13) =>74^2≡74+4*5 (mod 299)
...
例3：n=799=17*49
32^2≡15^2 (mod 799) h=9≡1/2 (m0d 17)
t=32 s=15 a=17
(32+9)^2≡(32+9)+(9-15-1)(9-15) => 41^2≡41+(-7)(-6) (mod 799) 连续整数为负
对上式加a=17得: (41+17)^2≡41+17+(-7+17)(-6+17) =>58^2≡58+10*11 (mod 799)
...
从上述例中，可知二次剩余中a与s的符号相反，所以才会出现二次剩余值或连续整数值为负的情况，但在实际计算时，还是按正常的二次剩余来什算。
正是由于a与s符号相反，加多个a和加多个t后，其同余值会趋近于一个较小值后，再次散发，如何能得到这个趋近的较小值，这里提供一个方法，供参考。
在提供方法前，先给出一个基本公式。
对于①式和③加多个a和加多个t后,二次剩余值会位于l*n，而l*n能够通过以下公式得到:
1) ⑪式二次剩余值(ua-(1+ⅴ)s)^2可以转换成如下计算
(mt-js)^2 j≥2，m≥1, ④ 可以得到该二次剩余值位于 (j^2-m^2)*n的位置,其中 mt-js可正可负 (还有另一值（mt+js)，因为散发，不讨论)
2） 对于③式中，多次加a和加t得:
(t+h+ma-jt)^≡t+h+ma-j+(h-s+ma-jt-1)(h-s+ma-jt) (mod n)
连续整数进行如下计算
(h-s+ma-jt) j≥0 m≥0 ⑤ 可以得到该二次剩余值位于 ((j+m+1)(j+m+2)-m(m+1))*n的位置,其中该整数可正可负
我们不关心上述二次剩余值及连续整数值的变化，只关心 二次剩余值及连续整数值何时趋于较小值,则可以通过位于l*n的位置的第一数或者一个较小的偏差值,得到①或③的解，该整数被分解。
二、公式④⑤趋于较小值的一个计算方法
重新设定一下条件
设n=2k+1 k≥1，n=ab , 1<a<b<2a (n,t)=1
可设定 b=a+c, c<a
如果上式中的c=h (h≡1/2 (mod a)):，可得费马分解的值如下:
t=(a+a+h)/2=a+h/2 s=h/2 h-s=h/2
因c位于a的1/2，可以表达为m/v，与④式的对应计算为:
m=m，j=2ⅴ+m
公式④中的m=1，j=2*2+1=5，代入④中有:
t-5s=a+h/2 - 5*(h/2)=-1 该值位于(5^2-1)n=24n, 即(sqrt(24n)+1)^2≡(-1)^2 (mod n)
公式⑤加一次t可得: (h-s)-s=0
该值位于((1+0+1)(1+0+2)-0*(0+1))n=6n, 即(sqrt(6n)+1)^2≡sqrt(6n)+1 (mod n)
以下举例说明:
例4 66887=211*317 264^2≡53^2 (mod 66887)
有t=264 s=53 a=211 b=317 h=106≡1/2 (mod 211)
b=211+106=317 此时表示为 1/2 , 5=2*2+1
上述值代入公式④
264-5*53=-1 或 (317-317)*2-1=-1
sqrt(24*66887)+1)=1267
1267^2≡(-1)^2 (mod 66887)
上述值代入公式⑤
106-53-53=0 或 317-317=0
sqrt(6*66887)+1=634
634^2≡634+(0-1)*0 => 634^2≡634 (mod 66887)
例5 380771=503*757 630^2≡127^2 (mod 380771)
有t=630 s=127 a=503 b=757 h=252≡1/2 (mod 503) a+h=755
b=757 在 1/2 的附近 5=2*2+1
代入公式④ 630-5*127=-5 或 (755-757)*2-1=-5
sqrt(24*380771)+1=3023
3023^2≡(-5)^2 (mod 380771)
代入公式⑤: 252-127-127=-2 或 755-757=-2
sqrt(6*380771)+1)=1512
1512^2≡1512+(-2-1)*(-2) => 1512^2≡1512+(-3)(-2) (mod 380771)
如果c≡m/v(mod a), v≥2 m≥1 (m,v)=1 则④式和⑤式的值趋近于较小值
.公式④中的 j=2v+m 二次剩余值为 (mt-(2v+m)s)^2 位于((2v+m)^2-m^2)*n ⑥
公式⑤中的整数值为 h-s+((m-1)/2)a-(j-1)s , 位于((j+(m-1)/2)(j+(m-1)/2 +1)-((m-1)/2)((m-1)/2 +1))*n ⑦
以下以a=503为例来说明
例6 378≡3/4 (mod 503)
443143=503*881 692^2≡189^2 (mod 443143)
得t=692 s=189 a=503 b=881 c=378≡3/4 (mod 503) a+c=881
b=a+c 11=2*4+3
代入公式⑥有 3*692-11*127=-3 或 (881-881)*2-3=-3
并得 11^2-3^2=112
sqrt(112*443143)+1=7045
7045^2≡(-3)^2 (mod 443143)
代入公式⑦ 252-189+503-3*189=-1 或 (881-881)*(4/2)-(3-1)/2=-1
并得 (4+1)(4+1+1)-1*2=28
sqrt(28*443143)+1)=3523
3523^2≡3523+(-1-1)*(-1) => 3523^2≡3523+(-2)(-1) (mod 443143)
例7 315≡5/8 (mod 503)
412963=503*821 662^2≡159^2 (mod 412963)
得t=662 s=159 a=503 b=821 c=315≡5/8 (mod 503) a+c=818
b=821 在5/8的附近 21=2*8+5
代入公式⑥ 5*662-21*159=-29 或 (818-821)*8-5=-29
并得 21^2-5^2=416
sqrt(416*412963)+1=13107
13107^2≡(-29)^2 (mod 412963)
代入公式⑦ 252-159+((5-1)/2)*503-(8-1)*189=-14 或 (818-821)*(8/2)-(5-1)/2=-14
并得 (8+2)(8+2+1)-2*3=104
sqrt(104*412963)+1)=6554
6554^2≡6554+(-14-1)*(-14) => 6554^2≡6554+(-15)*(-14) (mod 412963)
例8 96≡3/16 (mod 503) 因存在小数位，该值供参考，目前不知道二次剩余中这类小数位的计算，此时不能按同余方法进行计算，更像整数的除法。
302303=503*601 552^2≡49^2 (mod 302303)
得t=552 s=49 a=503 b=601 存在小数位，a+c=599(仅参考，不准确)
b=601 在3/16的附近 35=2*16+3
代入公式⑥有 3*552-35*49=-59 或 存在小数位，无法计算差值
并得 35^2-3^2=1216
sqrt(1216*302303)+1=19173
19173^2≡(-59)^2 (mod 302303)
代入公式⑦ 252-49+((3-1)/2)*503-(16-1)*49=-29 或 存在小数位，无法计算差值
并得 (16+1)(16+1+1)-1*2=304
sqrt(304*302303)+1)=9587
9587^2≡9587+(-29-1)*(-29) => 9587^2≡9587+(-30)*(-29) (mod 302303)
该方法利用了a与s正负性相反的性质，通过比较b与a+c的差值大小而得到，此时c取值为a的m/v，如果b与a+c差值较小 ，可通过上述公式求得，如果差值较大，上述公式基本无效。
三、小结
在上述例中，因a与s的相互相反性，多次加a和加t中，可以让二次剩余值或连续整数值在一定范围来回摆动，让部份值趋于较小值，有点像正弦的波形，不过不清楚合数中二次剩余值正负性的性质、特性，很多问题得不到有效的解决。如果能清楚这些性质、特性，可能会对整数分解有一定的帮助，上述正负性的描述，不是很成熟，还存在不少的问题，欢迎大家批评指正。