三、平方剩余的一些性质
  以下文中n为奇数。
   ① n=4k-1
    当n=4k-1时，a^2≡b (mod n)，先看一个例91，91的平方剩余如下(91=4×23-1，9<a≤45)：
91
10^2≡9 , 11^2≡30 , 12^2≡53 , 13^2≡78
14^2≡14 , 15^2≡43 , 16^2≡74 , 17^2≡16
18^2≡51 , 19^2≡88 , 20^2≡36 , 21^2≡77
22^2≡29 , 23^2≡74 , 24^2≡30 , 25^2≡79
26^2≡39 , 27^2≡1 , 28^2≡56 , 29^2≡22
30^2≡81 , 31^2≡51 , 32^2≡23 , 33^2≡88
34^2≡64 , 35^2≡42 , 36^2≡22 , 37^2≡4
38^2≡79 , 39^2≡65 , 40^2≡53 , 41^2≡43
42^2≡35 , 43^2≡29 , 44^2≡25 , 45^2≡23

根据以上中间数的介绍，前序与逆序相交之处为k，这里k=23
   观察以上范围内平方剩余，特别是中间数k=23，与23相差±1的两个数22和24的平方剩余：
   22^2≡29 mod 91
   24^2≡30 mod 91
   22与24的平方剩余相差为30-29=1，这是因为上式相减得：
   30–29≡24^2–22^2( mod 91)
   1≡(23+1)^2–(23–1)^2 ( mod 91)
   1≡4*23 ( mod 91)
  正好为4×23≡1 mod 91
   再看与23相差±2的两个数21和25的平方剩余：
   21^2≡77 mod 91
   25^2≡79 mod 91
   21与25平方剩余相差为79-77=2，且21的平方剩余77与23的平方剩余74相差3，25的平方剩余79与23的平方剩余74相差5(与中间数平方剩余相差3、5的证明见后)，这是因为上式相减得：
   79–77≡25^2–21^2( mod 91)
   2≡(23+2)^2–(23–2)^2 ( mod 91)
   2≡4*23*2 ( mod 91)
   正好为(4×23)*2≡2 mod 91
   .
   .
   .
   以此类推，20与26的平方剩余相差3，19与27的平方剩余相差4……(证明见后)
   再来证明21(k-2)与23(k)的平方剩余为什么相差3？
    证明一：
    设n=4k-1，k为中间数
     k^2≡k/4=b (mod n)   ①
     (k-2)^2≡c (mod n)      ②
     ①-②：b-c≡k^2-(k-2)^2 (mod n)
            b-c≡ 4k–4 (mod n)
      ∵ 4k≡1 (mod n)
      ∴ b-c≡ 1–4 (mod n)
           b-c≡–3 (mod n)
           c–b≡3 (mod n)  证毕

     证明二：
     同理可以证明k与k+2相差5。
     设n=4k-1，k为中间数
     k^2≡k/4=b (mod n)     ③
     (k+2)^2≡d (mod n)      ④
     ④-③：d-b≡(k+2)^2-k^2 (mod n)
           d-b≡ 4k+4 (mod n)
      ∵ 4k≡1 (mod n)
      ∴ d-b≡ 1+4 (mod n)
           d-b≡5 (mod n) 证毕

    Ⅰ、观察23,21,19,17…的平方剩余差为3,11,19…(也可以通过证明一得到该数列)，即平方剩余差是一个等差数列，公差为8。
     a(m)=a(1)+(m-1)*8  a(1)=3  m>0
     s1=3+11+19+…+3+8(m-1)
         =3m+4m(m-1)
         =m(4m-1)

    Ⅱ、观察23,25,27,29…的平方剩余差为5,13,21…(也可以通过证明二得到该数列)，即平方剩余差是一个等差数列，公差为8。
     a(m)=a(1)+(m-1)*8  a(1)=5  m>0
     s2=5+13+21+…+5+8(m-1)
         =5m+4m(m-1)
         =m(4m+1)

    Ⅲ、观察22,20,18,16…的平方剩余差为7,15,23…(也可以通过证明得到该数列)，即平方剩余差是一个等差数列，公差为8。
     a(m)=a(1)+(m-1)*8  a(1)=7  m>0
     s3=7+15+23+…+7+8(m-1)
         =7m+4m(m-1)
         =m(4(m+1)-1)

    Ⅳ、观察24,26,28,30…的平方剩余差为9,17,25…(也可以通过证明得到该数列)，即平方剩余差是一个等差数列，公差为8。
     a(m)=a(1)+(m-1)*8  a(1)=9  m>0
     s4=9+17+25+…+9+8(m-1)
         =9m+4m(m-1)
         =m(4(m+1)+1)

    根据以上，以中间数k为中心向中间数的两边共形成4个数列：
      小于k方向数列ⅠⅢ：
       m(4m-1)、m(4(m+1)-1)
       大于k方向数列 Ⅱ Ⅳ：
       m(4m+1)、m(4(m+1)+1)

     Ⅰ、Ⅲ数列往小于k方向必然与a^2各有一个交点，且两个交点是相邻的。
      Ⅱ、Ⅳ往大于K方向必然与i(i+1)+k各有一个交点，且这两个交点也是相邻的，与Ⅰ、Ⅲ数列的两个交点正好是与K为中心的对称点。
    如91，k=23，m=5
   Ⅰ数列：74+5(4*5-1)=169=13^2
    Ⅲ数列：29+5(4*6-1)=144=12^2
    12、13与23相差11、10
   
    Ⅱ数列：74+5(4*5+1)=179=12*(12+1)+23
     得45-12=33
    Ⅳ数列：29+5(4*6+1)=155=11*(11+1)+23
     得45-11=34
     34、33与23相差11、10

   现在证明Ⅰ数列往减方向与a^2的交点：
   证明：设交点处为a，因为Ⅰ数列以k、k-2、k-4…的平方剩余减小的，每个值相隔2，所以m为：
      m=(k-a)/2，k^2≡k/4=b (mod n)
    Ⅰ数列可以变为以下：
     k/4+4((k-a)/2)^2-(k-a)/2  (mod n)
   ≡k/4+k^2-2ka+a^2-(k-a)/2 (mod n)
   ≡k/4+k/4-2ka+a^2-k/2+a/2(mod n)
   ≡a^2-2ka+a/2 (mod n)
   ≡a^2-((4k-1)/2)*a (mod n)
   ≡a^2 (mod n)
   a的值为：
   k为奇数且(k+1)/2为奇数时：a=(k+1)/2，否则(k+1)/2为偶数时：a=(k+1)/2+1
   k为偶数且k/2为偶数时：a=k/2，否则k/2为奇数时：a=k/2+1

  Ⅱ、Ⅲ、Ⅳ数列也可以按此证明。

② n=4k+1
    当n=4k+1时，a^2≡b (mod n)，先看一个例93，93的平方剩余如下(93=4×23+1，9<a≤46)：

93
10^2≡7 , 11^2≡28 , 12^2≡51 , 13^2≡76
14^2≡10 , 15^2≡39 , 16^2≡70 , 17^2≡10
18^2≡45 , 19^2≡82 , 20^2≡28 , 21^2≡69
22^2≡19 , 23^2≡64 , 24^2≡18 , 25^2≡67
26^2≡25 , 27^2≡78 , 28^2≡40 , 29^2≡4
30^2≡63 , 31^2≡31 , 32^2≡1 , 33^2≡66
34^2≡40 , 35^2≡16 , 36^2≡87 , 37^2≡67
38^2≡49 , 39^2≡33 , 40^2≡19 , 41^2≡7
42^2≡90 , 43^2≡82 , 44^2≡76 , 45^2≡72
46^2≡70

根据以上中间数的介绍，前序与逆序相交之处为k，这里k=24
   观察以上范围内平方剩余，特别是中间数k=24，与24相差±1的两个数23和25的平方剩余：
   23^2≡64 mod 93
   25^2≡67 mod 93
   23与25的平方剩余相差为67-64=3，这是因为上式相减得：
   67–64≡25^2–23^2( mod 93)
   3≡(24+1)^2–(24–1)^2 ( mod 93)
   3≡4*24 ( mod 93)
  正好为4×24≡3 mod 93
   再看与24相差±2的两个数22和26的平方剩余：
   22^2≡19 mod 93
   26^2≡25 mod 93
   22与26平方剩余相差为25-19=6，且22的平方剩余19与24的平方剩余18相差1，26的平方剩余25与24的平方剩余18相差7(与中间数平方剩余相差1、7的证明见后)，这是因为上式相减得：
   25–19≡26^2–22^2( mod 93)
   6≡(24+2)^2–(24–2)^2 ( mod 93)
   6≡4*24*2 ( mod 93)
   正好为(4×24)*2≡6 mod 93
   .
   .
   .
   以此类推，21与27的平方剩余相差9，20与28的平方剩余相差12……(证明见后)
   再来证明22(k-1)与24(k+1)的平方剩余为什么相差1？
    证明一：
    设n=4k+1，则k+1为中间数
     (k+1)^2≡b (mod n)     ①
     (k-1)^2≡c (mod n)      ②
     ①-②：b-c≡(k+1)^2-(k-1)^2 (mod n)
            b-c≡ 4k (mod n)
      ∵ 4k≡-1 (mod n)
      ∴ b-c≡ -1 (mod n)
           c–b≡1 (mod n)  证毕

     证明二：
     同理可以证明k+1与k+3相差7。
     设n=4k+1，k+1为中间数
     (k+1)^2≡b (mod n)      ③
     (k+3)^2≡d (mod n)      ④
     ④-③：d-b≡(k+3)^2-(k+1)^2 (mod n)
           d-b≡ 4k+8 (mod n)
      ∵ 4k≡-1 (mod n)
      ∴ d-b≡ -1+8 (mod n)
           d-b≡7 (mod n) 证毕

    Ⅴ、观察24,22,20,18…的平方剩余差为1,9,17…(也可以通过证明一得到该数列)，即平方剩余差是一个等差数列，公差为8。
     a(m)=a(1)+(m-1)*8  a(1)=1  m>0
     s5=1+9+17+…+1+8(m-1)
         =m+4m(m-1)
         =m(4m-3)

    Ⅵ、观察24,26,28,30…的平方剩余差为7,15,23…(也可以通过证明二得到该数列)，即平方剩余差是一个等差数列，公差为8。
     a(m)=a(1)+(m-1)*8  a(1)=7  m>0
     s6=7+15+23+…+7+8(m-1)
         =7m+4m(m-1)
         =m(4m+3)

    Ⅶ、观察23,21,19,17…的平方剩余差为5,13,21…(也可以通过证明得到该数列)，即平方剩余差是一个等差数列，公差为8。
     a(m)=a(1)+(m-1)*8  a(1)=5  m>0
     s7=5+13+21+…+5+8(m-1)
         =5m+4m(m-1)
         =m(4m+1)

    Ⅷ、观察25,27,29,31…的平方剩余差为11,19,27…(也可以通过证明得到该数列)，即平方剩余差是一个等差数列，公差为8。
     a(m)=a(1)+(m-1)*8  a(1)=11  m>0
     s8=11+19+27+…+11+8(m-1)
         =11m+4m(m-1)
         =m(4m+7)

    根据以上，以中间数k+1为中心向中间数的两边共形成4个数列：
      小于k+1方向数列Ⅴ、Ⅶ：
       m(4m-3)、m(4m+1)
       大于k+1方向数列Ⅵ 、Ⅷ：
       m(4m+3)、m(4m+7)

     Ⅴ、Ⅶ数列往小于k+1方向必然与a^2各有一个交点，且两个交点是相邻的。
      Ⅵ 、Ⅷ往大于K+1方向必然与i(i+1)+(n-k/2)各有一个交点，且这两个交点也是相邻的，与Ⅴ、Ⅶ数列的两个交点正好是与K+1为中心的对称点。
    如93，k=24，m=6
   Ⅴ数列：18+6(4*6-3)=144=12^2
    Ⅶ数列：64+5(4*5+1)=169=13^2
    12、13与24相差12、11
   
    Ⅵ 数列：18+6(4*6+3)=180=10*(10+1)+70
     得46-10=36
    Ⅷ数列：67+5(4*5+7)=202=11*(11+1)+70
     得46-11=35
     36、35与24相差12、11

   现在证明Ⅴ数列往减方向与a^2的交点：
   证明：设交点处为a，因为Ⅴ数列以k+1、k-1、k-3…的平方剩余减小的，每个值相隔2，所以m为：
      m=(k+1-a)/2，(k+1)^2≡b (mod n)
    Ⅴ数列可以变为以下：
     b+4(((k+1)-a)/2)^2-3*((k+1)-a)/2  (mod n)
   ≡b+(k+1)^2-2(k+1)a+a^2-3*((k+1)-a)/2 (mod n)
   ≡2b-2(k+1)a+a^2-3(k+1)/2+3a/2 (mod n)
   ≡2(k+1)^2+a^2-a(4(k+1)-3)/2-3(k+1)/2 (mod n)
   ≡(k+1)(4(k+1)-3)/2+a^2 (mod n)
   ≡a^2 (mod n)
   a的值为：
   k+1为奇数且(k+2)/2为奇数时：a=(k+2)/2，否则(k+2)/2为偶数时：a=(k+2)/2+1
   k+1为偶数且(k+1)/2为偶数时：a=(k+1)/2，否则(k+1)/2为奇数时：a=(k+1)/2+1

  Ⅵ、Ⅶ、Ⅷ  数列也可以按此证明

四、以下来证明一般式：
   设n为奇数，n的平方剩余取值范围为[√n]<a≤(n-1)/2，[√n]为不大于√n的整数，n>0。设a^2≡b (mod n)，以a为中心前后按相等的数i(1≤i<a)各取一个数：
   (a-i)^2≡c (mod n)     ⑴
   a^2≡b (mod n)          ⑵
   (a+i)^2≡d (mod n)    ⑶
  上述 ⑶-⑴得：
   d-c≡4ai (mod n)       ⑷
   当a=k，上式变为d-c≡4ki (mod n)，进行以下计算：
   ⅰ、n=4k-1，得4k≡1 (mod n)，此时以中间数a=k为中心
       ⑷式变为：d-c≡i (mod n)
      当i=1,2,3…时，d-c的平方剩余差为1,2,3…，则k-1,k+1平方剩余相差1，k-2,k+2平方剩余相差2，k-3,k+3平方剩余相差3……
   ⅱ、n=4k+1，得4k≡–1 (mod n)，4(k+1)≡3 (mod n)，此时以中间数a=k+1为中心
        ⑷式变为：d-c≡3i (mod n)
       当i=1,2,3…时，d-c的平方剩余差为3,6,9…，则k,k+2平方剩余相差3，k-1,k+3平方剩余相差6，k-3,k+3平方剩余相差9……

   五、平方剩余为完全平方数的分布情况
    通过观察91=7*13平方剩余的几个完全平方数
    10^2≡9  17^2≡16
    27^2≡1  34^2≡64
    30^2≡81 37^2≡4  44^2≡25
    10与17相差7
    27与34相差7
    30、37、44相差7

   再来观察93=3*31平方剩余的几个完全平方数
    23^2≡64  26^2≡25  29^2≡4
    32^2≡1    35^2≡16  38^2≡49
    23、26、29、32、35、38都相差3
   
    这样我们大概可以知道平方剩余为完全平方数分布的一些情况：
    设n=fe，n为奇数，[√n]<a≤(n-1)/2，[√n]为不大于√n的整数，f<e，a的平方剩余为完全平方数。
    当f与e相差不大，a比较均匀分布在上述范围内，差值为f。
    当f与e相差较大，a比较均匀分布在上述范围内的一段区间内，相差越大，区间范围越小，且差值为f。

  本文没有具体算法。