合数中二次剩余值的正负性
二次剩余中，一般不存在正负性，因为正负性可以如下进行计算:： (-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)^2 (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)^2 =﹥ 67^2≡(-2)^2 (mod 299)，此时二次剩余值出现为负 继续加t=18得 (67+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
...(已截断)
---
来源: 看雪论坛
原文链接: https://bbs.kanxue.com/thread-286333.htm
[原创]整数分解随笔(合数中二次剩余的正负性)
230 浏览
2 回复
四、费马分解与扩展欧几里得算法的关系
设n=2k+1，n=ab，1<a<b，根据费马分解可得:
t^2≡s^2 (mod n) ， (t，s)=1
对上式中的t和s，按扩展欧几里得算法有:
t-q_1*s=r_1
s-q_2*r_1=r_2
r1-q_3*r_2=r_3
r_(ⅰ-2)-q_i*r_(ⅰ-1)=r_i
r_(m-2)-q_m*r_(m-1)=1
如果在第i步进行回，可得:
|ft-gs|=r_ⅰ ，该式与④相同，该值r_i≥1位于:(g^2-f^2)n上
当然a与b也可以按上述方法，进行扩展欧几里得算法得:
|fb-ga|=r，该值r≥1位于:
((f+g)^2-(f-g)^2)n上
如果换成a与t，a与s，b与t，b与s也可以求余值，这里就不给出相应公式了。
费马分解中，如果修改为:
(it)^2≡(ⅰs)^2 (mod n) ⅰ≥1，则有:
(it±js)^2≡(ⅰs±jt)^2 (mod n) ⅰ>j≥0(对j≥i未做深究，暂设定为上述条件)
上述移项展开即可证明，这里略去详细征明步骤。
上述式中，如果|f(ⅰt±js)-g(is±jt)^2|=r，则二次剩余值r^2位于(r_i≥1):
(|(ig-jf)^2-(if-jg)^2|)n上
如果对于任意两个值:ⅰt±js和ⅴt±us有:
|f(ⅰt±js)-g(vt±us)^2|=r，则该二次剩余值r^2位于(r≥1):
(|(jg-uf)^2-(ig-vf)^2|)n上
ⅰt±js和ⅴs±ut也相似，这里略去。
对于ⅰt±js+1，如果已知|vt-us|=1，即得:
it±js+|vt-us|，注意正负性。
例n=299=13*23
根据费马分解有:
18^2≡5^2 (mod 299)
31: 2t-s
44: 3t-2s
12×44-17×31=1，1的二次剩余值位于:
(1×17-2×12)^2-(2×17-3×12)^2=45
即45*299
10×31-7×44=2，2的二次剩余值位于:
(1×10-2×7)^2-(2×10-3×7)^2=15
即15*299
小结:
两个值之间的变化较为复杂，上述过程还存在着不完善，这样的复杂性和不完善性，影响了如何能设计出一个较好的算法，希望各位大神能给出意见和建议，这里表示十分感谢！
设n=2k+1，n=ab，1<a<b，根据费马分解可得:
t^2≡s^2 (mod n) ， (t，s)=1
对上式中的t和s，按扩展欧几里得算法有:
t-q_1*s=r_1
s-q_2*r_1=r_2
r1-q_3*r_2=r_3
r_(ⅰ-2)-q_i*r_(ⅰ-1)=r_i
r_(m-2)-q_m*r_(m-1)=1
如果在第i步进行回，可得:
|ft-gs|=r_ⅰ ，该式与④相同，该值r_i≥1位于:(g^2-f^2)n上
当然a与b也可以按上述方法，进行扩展欧几里得算法得:
|fb-ga|=r，该值r≥1位于:
((f+g)^2-(f-g)^2)n上
如果换成a与t，a与s，b与t，b与s也可以求余值，这里就不给出相应公式了。
费马分解中，如果修改为:
(it)^2≡(ⅰs)^2 (mod n) ⅰ≥1，则有:
(it±js)^2≡(ⅰs±jt)^2 (mod n) ⅰ>j≥0(对j≥i未做深究，暂设定为上述条件)
上述移项展开即可证明，这里略去详细征明步骤。
上述式中，如果|f(ⅰt±js)-g(is±jt)^2|=r，则二次剩余值r^2位于(r_i≥1):
(|(ig-jf)^2-(if-jg)^2|)n上
如果对于任意两个值:ⅰt±js和ⅴt±us有:
|f(ⅰt±js)-g(vt±us)^2|=r，则该二次剩余值r^2位于(r≥1):
(|(jg-uf)^2-(ig-vf)^2|)n上
ⅰt±js和ⅴs±ut也相似，这里略去。
对于ⅰt±js+1，如果已知|vt-us|=1，即得:
it±js+|vt-us|，注意正负性。
例n=299=13*23
根据费马分解有:
18^2≡5^2 (mod 299)
31: 2t-s
44: 3t-2s
12×44-17×31=1，1的二次剩余值位于:
(1×17-2×12)^2-(2×17-3×12)^2=45
即45*299
10×31-7×44=2，2的二次剩余值位于:
(1×10-2×7)^2-(2×10-3×7)^2=15
即15*299
小结:
两个值之间的变化较为复杂，上述过程还存在着不完善，这样的复杂性和不完善性，影响了如何能设计出一个较好的算法，希望各位大神能给出意见和建议，这里表示十分感谢！
vj b20 偏移