[原创]整数分解随笔(四)

本次文中未注明处n≥3，且为奇数。
一、n中因子平方剩余的分布
  1、假设n=ab，b>a>1(a、b不一定是素因子)，在[1,n)中可以得到如下包含因子b的数：
    b  2b  3b  ...  (a-1)b
   上述平方剩余序列中求最后一个平方剩余：
         ((a-1)b)^2(mod n)≡(ab-b)^2 (mod n)
                          ≡(-b)^2 (mod n)
                          ≡b^2 (mod n)
     即((a-1))^2≡b^2(mod n),\
     同样可以得到：((a-2)b)^2≡(2b)^2(mod n)
                   .
                   .
     现在来求中间一对数的平方剩余：                  
     n为奇数，n=ab，b>a>1，
     设a=2m+1，代入上式得：
     n=(2m+1)b ->
     n=2mb+b   ->
     n=mb+mb+b ->
     n-(m+1)b=mb    ①
     上式左边的平方剩余为：
     (n-(m+1)b)^2≡((m+1)b)^2 (mod n )  ②
     ∴ 根据①、②得：(mb)^2≡((m+1)b)^2 (mod n )
     
     根据上述我们可以知道，在[1,n)中对于大于(n-1)/2包含b数的平方剩余，可以反映在[1,(n-1)/2]中。
     现在来看一个例：
     299=13*23
     在[1,149]中共有 (13-1)/2=6个23的平方剩余因子
     23  46  69  92  115  138
     7*23=161^2≡138^2 (mod 299)
  2、在上面文中，我们得到了一个新的分解n的方法：
     a^2≡b(mod n)，按一定方法配成Aa^2+Ba+C≡0 (mod n)，这里设A=1(对于A>1的情况，较复杂，暂不讨论)
     上式变成 a^2+Ba+C≡0 (mod n)  B、C为整数，b=-(Ba+C)，两个根为a1、a2(为整数)，则可得到：
        (a-a1)(a-a2)≡0 (mod n)
      gcd(a-a1,n)>1 且 gcd(a-a2)>1
      得到n的两个因子，n被分解。在上面讨论中我们知道n=ts，s>t>1，所以该分解必是以较大数s的倍数为中心，来找寻较小数t。
      现在再来讨论c^2≡d^2 (mod n)，其中d^2<√n，在[√n]<c≤(n-1)/2中的分布规律及其与a^2≡b(mod n)的关系
      先看例：299=13*23
       49^2≡9 (mod 299)         ->
       (49+3)(49-3)≡0(mod 299)  ->
       52*46≡0 (mod 299)
       gcd(52,299)=13  gcd(46,299)=23
       48^2≡211(mod 299)        ->
       48^2≡-88(mod 299)        ->
       48^2≡-2*48+6(mod 299)    ->
       48^2+2*48-6≡0(mod 299)   ->
       (48+4)(48-2)≡0(mod 299)  ->
       52*46≡0 (mod 299)
       gcd(52,299)=13  gcd(46,299)=23
  
       47^2≡116(mod 299)        ->
       47^2≡-183(mod 299)       ->
       47^2≡-4*47+5(mod 299)    ->
       (47+5)(47-1)≡0 (mod 299) ->
       52*46≡0 (mod 299)
       gcd(52,299)=13  gcd(46,299)=23
       50^2≡108(mod 299)        ->
       50^2≡2*50+8(mod 299)     ->
       50^2-2*50-8≡0(mod 299)   ->
       (50+2)(50-4)≡0(mod 299)  ->
       52*46≡0 (mod 299)
       gcd(52,299)=13  gcd(46,299)=23
       51^2≡209(mod 299)        ->
       51^2≡4*51+5(mod 299)     ->
       51^2-4*51-5≡0(mod 299)   ->
       (51+1)(51-5)≡0(mod 299)  ->
       52*46≡0 (mod 299)
       gcd(52,299)=13  gcd(46,299)=23
       现在讨论为什么是这种情况？
       从c^2≡d^2(mod n)，可得(c+d)(c-d)≡0(mod n)
       与(a-a1)(a-a2)≡0(mod n)相同，都是以较大数s的倍数为中心，来找寻较小数t。
       对于(c+d)(c-d)≡0(mod n)，可以变化得：
       (c+d)(c-d)≡0(mod n)              ->
       (c+1+d-1)(c+1-(d+1))≡0 (mod n)   ->
       (c+1)^2-2(c+1)-(d^2-1)≡0 (mod n) ->
       (c+1)^2≡2(c+1)+(d^2-1) (mod n)
       (c+d)(c-d)≡0(mod n)              ->
       (c+2+d-2)(c+2-(d+2))≡0 (mod n)   ->
       (c+2)^2-4(c+2)-(d^2-4)≡0 (mod n) ->，
       (c+2)^2≡4(c+i)+(d^2-4) (mod n)
       .
       .
       (c+d)(c-d)≡0(mod n)              ->
       (c+i+d-i)(c+i-(d+i))≡0 (mod n)   ->
       (c+i)^2-2i(c+i)-(d^2-i^2)≡0 (mod n) ->
       (c+i)^2≡2i(c+i)+(d^2-i^2) (mod n)
       c-1 c-2 ... c-i也可以得到同样的结果，这里不再推算，请大家自行推算。
       在整数分解随笔(二)中，已经指出，c^2≡d^2(mod n)，都是相差较小因子t的，而c^2≡d^2(mod n)都是分布在较大因子s的周围，即
       s  2s 3s ... ms  其中t=2m+1
       如299，平方剩余中的平方数，是分布在
        23  46 69 92 115 138的周围
       对于提出新分解方法a^2≡b(mod n)，进行配方的计算 4中的对称数方法，是在一段范围内查找平方数，而不是只查找一个平方数。