整数分解随笔(8)
     本次文中，将用费马分解法对特定一类数得到分解的方法，因还存在一定的局限，也存在不足，希望大家提出意见，共同交流，本人十分感谢。
     本次文中，未说明处，n>2且为奇合数。

一、回顾
   在说明分解方法前，先回顾一下二次剩余后序序列的内容：
  对于4k-1的整数，有： ((n-1)/2)^2     ≡k (mod n)
                                     (((n-1)/2)-1)^2≡k+2 (mod n)
                                     (((n-1)/2)-2)^2≡k+6 (mod n)
                                     (((n-1)/2)-3)^2≡k+12 (mod n)
                                      .
                                      .
                                      (((n-1)/2)-i)^2≡k+i(i+1) (mod n)  i≥0
                                      .
  对于4k+1的整数，有： ((n-1)/2)^2     ≡-k (mod n)
                                     (((n-1)/2)-1)^2≡-k+2 (mod n)
                                     (((n-1)/2)-2)^2≡-k+6 (mod n)
                                     (((n-1)/2)-3)^2≡-k+12 (mod n)
                                      .
                                      .
                                      (((n-1)/2)-i)^2≡-k+i(i+1) (mod n)  i≥0
                                      .
    对后序序列中的二次剩余值 k, k+2, k+6, ..., k+i(i+1)，在特定一类数中，可以知道另一个值a也等于这些二次剩余值。
二、特定数
    1、举例
     先看以下例中的特定数：
     例1：n=1411=4*353-1=17*83，为4k-1型，其中k=353
              根据((n-1)/2)≡k(mod n)，得 705^2≡353 (mod 1411)
              对k加n可得：
              n+k=1411+353=1764=42^2
              42^2≡353 (mod 1411)    =>  42^2≡705^2 (mod 1411)
     例2：n=2599=4*650-1=23*113，为4k-1型，其中k=650
              根据((n-1)/2)≡k(mod n)，得 1299^2≡650(mod 2599)
              对k加n可得：
              n+k=2599+650=3249=57^2
              57^2≡650 (mod 2599)  =>  57^2≡1299^2 (mod 2599)
     上述两个例中，存在一个共同的特点，就是：
            1411=17*83，其中 5*17-83=2
            2599=23*113，其中 5*23-113=2
     即n的两个因子(非质因子)中，一个因子乘以5与另一个因子相差为2。
  2、特定数的说明：
     ⑴ 上面例中，如果n中一个因子的5倍与另一个因子相差为2=1*2(相邻两个整数的乘积)，可以得到如下的公式：
     下面来证明：
     设n=a*b, b>a , 其中a=4k±1(k≥1), 如果 5a-b=2或者b-5a=2, 则n为4*kn-1型，且 (2*5*k±3)^2≡kn(mod n)或 (2*5*k±2)^2≡kn(mod n)
     证明：证明其中的两种情况
        ①、 当 a=4k+1 (k≥1):  5a=5(4k+1)=20k+5
             5a-b=2  =>  b=5a-2=20k+3
             n=a*b=(4k+1)(20k+3)=80k^2+32k+3=4(20k^2+8k+1)-1  n为4*kn-1型
             其中 kn=20k^2+8k+1   
             与n相加得:
             n+kn=80k^2+32k+3+20k^2+8k+1=(10k)^2+40k+4=(10k+2)^2
             即  (10k+2)^2≡kn(mod n)  =>  (10k+2)^2≡((n-1)/2)^2(mod n)
        ②、 当 a=4k-1 (k≥1):  5a=5(4k-1)=20k-5
             5a-b=2  =>  b=5a-2=20k-7
             n=a*b=(4k-1)(20k-7)=80k^2-48k+7=4(20k^2-12k+2)-1  n为4*kn-1型
             其中 kn=20k^2-12k+2   
             与n相加得:
             n+kn=80k^2-48k+7+20k^2-12k+2=(10k)^2-60k+9=(10k-3)^2
             即  (10k-3)^2≡kn(mod n)  =>  (10k-3)^2≡((n-1)/2)^2(mod n)
            其它两种情况证明略。
       证毕。

      当然，如果n中一个因子的5倍与另一个因子相差为6=2*3(相邻两个整数的乘积)，可以得到如下的公式：
      设n=a*b, b>a , 其中a=4k±1(k≥1), 如果 5a-b=6或者b-5a=6, 则n为4*kn-1型，且 (2*5*k±3)^2≡kn+2(mod n)或 (2*5*k±2)^2≡kn+2(mod n)
      即(2*5*k±3)^2≡(((n-1)/2)-1)(mod n)或 (2*5*k±2)^2≡(((n-1)/2)-1)(mod n)
      证明略。

     但当n中一个因子的5倍与另一个因子相差为12=3*4和20=4*5时，却无法推出相应的公式，为30=5*6和42=6*7时，就能推出相应的公式，有点搞不明白。

    ⑵  如果n中一个因子的3倍与另一个因子相差为2=1*2(相邻两个整数的乘积)，可以得到如下的公式：
     设n=a*b, b>a , 其中a=4k±1(k≥1), 如果 3a-b=2或者b-3a=2, 则n为4*kn+1型，且 (2*3*k±1)^2≡-kn(mod n)或 (2*3*k±2)^2≡-kn(mod n)
     证明：证明其中的两种情况
        ①、 当 a=4k+1 (k≥1):  3a=3(4k+1)=12k+3
             3a-b=2  =>  b=3a-2=12k+1
             n=a*b=(4k+1)(12k+1)=48k^2+16k+1=4(12k^2+4k)+1  n为4*kn+1型
             其中 kn=12k^2+4k  因((n-1)/2)^2≡-kn(mod n)   
             所以-kn与n相加得:
             n+(-kn)=48k^2+16k+1-12k^2-4k=(6k)^2+12k+1=(6k+1)^2
             即  (6k+1)^2≡-kn(mod n)  =>  (6k+1)^2≡((n-1)/2)^2(mod n)
        ②、 当 a=4k-1 (k≥1):  3a=3(4k-1)=12k-3
             3a-b=2  =>  b=3a-2=12k-5
             n=a*b=(4k-1)(12k-5)=48k^2-32k+5=4(12k^2-8k+1)+1  n为4*kn+1型
             其中 kn=12k^2-8k+1  因((n-1)/2)^2≡-kn(mod n)   
             所以-kn与n相加得:
             n+(-kn)=48k^2-32k+5-12k^2+8k-1=(6k)^2-24k+4=(6k-2)^2
             即  (6k-2)^2≡-kn(mod n)  =>  (6k-2)^2≡((n-1)/2)^2(mod n)
            其它两种情况证明略。
       证毕。
      
       同样的，与乘5倍相同， 设n=a*b, b>a , 其中a=4k±1(k≥1), 如果 3a-b=6或者b-3a=6, 则n为4*kn+1型，且 (2*3*k±1)^2≡-kn+2(mod n)或 (2*3*k±2)^2≡-kn+2(mod n) ，即(2*3*k±1)^2≡(((n-1)/2)-1)(mod n)或 (2*3*k±2)^2≡(((n-1)/2)-1)(mod n)
     
     ⑶ 如果n中一个因子的9倍与另一个因子相差为2=1*2(相邻两个整数的乘积)，可以得到如下的公式：
     设n=a*b, b>a , 其中a=4k±1(k≥1), 如果 9a-b=2或者b-9a=2, 则n为4*kn-1型，且 (2*9*k±4)^2≡kn(mod n)或 (2*9*k±5)^2≡kn(mod n)
     证明：证明其中的两种情况
        ①、 当 a=4k+1 (k≥1):  9a=9(4k+1)=36k+9
             9a-b=2  =>  b=9a-2=36k+7
             n=a*b=(4k+1)(36k+7)=144k^2+64k+7=4(36k^2+16k+2)-1  n为4*kn-1型
             其中 kn=36k^2+16k+2    
             所以kn与2n相加得:
             2n+kn=288k^2+128k+14+36k^2+16k+2=(18k)^2+144k+16=(18k+4)^2
             即  (18k+4)^2≡-kn(mod n)  =>  (18k+4)^2≡((n-1)/2)^2(mod n)
        ②、 当 a=4k-1 (k≥1):  9a=9(4k-1)=36k-9
             9a-b=2  =>  b=9a-2=36k-11
             n=a*b=(4k-1)(36k-11)=144k^2-80k+11=4(36k^2-20k+3)-1  n为4*kn-1型
             其中 kn=36k^2-20k+3     
             所以kn与2n相加得:
             2n+kn=288k^2-80k+22+36k^2-20k+3=(18k)^2-100k+25=(18k-5)^2
             即  (18k-5)^2≡kn(mod n)  =>  (18k-5)^2≡((n-1)/2)^2(mod n)
            其它两种情况证明略。
       证毕。
     ⑷ 如果n中两个因子的倍数为3、7、11...相差2、6时，为4k+1型，n中两个因子的倍数为5、9、13...相差2、6时，为4k-1型，可以按上述方法推算各自的公式。
         进一步也可以扩展，如n=299=13*23,  13*5-23=42=6*7, 也能推出相应的公式。        
         对于一般的情况n=a*b ,  b>a ,  如果ia-jb=m(m+1), (i≥1 j≥1 m≥1) ，也应该得到相应的公式，也许可以分解的数会更多。
         以上为二次剩余的后序序列的推算，而对二次剩余的前序序列 1^2 , 2^2 , 3^2 ......，也可以按费马分解法得到：
         设n=a*b, b>a , 其中a=4k+1(k≥1), 如果 2a-b=3, 可得b=2a-3 = 8k-1
            按费马分解方法得：  t=(a+b)/2=(4k+1+8k-1)/2=6k   s=(b-a)/2=(8k-1-4k-1)/2=2k-1
            即    (6k)^2 ≡ (2k-1)^2 (mod n)
         如: n=299=13*23   2*13-23=3     ∴ (6*3)^2  ≡ (2*3-1)^2 (mod 299)  =>  18^2≡5^2(mod 299)

三、小结
     因内容过多，所以省去了一部分证明，也省去了一些举例，不过个人觉得应该存在一定的公式，可以分解有限整数，因本人能力有限，无法再进一步的扩展。如果有兴趣，可以相互交流，看看能否得到一个更好的解决方法。

[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界