本次文中，分为两部分，第一部分介绍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，该值必为二次剩余，上式得证。】

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课