整数分解随笔(合数中二次剩余的正负性)

scsongls

          合数中二次剩余值的正负性

  二次剩余中，一般不存在正负性，因为正负性可以如下进行计算:：
   (-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 ,ⅴ≥0，①式中的二次剩余值会变为:ua-s- ⅴs，即左边加a，右边也加a，左边加t，右边-s，如下式:
  (t+ua+ ⅴt)^2≡(ua-s- ⅴs)^2 (mod  n)    ①-1
    上式中，右边移位到左边得:
  ((1+ⅴ)lt-s)+2ua)((1+ⅴ)(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)   ①-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的位置的第一数或者一个较小的偏差值,得到①或③的解，该整数被分解。

   

scsongls

二、公式④⑤趋于较小值的一个计算方法
    重新设定一下条件
    设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/ⅴ，与④式的对应计算为:
    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 +０+ 1)(1 +０+2)- ０*(０ + 1))n=6n, 即(sqrt(6n)+1)^2≡  ｓｑrｔ(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中，可以让二次剩余值或连续整数值在一定范围来回摆动，让部份值趋于较小值，有点像正弦的波形，不过不清楚合数中二次剩余值正负性的性质、特性，很多问题得不到有效的解决。如果能清楚这些性质、特性，可能会对整数分解有一定的帮助，上述正负性的描述，不是很成熟，还存在不少的问题，欢迎大家批评指正。

scsongls

经反复几次编辑，上传了全部内容，