首页
论坛
课程
招聘
[原创]整数分解随笔(8)
2020-2-5 12:00 8261

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

2020-2-5 12:00
8261
      整数分解随笔(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)

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

[看雪官方培训] Unicorn Trace还原Ollvm算法!《安卓高级研修班》2021年6月班开始招生!!

收藏
点赞1
打赏
分享
最新回复 (3)
雪    币: 2497
能力值: ( LV1,RANK:0 )
在线值:
发帖
回帖
粉丝
mb_xghoecki 活跃值 2020-2-5 17:56
2
3
感谢分享
雪    币: 190
活跃值: 活跃值 (13)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
AStephen 活跃值 2020-2-6 22:44
3
0
感谢分享,请问能通过公钥算出RSA的1024以内的私钥吗?
雪    币: 10537
活跃值: 活跃值 (261)
能力值: (RANK:190 )
在线值:
发帖
回帖
粉丝
看场雪 活跃值 3 2020-12-23 11:53
4
0
感谢LZ分享
游客
登录 | 注册 方可回帖
返回