首页
论坛
课程
招聘
[原创]整数分解随笔(九)
2021-1-2 11:28 3452

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

2021-1-2 11:28
3452

   本次文中,分为两部分,第一部分介绍a^2≡b(mod n)中b-a差值所得到二次剩余值的计算,第二部分是对a≡1/2的拓展,对于a≡1/2,在之前的介绍中得到是与二次剩余值k或者n-k的差值为连续整数,如果当a≡s/j(mod n)时 ( j≥2, s≥1, j>s (s,j)=1) ,推出一般式,便于得到与该二次剩余值的关系计算方法,为了能更清晰的表达,文中有不少的举例,所以本次文也比较长,如果文中有不妥之处,欢迎批评指正,也欢迎大家相互交流。

一、a^2≡b(mod n)差值的计算
    a^2≡b(mod n) => a^2≡ ∓ia+b±ia(mod n)  , i≥0 ...①
    对于该式有如下计算方法:
    a^2≡ ∓ia+b±ia(mod n) => a^2±ia≡b±ia(mod n) 两边同时乘以4并加 i^2
    4a^2±4ia+i^2≡4(b±ia)+i^2 (mod n) => (2a±i)^2≡i^2+4(b±ia) (mod n)
    而i^2+4(b±ia)正好为一元二方程的平方根
    如果 i=2j (j≥1) , ①式可以按以下方法进行变化:
    a^2±ia≡b±ia(mod n) => a^2±2ja≡b±2ja(mod n) ,两边同时加 j^2 得:
    a^2±2ja+j^2≡j^2+b±2ja(mod n) =>(a±j)^2≡ j^2+b±2ja(mod n)
    即相邻二次剩余值可以通过b值进行计算。
1、a^2≡b(mod n)相邻值计算
    a^2≡b(mod n)  => a^2≡ ia+b-ia(mod n)  , i≥0,即根据b-ia的差值可以计算出小于a值的平方剩余
   当i为偶数,即i=2j,可以计算相邻值。
        把i=2j 代入上式,得 a^2≡2ja+b-2ja (mod n)  =>
                                                 a^2-2ja≡b-2ja (mod n)  =>(两边同时加 j^2)
                                                a^2-2ja+j^2≡(b-2ja)+j^2 (mod n)  =>
                                                (a-j)^2 ≡ j^2+(b-2ja)   (mod n)
    a^2≡b(mod n)  => a^2≡ -ia+b+ia(mod n)  , i≥0  (a+j)^2≡j^2+(b+2ja)   (mod n)  ( i=2j )
    例 n=299
         32^2 ≡ 127 (mod 299)  => 32^2≡ 63+2*32 (mod 299) 得 31^2≡63+1^2=64(mod 299)
           32^2≡-1+4*32(mod 299)  得  30^2≡ -1+2^2=3(mod 299)
           32^2≡191-2*32(mod 299)  =>  33^2≡ 192( mod 299)
2、a^2≡b(mod n)对称值计算
   上式中i为偶数,如果i为奇数,即i=2j+1(j≥0),可以计算对称值(只计算n=4k-1,n=4k+1也可以同样得到)
      根据a^2≡b(mod n)对称值(b-a)的计算得,(2k-(a-(2j+1-1)/2))^2≡k+j(j+1)+b-(2j+1)a (mod n)
      例 n=299
      32^2≡127 (mod 299) =>32^2≡1*32+127-1*32(mod 299)  对称值为
                  (150-32)^2≡75+127-32 => 118^2≡170(mod 299)
      32^2≡127 (mod 299) =>32^2≡3*32+127-3*32(mod 299)  对称值为
                  (150-(32-(3-1)/2))^2≡75+1*2+127-3*32=>119^2≡108(mod 299)
      32^2≡127 (mod 299) =>32^2≡5*32+127-5*32(mod 299)  对称值为
                  (150-(32-(5-1)/2))^2≡75+2*3+127-5*32=>120^2≡48(mod 299)
      ......
      根据a^2≡b(mod n)对称值(b+a)的计算得,(2k-(a+(2j+1+1)/2))^2≡k+j(j+1)+b+(2j+1)a (mod n)
      例 n=299
      32^2≡127 (mod 299) =>32^2≡-1*32+127+1*32(mod 299)  对称值为
                  (150-(32+1))^2≡75+127+32 => 117^2≡234(mod 299)
      32^2≡127 (mod 299) =>32^2≡-3*32+127-3*32(mod 299)  对称值为
                  (150-(32+(3+1)/2))^2≡75+1*2+127+3*32=>116^2≡1(mod 299)
      32^2≡127 (mod 299) =>32^2≡-5*32+127-5*32(mod 299)  对称值为
                  (150-(32+(5+1)/2))^2≡75+2*3+127+5*32=>115^2≡69(mod 299)
      ......

3、a^2≡b(mod n)乘以2的计算
     a^2≡ ia+b-ia(mod n) (i≥0) => a^2-ia-(b-ia)≡0 (mod n)
     该式为一元二次方程,根据通解中的根号得到: i^2+4(b-ia)=i^2-4ia+4b≡4a^2-4ia+i^2=(2a-i)^2
     即:  i^2+4(b-ia)≡(2a-i)^2 (mod n)
     例 n=299
     32^2 ≡ 127 (mod 299) => 32^2≡1*32+95 (mod 299) => (2*32-1)^2≡1^2+4*95(mod 299) => 63^2≡82(mod 299)
     32^2 ≡ 127 (mod 299) => 32^2≡2*32+63 (mod 299) => (2*32-2)^2≡2^2+4*63(mod 299) => 62^2≡256(mod 299)
     32^2 ≡ 127 (mod 299) => 32^2≡3*32+31 (mod 299) => (2*32-3)^2≡3^2+4*31(mod 299) => 61^2≡133(mod 299)
     ...
     同样 a^2≡ -ia+b+ia(mod n) (i≥0) => a^2+ia-(b+ia)≡0 (mod n) 得到:
     (2a+i)^2≡i^2+4(b+ia) (mod n)
     32^2 ≡ 127 (mod 299) => 32^2≡-1*32+159 (mod 299) => (2*32+1)^2≡1^2+4*159(mod 299) => 65^2≡39(mod 299)
     32^2 ≡ 127 (mod 299) => 32^2≡-2*32+191 (mod 299) => (2*32+2)^2≡2^2+4*191(mod 299) => 66^2≡170(mod 299)
     32^2 ≡ 127 (mod 299) => 32^2≡-3*32+223 (mod 299) => (2*32+3)^2≡3^2+4*223(mod 299) => 67^2≡4(mod 299)
     ...

4、设c^2≡d(mod n),该平方剩余值是否在a^2≡b(mod n)范围的判断
     1}、a<k的判断,按完全平方判断
         c>a: 上式两式相减的,c^2-a^2≡d-b(mod n)  => c^2≡a^2+d-b(mod n)
             例 n=299  
                32^2 ≡ 127 (mod 299)  判断 259是否在32的右边,即大于32,根据上式得
                   32^2+259-127=1024+132=1156=34^2  
         c<a: 上式两式相减的,a^2-c^2≡b-d(mod n)  => c^2≡a^2-(b-d)(mod n)
             例 n=299  
                32^2 ≡ 127 (mod 299)  判断 3是否在32的左边,即小于32,根据上式得
                   32^2-(127-3)=1024-124=900=30^2
     2}、a>k的判断,按连续整数积判断
         c<a:  a(a-1)+d-b≡j(j+1)(mod n)
             例  n=299
                133^2≡48(mod 299) 判断118是否位于133的左边: 150-133=17
                  17(17-1)+118-48=272+70=342=18*19  所以 (150-19)^2≡118(mod 299) => 131^2≡118(mod 299)
           c>a:  a(a-1)-(b-d)≡j(j+1)(mod n)
             例  n=299
                133^2≡48(mod 299) 判断285是否位于133的右边: 150-133=17 因285>48 所以 285≡-14(mod 299)
                  17(17-1)-(48+14)=272-62=210=14*15  所以 (150-15)^2≡285(mod 299) => 135^2≡285(mod 299)
    3)、a=k的判断
        当a=k时,存在值得多次跳跃(即加一次n,则为跳跃一次),对这种情况有如下公式的的计算
        c<k:k^2≡k/4(mod n) (n=4k-1型,对于n=4k+1型,这里不给出)  (k-2i)^2≡k/4+(2i)^2-i (mod n) (i>0)
              (k-(2i-1))^2≡k/4+2k+(2i-1)^2-i (mod n) (i>0)
              例 n=299=4*75-1
                  75^2≡243(mod 299)    (75-4)^2≡243+4^2-4/2 => 71^2≡257(mod 299)
                                                        (75-5)^2≡243+150+5^2-3 => 70^2≡116(mod 299)
        c>k:k^2≡k/4(mod n) (n=4k-1型)  (k+2i)^2≡k/4+(2i)^2+i (mod n)
              (k+(2i-1))^2≡k/4+2k+(2i-1)^2+i-1 (mod n) (i>0)
              例 n=299=4*75-1
                  75^2≡243(mod 299)    (75+4)^2≡243+4^2+4/2 => 79^2≡261(mod 299)
                                                        (75+5)^2≡243+150+5^2+3-1 => 80^2≡121(mod 299)



二、乘法逆元的计算方法
      在前面文中,有对a≡1/2(mod n)计算方法,平方剩余值c^2≡d(mod n),与k或者n-k的差,即d-k或者d-(n-k)为连续整数积时,在后序序列中,找到费马分解的另一个值,整数被分解,当a≡i/j (mod n) (j>2,i≥1),即c^2≡d(mod n)时,c^2≡d(mod n),如何计算d与b的差值。
      设a^2≡b (mod n),按以下两种方式计算二次剩余:
        ⑴  a的乘法逆为偶数时,即 a≡m/(2j)(mod n) ( j≥1 , m为整数,共j个值,取值见后续说明) ,按a±ij计算二次剩余,其中i≥1,得:
             (a±i*j)^2≡d(mod n)                    =>
             a^2±2a*i*j+(i*j)^2≡d(mod n)    =>
             d-b≡(i*j)^2±a*(2j)*i(mod n)
             ∵ a*(2j)≡m(mod n)  ∴上式可得:
              d-b≡(i*j)^2±m*i (mod n)       ②
        ⑵ a的乘法逆为奇数时,即 a≡m/(2j+1)(mod n) ( j≥1 , m为整数,共2j+1个值,取值见后续说明) ,按a±i(2j+1)计算二次剩余,其中i≥1,得:
             (a±i*(2j+1))^2≡d  (mod n)                             =>
             a^2±2a*i*(2j+1)+(i*(2j+1))^2≡d (mod n)      =>
             d-b≡(i*(2j+1))^2±2*a*(2j+1)*i (mod n)
             ∵ a*(2j+1)≡m (mod n)  ∴上式可得:
              d-b≡(i*(2j+1))^2±2*m*i (mod n)    ③

    1、先看公式②,即逆元为偶数情况 a≡m/2j (mod n)及m值得变化
         m值与j相关,共有j个值:
            当j为偶数时,1/2j -j/2, 1/2j -j/2+1 , ... 1/2j -2, 1/2j -1, 1/2j, 1+1/2j,  2+1/2j, ... j/2-1+1/2j
            当j为奇数时,1/2j -(j-1)/2, 1/2j -(j-1)/2+1, ... 1/2j -2, 1/2j -1, 1/2j, 1+1/2j, 2+1/2j, ... (j-1)/2-1+1/2j, (j-1)/2+1/2j
            后续举例进行m的说明。
      ⑴  j=1,此时m只有一个值 m=1,a≡1/2 (mod n) ,
           根据 ② 计算公式,在i=1,2,3,4.....,值为:
            i=1:   d-b≡1^2±1=1(1±0) (mod n)                     
            i=2:   d-b≡2^2±2=2(2±1) (mod n)
            i=3:   d-b≡3^23=3(3±1) (mod n)
            .
            .
            .
            即为连续的两个整数积,为逆序值,逆序序列为 ① 的一个特殊情况
      ⑵  j=2,此时m有两个值 m=1及m=-3,可以计算出a≡1/4周边的二次剩余值:
           先看m=1, a≡1/4 (mod n)
           根据 ② 计算公式,在i=1,2,3,4.....,值为:
            i=1:   d-b≡2^2±1 (mod n)                     
            i=2:   d-b≡4^2±2 (mod n)
            i=3:   d-b≡6^2±3 (mod n)
            .
            .
            .
            m=-3 ,a≡-3/4 (mod n) ,即a左边的一个值,可按这样计算 :1/4-1=-3/4
            根据 ② 计算公式,在i=1,2,3,4.....,值为:
            i=1:   d-b≡2^2±(-m)*1=2^2±(-3)*1 (mod n)                     
            i=2:   d-b≡4^2±(-m)*2=4^2±(-3)*2 (mod n)
            i=3:   d-b≡6^2±(-m)*3=6^2±(-3)*3 (mod n)
            .
            .
            .
          例:n=299  
              a≡1/4 (mod 299) ≡75 (mod 299)  75^2≡243 (mod 299)
             (75-2*1)^2=73^2≡246 (mod 299)      (75+2*1)^2=77^2≡248 (mod 299)
             i=1: 246-243=3=2^2-1                     248-243=5=2^2+1
             (75-2*2)^2=71^2≡257 (mod 299)      (75+2*2)^2=79^2≡261 (mod 299)
             i=2: 257-243=14=4^2-2                     261-243=18=4^2+2
             (75-2*3)^2=69^2≡276 (mod 299)      (75+2*3)^2=81^2≡282 (mod 299)
             i=3: 276-243=33=6^2-3                     282-243=39=6^2+3
             .
             .
             对a≡1/4 (mod 299)只计算了一半的二次剩余值,现在再来计算另一半的二次剩余值,即为 a≡1/4-1=-3/4 (mod 299):
             (1/4-1)^2=(-3/4)^2 或者(75-1)^2=74^2≡94 (mod 299),以94为基准计算二次剩余:
             (74-2*1)^2=72^2≡101 (mod 299)      (74+2*1)^2=76^2≡95 (mod 299)
             i=1: 101-94=7=2^2-(-3)*1                     95-94=1=2^2+(-3)*1
             (74-2*2)^2=70^2≡116 (mod 299)      (74+2*2)^2=78^2≡104 (mod 299)
             i=2: 116-94=24=4^2-(-3)*2                     104-94=10=4^2+(-3)*2
             (74-3*3)^2=68^2≡139 (mod 299)      (74+2*3)^2=80^2≡121 (mod 299)
             i=3: 139-94=45=6^2-(-3)*3                     121-94=27=6^2+(-3)*3
             .
             .
            比如,要判断256是否在1/4的周围,以(1/4)^2≡ 243 (mod 299) 和 (1-1/4)^2≡ 94 (mod 299)两个二次剩余值为基准值进行计算,可以按以下公式进行判断(把i换成x):
            (2x)^2-x=256-243  => (2x)^2-x-13=0   根据一元二次通解:B^2-4AC=1+4*4*13=209  虽然209为二次剩余值(见下面的证明),但不太好找对应的平方数。
             【 该段为B^2-4AC为二次剩余值得证明:
                设c^2≡d (mod n),根据公式 ② 得:
                      d-b≡(jx)^2±mx (mod n)  => (jx)^2±mx-(d-b)≡ 0 (mod n)
                     一元二次通解得: m^2-4*j^2*(-(d-b))=m^2+(2j)^2*(d-b)≡m^2+(2j*c)^2-(2j*a)^2
                    因为  a≡m/(2j)(mod n),所以上式为  m^2+(2j*c)^2-m^2=(2j*c)^2,该值必为二次剩余,上式得证。】


            (2x)^2-(-3)x=256-94  => (2x)^2+3x-162=0   根据一元二次通解:B^2-4AC=3^2+4*4*162=2601=51^2
                       (-3±51)/(2*2)  => (-3+51)/4=12为整数,所以 (74-12)^2=62^2≡256 (mod 299)
             说明:上面(-3±51)/(2*2)中,2*2按通解公式应为2*4,因解出整数值后要乘以j或者2j+1,即(2/4)*2=1/2,所以通解得到整数后不必在乘相同得值,下述在计算时也是用了相同得方法,这个不是手误;还有51^2≡209 (mod 299)相等的原因,在本次文中不作论述,下次文中再说明。

      ⑶  j=3,此时m有三个值 :m=1、m=-5及m=7,可以覆盖计算出a≡1/6周边的二次剩余值:
           先看m=1, a≡1/6 (mod n)
           根据 ② 计算公式,在i=1,2,3,4.....,值为:
            i=1:   d-b≡3^2±1 (mod n)                     
            i=2:   d-b≡6^2±2 (mod n)
            i=3:   d-b≡9^2±3 (mod n)
            .
            .
            .
            m=-5 ,a≡-5/6 (mod n) ,即a左边的一个值,可按这样计算 :1/6-1=-5/6
            根据 ② 计算公式,在i=1,2,3,4.....,值为:
            i=1:   d-b≡3^2±(-m)*1=3^2±(-5)*1 (mod n)                     
            i=2:   d-b≡6^2±(-m)*2=6^2±(-5)*2 (mod n)
            i=3:   d-b≡9^2±(-m)*3=9^2±(-5)*3 (mod n)
            .
            .
            .
            m=7 ,a≡7/6 (mod n) ,即a右边的一个值,可按这样计算 :1/6+1=7/6
            根据 ② 计算公式,在i=1,2,3,4.....,值为:
            i=1:   d-b≡3^2±m*1=3^2±7*1 (mod n)                     
            i=2:   d-b≡6^2±m*2=6^2±7*2 (mod n)
            i=3:   d-b≡9^2±m*3=9^2±7*3 (mod n)
            .
            .
            .
          例:n=299  
              a≡1/6 (mod 299) ≡50 (mod 299)  50^2≡108 (mod 299)
             (50-3*1)^2=47^2≡116 (mod 299)      (50+3*1)^2=53^2≡118 (mod 299)
             i=1: 116-108=8=3^2-1                     118-108=10=3^2+1
             (50-3*2)^2=44^2≡142 (mod 299)      (50+3*2)^2=56^2≡146 (mod 299)
             i=2: 142-108=34=6^2-2                     146-108=38=6^2+2
             (50-3*3)^2=41^2≡186 (mod 299)      (50+3*3)^2=59^2≡192 (mod 299)
             i=3: 186-108=78=9^2-3                     192-108=84=9^2+3
             .
             .
             为覆盖a≡1/6 (mod 299)所有的二次剩余值,现在再来计算其它两个的二次剩余值,即为 a≡1/6-1=-5/6 (mod 299):
             (1/6-1)^2=(-5/6)^2 或者(50-1)^2=49^2≡9 (mod 299),以9为基准计算二次剩余:
             (49-3*1)^2=46^2≡23 (mod 299)      (49+3*1)^2=52^2≡13 (mod 299)
             i=1: 23-9=14=3^2-(-5)*1                     13-9=4=3^2+(-5)*1
             (49-3*2)^2=43^2≡55 (mod 299)      (49+3*2)^2=55^2≡35 (mod 299)
             i=2: 55-9=46=6^2-(-5)*2                     35-9=26=6^2+(-5)*2
             (49-3*3)^2=40^2≡105 (mod 299)      (49+3*3)^2=58^2≡75 (mod 299)
             i=3: 105-9=96=9^2-(-5)*3                     75-9=66=9^2+(-5)*3
             .
             .
             (1/6+1)^2=(7/6)^2 或者(50+1)^2=51^2≡209 (mod 299),以209为基准计算二次剩余:
             (51-3*1)^2=48^2≡211 (mod 299)      (51+3*1)^2=54^2≡225 (mod 299)
             i=1: 211-209=2=3^2-7*1                     225-209=16=3^2+7*1
             (51-3*2)^2=45^2≡231 (mod 299)      (51+3*2)^2=57^2≡259 (mod 299)
             i=2: 231-209=22=6^2-7*2                     259-209=50=6^2+7*2
             (51-3*3)^2=42^2≡269 (mod 299)      (51+3*3)^2=60^2≡12 (mod 299)
             i=3: 269-209=60=9^2-7*3                     12+299-209=112=9^2+7*3
             .
             .
            比如,1/6相关范围内是否存在完全平方,基准值(1-1/6)^2≡9 (mod 299)、(1/6)^2≡108 (mod 299)、(1+1/6)^2≡209 (mod 299)进行计算,因9为完全平方,淘汰该基准值:
            大于108的完全平方值为121:
            (3x)^2-x=121-108  => (3x)^2-x-13=0   根据一元二次通解:B^2-4AC=1+4*9*13≡170   170为二次剩余值,但不太好找对应的平方数。
            (3x)^2-x=144-108  => (3x)^2-x-36=0   根据一元二次通解:B^2-4AC=1+4*9*36≡101   20^2≡101 (mod 299)
                       (-1±20)/(2*3)  无整数解,加n  => (-1±20+299)/(2*3)=53  所以 (50+53)^2=103^2≡144 (mod 299)
            大于209的完全平方值为225:
            (3x)^2-7x=225-209  => (3x)^2-7x-16=0   根据一元二次通解:B^2-4AC=7^2+4*9*16=625=25^2  
                       (-7±25)/(2*3)  => (-7+25)/6=3 为整数,所以 (50+3)^2=53^2≡225 (mod 299)

    2、公式③,即逆元为奇数情况 a≡m/(2j+1) (mod n)及m值得变化
         m值与j相关,共有2j+1个值:
            1/(2j+1) -j, 1/(2j+1) -j-1, ...1/(2j+1) -2, 1/(2j+1) -1 , 1/(2j+1), 1/(2j+1) +1, 1/(2j+1) +2, ... 1/(2j+1) +j-1, 1/(2j+1) +j
            后续举例进行m的说明。
      ⑴  j=1,此时m有3个值 m=1、m=-2、m=4,可以计算出a≡1/3周边的二次剩余值:
            m=1,a≡1/3 (mod n)
           根据 ③ 计算公式,在i=1,2,3,4.....,值为:
            i=1:   d-b≡(1*3)^2±2*m*1=3^2± 2 (mod n)                     
            i=2:   d-b≡(2*3)^2±2*m*2=6^2± 4 (mod n)
            i=3:   d-b≡(3*3)^2±2*m*3=9^2± 6 (mod n)
            .
            .
            m=-2 ,a≡-2/3 (mod n) ,即a左边的一个值,可按这样计算 :1/3-1=-2/3
            根据 ② 计算公式,在i=1,2,3,4.....,值为:
            i=1:   d-b≡(1*3)^2±2*m*1=3^2± (-4) (mod n)                     
            i=2:   d-b≡(2*3)^2±2*m*2=6^2± (-8) (mod n)
            i=3:   d-b≡(3*3)^2±2*m*3=9^2± (-12) (mod n)
            .
            .
             m=4 ,a≡4/3 (mod n) ,即a左边的一个值,可按这样计算 :1/3+1=4/3
            根据 ③ 计算公式,在i=1,2,3,4.....,值为:
            i=1:   d-b≡(1*3)^2±2*m*1=3^2± 8 (mod n)                     
            i=2:   d-b≡(2*3)^2±2*m*2=6^2± 16 (mod n)
            i=3:   d-b≡(3*3)^2±2*m*3=9^2± 24 (mod n)
            .
            .

          例:n=299  
              a≡1/3 (mod 299) ≡100 (mod 299)  100^2≡133 (mod 299)
             (100-3*1)^2=97^2≡140 (mod 299)      (100+3*1)^2=103^2≡144 (mod 299)
             i=1: 140-133=7=3^2-2                     144-133=11=3^2+2
             (100-3*2)^2=94^2≡165 (mod 299)      (100+3*2)^2=106^2≡173 (mod 299)
             i=2: 165-133=32=6^2-4                     173-133=40=6^2+4
             (100-3*3)^2=91^2≡208 (mod 299)      (100+3*3)^2=109^2≡220 (mod 299)
             i=3: 208-133=75=9^2-6                     220-133=87=9^2+6
             .
             .
             m=-2,  a≡(1/3-1)=-2/3 (mod 299) ≡99 (mod 299)  (100-1)^2=99^2≡233 (mod 299)
             (99-3*1)^2=96^2≡246 (mod 299)      (99+3*1)^2=102^2≡238 (mod 299)
             i=1: 246-233=13=3^2-2*(-2)*1         238-233=5=3^2+2*(-2)*1
             (99-3*2)^2=93^2≡277 (mod 299)      (99+3*2)^2=105^2≡261 (mod 299)
             i=2: 277-233=44=6^2-2*(-2)*2         261-233=28=6^2+2*(-2)*2
             (99-3*3)^2=90^2≡27 (mod 299)        (99+3*3)^2=108^2≡3 (mod 299)
             i=3:27+299-233=93=9^2-2*(-2)*3    3+299-233=69=9^2+2*(-2)*3
             .
             .
             m=4,  a≡(1/3+1)=4/3 (mod 299) ≡101 (mod 299)  (100+1)^2=101^2≡35 (mod 299)
             (101-3*1)^2=98^2≡36 (mod 299)      (101+3*1)^2=104^2≡52 (mod 299)
             i=1: 36-35=1=3^2-2*4*1                   238-233=5=3^2+2*4*1
             (101-3*2)^2=95^2≡55 (mod 299)      (101+3*2)^2=107^2≡87 (mod 299)
             i=2: 55-35=20=6^2-2*4*2                 87-35=52=6^2+2*4*2
             (101-3*3)^2=92^2≡92 (mod 299)        (101+3*3)^2=110^2≡140 (mod 299)
             i=3:92-35=57=9^2-2*4*3                   140-35=105=9^2+2*4*3
             .
             .
 
      ⑵  j=2,此时m有2*2+1=5个值 m=1、m=-4、m=-9、m=6、m=11,可以计算出a≡1/5周边的二次剩余值:
           先看m=1, a≡1/5 (mod n)
           根据 ③ 计算公式,在i=1,2,3,4.....,值为:
            i=1:   d-b≡(5*i)^2±2*m*i=5^2±2 (mod n)                     
            i=2:   d-b≡(5*i)^2±2*m*i=10^2±4 (mod n)
            i=3:   d-b≡(5*i)^2±2*m*i=15^2±6 (mod n)
            .
            .
            .
            m=-4 ,a≡-4/5 (mod n) ,即a左边的一个值,可按这样计算 :1/5-1=-4/5
            根据 ③ 计算公式,在i=1,2,3,4.....,值为:
            i=1:   d-b≡(5*i)^2±2*m*i=5^2±(-8) (mod n)                     
            i=2:   d-b≡(5*i)^2±2*m*i=10^2±(-16) (mod n)
            i=3:   d-b≡(5*i)^2±2*m*i=15^2±(-24) (mod n)
            .
            .
            m=-9 ,a≡-9/5 (mod n) ,即a左边的第二个值,可按这样计算 :1/5-2=-9/5
            根据 ③ 计算公式,在i=1,2,3,4.....,值为:
            i=1:   d-b≡(5*i)^2±2*m*i=5^2±(-18) (mod n)                     
            i=2:   d-b≡(5*i)^2±2*m*i=10^2±(-36) (mod n)
            i=3:   d-b≡(5*i)^2±2*m*i=15^2±(-54) (mod n)
            .
            .
            m=6 ,a≡6/5 (mod n) ,即a右边的第一个值,可按这样计算 :1/5+1=6/5
            根据 ③ 计算公式,在i=1,2,3,4.....,值为:
            i=1:   d-b≡(5*i)^2±2*m*i=5^2±12 (mod n)                     
            i=2:   d-b≡(5*i)^2±2*m*i=10^2±24 (mod n)
            i=3:   d-b≡(5*i)^2±2*m*i=15^2±36 (mod n)
            .
            .
            m=11 ,a≡-11/5 (mod n) ,即a右边的第二个值,可按这样计算 :1/5+2=11/5
            根据 ③ 计算公式,在i=1,2,3,4.....,值为:
            i=1:   d-b≡(5*i)^2±2*m*i=5^2±22 (mod n)                     
            i=2:   d-b≡(5*i)^2±2*m*i=10^2±44 (mod n)
            i=3:   d-b≡(5*i)^2±2*m*i=15^2±66 (mod n)
            .
            .

          例:n=299  
              m=1,a≡1/5 (mod 299) ≡60 (mod 299)  60^2≡12 (mod 299)
             (60-5*1)^2=55^2≡35 (mod 299)       (60+5*1)^2=65^2≡39 (mod 299)
             i=1: 35-12=23=5^2-2                       39-12=27=5^2+2
             (60-5*2)^2=50^2≡108 (mod 299)      (60+5*2)^2=70^2≡116 (mod 299)
             i=2: 108-12=96=10^2-4                    116-12=104=10^2+4
             (60-5*3)^2=45^2≡231 (mod 299)      (60+5*3)^2=75^2≡243 (mod 299)
             i=3: 231-12=219=15^2-6                   243-12=231=15^2+6
             .
             .
              m=-4,a≡(1/5-1)=-4/5 (mod 299) ≡59 (mod 299)   (60-1)^2=59^2≡192 (mod 299)
             (59-5*1)^2=54^2≡225 (mod 299)       (59+5*1)^2=64^2≡209 (mod 299)
             i=1: 225-192=33=5^2-2*(-4)*1          39-12=27=5^2+2
             (59-5*2)^2=49^2≡ 9(mod 299)           (59+5*2)^2=69^2≡276 (mod 299)
             i=2: 9+299-192=116=10^2-2*(-4)*2   276-192=84=10^2+2*(-4)*2
             (59-5*3)^2=44^2≡142 (mod 299)      (59+5*3)^2=74^2≡94 (mod 299)
             i=3:142+299-192=249=15^2-2*(-4)*3   94+299-192=201=15^2+2*(-4)*3
             .
             .
              m=-9,a≡(1/5-2)=-9/5 (mod 299) ≡58 (mod 299)   (60-2)^2=58^2≡75 (mod 299)
             (58-5*1)^2=53^2≡118 (mod 299)       (58+5*1)^2=63^2≡82 (mod 299)
             i=1: 118-75=43=5^2-2*(-9)*1            82-75=7=5^2+2*(-9)*1
             (58-5*2)^2=48^2≡211 (mod 299)      (58+5*2)^2=68^2≡139 (mod 299)
             i=2: 211-75=136=10^2-2*(-9)*2         139-75=64=10^2+2*(-9)*2
             (58-5*3)^2=43^2≡55 (mod 299)        (58+5*3)^2=73^2≡246 (mod 299)
             i=3:55+299-75=279=15^2-2*(-9)*3   246-75=171=15^2+2*(-9)*3
             .
             .
             .
             m=6、m=11,即a≡(1/5+1)=6/5和a≡(1/5+2)=11/5 略去,不再列举。

      ⑶  j=2,a≡2/5(mod n),m有2*2+1=5个值 m=1*2=2、m=-4*2=-8、m=-9*2=-18、m=6*2=12、m=11*2=22,可以计算出a≡2/5mod n)周边的二次剩余值,具体例子不再列举,可以参考前面的数据。
          对于t/(2j)  t≥1 , 当t>j且(t , 2j)=1时,|t/(2j) - 1|必在[1,j)找到相应的值,所以不必考虑t>j的值,1≤t<j。
         同样 t/(2j+1) t≥1 ,当t>j且(t , 2j+1)=1时,|t/(2j+1) - 1|必在[1,j]找到相应的值,所以也不必考虑t>j的值,1≤t≤j
         所以上式中,要考虑乘以t值
         如 a≡1/7,共有3个周边值需要计算: 1/7  2/7 3/7
             a≡1/10,共有2个周边值需要计算: 1/10  3/10 (其它分子与分母非互素,这类数不必考虑,但从②③公式中,似乎4/10与2/5有点不相同)

三、小结
      如果能从a^2≡b (mod n)、c^2≡d (mod n)及其相关联的一组或者多组数中,构造出Ax^2+Bx+C≡0 (mod n)这样的一元二次或者二元二次的方程,并能得到相应的整数解,那整数将被分解,但目前还暂时找不到相应的方法。
     或者可以考虑在s/2 s/3 s/4 ... s/j  ( j≥2, s≥1, j>s  (j,s)=1)各自范围内,是否存在与其它范围内的二次剩余相同的值,即s/3与s/5是否存在二次剩余相同的值,最好能找到相应的方法或者算法,将加快整数的分解,但不能彻底分解整数。


[公告]5月14日腾讯安全零信任发展趋势论坛重磅开幕!邀您一起从“零”开始,共建信任!!

收藏
点赞1
打赏
分享
最新回复 (3)
雪    币: 6727
活跃值: 活跃值 (4973)
能力值: ( LV12,RANK:210 )
在线值:
发帖
回帖
粉丝
pureGavin 活跃值 2 2021-1-2 12:29
2
0
年更系列,感谢分享
雪    币: 2184
活跃值: 活跃值 (431)
能力值: ( LV5,RANK:60 )
在线值:
发帖
回帖
粉丝
小菜鸟一 活跃值 2021-1-4 07:10
3
0
在未完成分解之前,一切都是异想天开
雪    币: 409
活跃值: 活跃值 (301)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
mb_foyotena 活跃值 2021-1-4 08:28
4
0
小菜鸟一 在未完成分解之前,一切都是异想天开
回到二十年前,现在的很多东西都是异想天开
游客
登录 | 注册 方可回帖
返回