整数分解随笔

scsongls

      整数分解随笔
     以下是我对整数分解的一些想法，主要基于Fermat分解法，也不知道对与错，且还有很多东西搞不清楚，望大家批评指证，并提出宝贵意见，本人十分感谢。
一、先看两个式子：
1+3+5+…+(2n-3)+(2n-1)=n^2  …… ①
2+4+6+…+2(n-1)+2n=n(n+1)   …… ②

以上两式的证明请参考相关书籍。

二、对于((n-1)/2)^2余的求法，即((n-1)/2)^2的平方剩余的求法：（n为奇数）

对于((n-1)/2)^2的平方剩余，我们有以下的求法：

1、当n=4k-1时：余为：
    ((n-1)/2)^2≡((n-1)/2+1)/2 (mod n)                         ③
    商为：((n-1)/2+1)/2-1
    如35=4*9-1
    则((35-1)/2)^2=17^2≡(17+1)/2=9 (mod 35)
    商为：9-1=8
   
    39=4*10-1
    则((39-1)/2)^2=19^2≡(19+1)/2=10 (mod 39)
    商为：10-1=9
   证明：当n=4k-1
    ③式左边为：
    ((n-1)/2)^2=((4k-1-1)/2)^2=(2k-1)^2
    ③式右边为：
     商：((n-1)/2+1)/2-1=((4k-1-1)/2+1)/2-1=k-1
     余：((n-1)/2+1)/2=((4k-1-1)/2+1)/2=k
    则(k-1)*n+k=(k-1)(4k-1)+k=(2k-1)^2
       商        余
      ③式左边=右边，证毕
2、当n=4k+1时；余为：
    ((n-1)/2)^2≡n-((n-1)/4) (nod n)  ④
    商为：((n-1)/4)-1
    如57=4*14+1
    则((57-1)/2)^2=28^2≡57-(28/2)=43 (mod 57)
    商为：((57-1)/2)/2-1=(28/2)-1=13
   
    77=4*19+1
    则((77-1)/2)^2=38^2≡77-(38/2)=58 (mod 77)
    商为：((77-1)/2)/2-1=(38/2)-1=18
    证明：当n=4k+1
        ④式左边为:
         ((n-1)/2)^2=((4k+1-1)/2)^2=(2k)^2
        ④式右边为:
         n*(((n-1)/4)-1)+n-((n-1)/4)=(4k+1)*((4k+1-1)/4)-1)+4k+1-((4k+1-1)/4)=(2k)^2
               商           余
        ④的左边=右边，该式成立。


三、我们来看以下三个数的平方剩余：
，平方剩余的取值范围为[√n]<a≤(n-1)/2，其中n>0，且为奇数，[√n]为不大于√n的整数。a^2≡d(mod n)
35   
√35≈5.91   (35-1)/2=17
则6≤a≤17
6^2≡1,7^2≡14,8^2≡29,9^2≡11
10^2≡30,11^2≡16,12^2≡4,13^2≡29
14^2≡21,15^2≡15,16^2≡11,17^2≡9
对以上的平方剩余，按相反的方向进行排列得：
17^2≡9，16^2≡11，15^2≡15，14^2≡21，13^2≡29，12^2≡4，…
观察上述得：
17与16的平方剩余相差2(11–9=2)，16与15的平方剩余相差4(15–11=4)，15与14的平方剩余相差6(21–14=6)，14与13的平方剩余相差8(29–21=8)，12与13的平方剩余相差10(4+35–29=10)，…
按逆序方向的平方剩余差可得：
2    4    6     8    10 …20  22
33 31  29   27  25 …15  13
上排式子中的33 31 29…是两个数的平方差，如33=17^2–16^2，具体见①式，当然也可以按16^2+1=33或17^2–1=33，但上下两式相加一定等于35，即平方剩余差与相关联两个数的平方差之和一定等于该数n(35)，或者说平方剩余差的正序与逆序之和等于n(35)。


39
√39≈6.24
7^2≡10,8^2≡25,9^2≡3,10^2≡22
11^2≡4,12^2≡27,13^2≡13,14^2≡1
15^2≡30,16^2≡22,17^2≡16,18^2≡12
19^2≡10
对以上的平方剩余，按相反的方向进行排列得：
19^2≡10，18^2≡12，17^2≡16，16^2≡22，15^2≡30，14^2≡1，…
观察上述得：
19与18的平方剩余相差2(12–10=2)，18与17的平方剩余相差4(16–12=4)，17与16的平方剩余相差6(22–16=6)，16与15的平方剩余相差8(30–22=8)，15与14的平方剩余相差10(1+39–30=10)，…
按逆序方向的平方剩余差可得：
2    4    6     8    10 …22  24
37 35  33   31  29 …17  15
上排式子中的37 35 33…是两个数的平方差，如37=19^2–18^2，具体见①式，当然也可以按18^2+1=37或19^2–1=37，但上下两式相加一定等于39，即平方剩余差与相关联两个数的平方差之和一定等于该数n(39)，或者说平方剩余差的正序与逆序之和等于n(39)。


77
√77≈8.77
9^2≡4,10^2≡23,11^2≡44,12^2≡67
13^2≡15,14^2≡42,15^2≡71,16^2≡25
17^2≡58,18^2≡16,19^2≡53,20^2≡15
21^2≡56,22^2≡22,23^2≡67,24^2≡37
25^2≡9,26^2≡60,27^2≡36,28^2≡14
29^2≡71,30^2≡53,31^2≡37,32^2≡23
33^2≡11,34^2≡1,35^2≡70,36^2≡64
37^2≡60,38^2≡58
对以上的平方剩余，按相反的方向进行排列得：
38^2≡58，37^2≡60，36^2≡64，35^2≡70，34^2≡1，…
观察上述得：
38与37的平方剩余相差2(60–58=2)，37与36的平方剩余相差4(64–60=4)，36与35的平方剩余相差6(70–64=6)，35与34的平方剩余相差8(1+77–70=8)，…
按逆序方向的平方剩余差可得：
2    4    6     8    10 …56  58
75 73  71   69  67 …21  19
上排式子中的75 73 71…是两个数的平方差，如75=38^2–37^2，具体见①式，当然也可以按37^2+1=75或38^2–1=75，但上下两式相加一定等于77，即平方剩余差与相关联两个数的平方差之和一定等于该数n(77)，或者说平方剩余差的正序与逆序之和等于n(77)。


我们来证明从(n-1)/2向√n的逆序方向为什么会相差2k?
设n为奇数，[√n]<a≤(n-1)/2
((n-1)/2)^2≡d (mod n)
((n-1)/2-1)^2≡c (mod n)
我们先证明c-d=2
上面两个式子相减得
((n-1)/2)^2-((n-1)/2-1)^2≡d-c (mod n)
因n为奇数，设n=2k+1，代入上式得
k^2-(k-1)^2≡d-c (mod n)
-2k+1≡d-c (mod n)
-(2k+1)-2≡d-c (mod n)
-2≡d-c (mod n)
c-d≡2 (mod n)
证毕。
我们来证明-般式，设n=2j+1(j>0)
((n-1)/2-k)^2≡d (mod n)
((n-1)/2-k-1)^2≡c (mod n)
上式相减得
((n-1)/2-k)^2-((n-1)/2-k-1)^2≡d-c (mod n)
把n=2j+1代入上式得
(j-k)^2-(j-k-1)^2≡d-c (mod n)
2(j-k)-1≡d-c (mod n)
2j+1-2k-2≡d-c (mod n)
-2(k+1)≡d-c (mod n)
c-d≡2(k+1) (mod n)
证毕。

我们再看一个式子：
a^2≡d (mod n)
两边加2a+1得
a^2+2a+1≡d+2a+1 (mod n)
(a+1)^2≡d+a+a+1 (mod n)
即下个数的平方剩余等于该数的平方剩余加2倍该数再加1

scsongls

四、相邻平方剩余差逆序的规律
观察上述35、39、77三个数的相邻平方剩余差逆序方向，发现((n-1)/2)^2≡d (mod n)中的d，如果是偶数或奇数，按逆序方向与它相邻数的平方剩余差按2 4 6 8…相加，这些平方剩余同样也是偶数或奇数(与d的奇偶性相同)，直到大于n，然后这些平方剩余再按奇数或偶数的规律按2k的大小进行增加直到再次大于n，这样的平方剩余是奇偶交替(大于n就交换)。
如35：逆序方向的平方剩余为9 11 15 21 29都为奇数，下一个数29+10=39>35，则39–35=4，接下来与之相邻的两个平方剩余16，30都为偶数，下一个数30+16=46>35，所以46–35=11，再次变成奇数。
39、77都有同样的规律。即对于n为奇数，[√n]<a<=(n-1)/2，按逆序的平方剩余都有该规律。


五、根据上节所述，我们知道n的相邻间平方剩余差的逆序排列为等差数列2 4 6 8…2m。(n-1)/2的平方剩余与它不相邻数的平方剩余差又是怎样的呢？
     先举例说明：
      我们来看35，17^2≡9 (mod 35)，16的平方剩余为11，与17的平方剩余9相差2，15的平方剩余为15，与17的平方剩余9相差6：15–9=6，而6=2+4，14的平方剩余21，与17的平方剩余9相差12：21–9=12，而12=2+4+6，13的平方剩余为29，与17的平方剩余9相差20：29–9=20，而20=2+4+6+8。
    上述39、77都具有这样的性质，即奇数的平方剩余都有这样的性质，对于素数和a^k(a为大于2的奇数， k≥2)虽有这样的性质，但却没有两两配对的数。
    如果给出某个数的平方剩余(n为奇数)：
         b^2≡c (mod n)  
      已知 ((n-1)/2)^2≡d (mod n)
      求得两个平方剩余差： c-d=a
     根据②求等差数列的和可得：
    2+4+6+8+…+2m=m(m+1)=a  ⑤
    m^2+m-a=0，
   上式为一元二次方程，根据一元二次方程的通解公式(-b±√(b^2-4ac))/2(只取正数，舍去负数)得：
       m=(-1+√(1+4a))/2，
       当1+4a为完全平方数时，m有解，有解，则可分解n，先来看几个例，再来看具体算法：
35：8^2≡29 (mod 35)
         17^2≡9  (mod 35)
        29-9=20*4+1=81=9^2
    所以该式有解：(两种方法)
     1、m=(-1+9)/2=4
             (17-4)^2=13^2≡29 (mod 35)
             即13^2≡8^2 (mod 35)
     2、(2*8)^2=16^2≡9^2  (mod 35)
          即如果4a+1为完全平方数，与该数乘2是同余的
77：10^2≡23 (mod 77)
         38^2≡58 (mod 77)
    因为23是奇数，58是偶数，所以
     23+77–58=42*4+1=169=13^2
     1、m=(-1+13)/2=6
           (38-6)^2=32^2≡10^2 (mod 77)
     2、(2*10)^2=20^2≡13^2 (mod 77)
  
  依据上述我们可以设计出一种算法(取值范围为[√n]<a≤(n-1)/2)：
     算法一
   Ⅰ、计算((n-1)/2)^2≡d (mod n)，计算方法可参照前述。
   Ⅱ、从n的平方剩余中任取-个数b，不要取太靠近((n-1))/2的数：
         b^2≡c (mod n)
   Ⅲ、判断c、d的奇偶性，如果同奇或同偶：c-d=a，1奇1偶：c+n-d=a，转Ⅳ
    Ⅳ、计算1+4a，判断是否为完全平方数，如果是完全平方数：1+4a=h^2，则两种计算方法：
    ⑴  求出m=(-1+h)/2
         ((n-1)/2-m)^2≡b^2 (mod n)
    ⑵ (2*b)^2≡h^2 (mod n)
    转Ⅴ
    如果不是完全平方数，a=a+2n，设置-个阀值g，且k=k+1(k的初值为0)，如果k<g则转Ⅳ，否则调整b值，从Ⅱ开始计算。
     Ⅴ 根据和或者差值，与n进行碾转相除法即可求出n的因子。
      问题是：我调整过k值，当k值不超过20或30时，查找速度明显好于k>40以上，自我感觉可能与我写的完全平方数判断算法不好有关，但我也不知道如何去调整这个k值。
      还有b如何调整，也是-个问题，我的做法是b=b+1，这个查找效率极其糟糕，b值如何调整，我也没有具体的方法。



六、根据以上介绍我们再来设计一个算法：(设n为奇数，[√n]<a≤(n-1)/2)
  数35：(35–1)/2=17
                 17^2≡9 (mod 35)
     对平方剩余9开方：√9=3
     很碰巧17的平方剩余正好是-个完全平方数9=3^2：(17+3)(17-3)≡0 (mod 35)
       gcd(35,20)=5
       gcd(35,14)=7

数39：(39-1)/2=19
                 19^2≡10 (mod 39)
     对平方剩余10开方：√10≈3.16，因19的平方剩余10不是完全平方数，找一个大于10的完全平方数且为偶数，因4>3.16，4^2=16为偶数，与19的平方剩余10的差为：
           16–10=6
   根据第五节的描述求：
       6*4+1=25=5^2为完全平方数
按上节描述有两种求法：
      ⑴、m=(-1+5)/2=2
         (19-2)^2=17^2≡4^2 (mod 39)
      ⑵ 、(2*4)^2=8^2≡5^2 (mod 39)
以上两式根据碾转相除法即可求得39的因子。

数77：(77-1)/2=38
                 38^2≡58 (mod 77)
     对平方剩余58开方：√58≈7.61，因38的平方剩余58不是完全平方数，找-个大于58的完全平方数且为偶数，因8>7.61，8^2=64为偶数，与38的平方剩余58的差为：
           64–58=6
   根据第五节的描述求：
       6*4+1=25=5^2为完全平方数
按上节描述有两种求法：
      ⑴、m=(-1+5)/2=2
         (38-2)^2=36^2≡8^2 (mod 77)
      ⑵ 、(2*8)^2=16^2≡5^2 (mod 77)
以上两式中的任一式根据碾转相除法即可求得77的因子。
    根据上述所得设计一算法：
    算法二
   Ⅰ、计算((n-1)/2)^2≡d (mod n)，计算方法可参照前述(n为奇数)。
   Ⅱ、计算√d，选一数b>√d，且b与d同奇或同偶，k=0。
   Ⅲ、a=b^2-d
            判断1+4a是否为完全平方数，如1+4a=h^2转Ⅴ，否则转Ⅳ
    Ⅳ、if  k<g(设置的一个阀值)
               a=a+2*n
               k=k+1
            else
                b=b+2
                k=0
            endif
            转Ⅲ
    Ⅴ、按以下两种方种计算：
       ⑴  求出m=(-1+h)/2
         ((n-1)/2-m)^2≡b^2 (mod n)
       ⑵ (2*b)^2≡h^2 (mod n)
      碾转相除法求出n的因子。

  按上述算法我们来看例：
1403：(1403-1)/2=701
    701^2≡(701+1)/2=351 (mod 1403)
    √351≈18.73
    ∵351为奇数 19>18.73
     19^2–351=10
      1+4*10=41不是完全平方数，重选一个数
     21^2–351=90
     1+4*90=361=19^2
   按以下两种方法求：
    ⑴、m=(-1+19)/2=9
         (701-9)^2=692^2≡21^2 (mod 1403)
    ⑵ 、(2*21)^2=42^2≡19^2 (mod 1403)
    根据⑴ gcd(1403,713)=23
                  gcd(1403,671)=61
    根据 ⑵ gcd(1403,61)=61
                  gcd(1403,23)=23
     ∴ 1403=23*61
   再举一个例
  

scsongls

  10001：(10001-1)/2=5000
    5000^2≡10001–5000/2=7501 (mod 10001)
    √7501≈86.61
    ∵7501为奇数 87>86.61
     87^2–7501=68
      1+4*68=273不是完全平方数，重选一个数87+2=89
     89^2–7501=420
     1+4*420=1681=41^2
   按以下两种方法求：
    ⑴、m=(-1+41)/2=20
         (5000-20)^2=4980^2≡89^2 (mod 10001)
    ⑵ 、(2*89)^2=178^2≡41^2 (mod 1403)
    根据⑴ gcd(10001,4891)=73
                  gcd(10001,5069)=137
    根据 ⑵ gcd(10001,219)=73
                  gcd(10001,137)=137
     ∴ 10001=73*137

   上述算法在12位以内速度还算可以，到14位计算的速度极剧下降。如下两个数(按超大整数的加减乘除和二分查找完全平方来计算的)：
216781*1083541=234891101521
1388461*11320957=15718707277177

第一个数234891101521耗时不到一分钟就能找到结果，第二个数15718707277177耗时近两个小时，不知道是否是开根号和完全平方数的判断算法写得太差了。
    该算法是否跟位数有关，也是一个未知数。

七、中间数(设n为奇数，a≤(n-1)/2)
    根据上述描述，(n-1)/2逆序的相邻平方剩余差为2 4 6 8…，相加和：
      S=2+4+6+8+…
    ((n-1)/2)^2≡d (mod n)
    m=S+d         ⑥
   根据 ①式：
     a^2=1+3+5+7+…
   m与a^2是否在某个点相等？即正序中一个数平方同逆序平方和与d的差正好交汇于某点(1+4S为完全平方数，或m=a^2)——中间数？如果有，又是多少？
  35：(35-1)/2=17^2≡9 (mod 35)
      S=2+4+6+…+16=72
      72+9=81=9^2
   77：(77-1)=38^2≡58 (mod 77)
       S=2+4+6+…+36=342
       342+58=400=20^2
  中间数可以按以下求法：
   n=4k-1：中间数m=①-②=d
   n=4k+1：中间数m=①-②=d-(n-1)/2
   35、77可以按此直接求出，但中间数与分解的关系如何？我不清楚，也没有进行进一步的算法研究(这个中间数似乎与算法一有一定的关联性)。

八、当然根据平方剩余逆序，我们知道当两个相邻平方剩余差如果大于n，则另一个平方剩余会很小，这样也可以设计一种算法，不过未去研究，先看几个例：
   77：(77-1)/2=38^2≡58 (mod 77)
   ⑴ n的情况：  77-58=19
       √19≈4.36
       取整数部分4，与4相邻数为3、5，两数之乘积分别为：4*5=20>19
         4*3=12<19
        ∴ 38–3=35^2≡(58+12)=70 (mod 77)
        38-4=34^2≡(58+20)=78 (mod 77)
       ∵ 78>77
       ∴ 34^2≡78-77=1 (mod 77)
     ⑵  2n的情况：  2*77-58=96
       √96≈9.80
       取整数部分9，与9相邻数10，两数之积：9*10=90<96
         10*11=110>96
        ∴ 38–9=29^2≡(58+90)=148 (mod 77)
       ∵ 148>77
       ∴ 29^2≡148-77=71 (mod 77)
       38-10=28^2≡(58+110)=168 (mod 77)
       ∵ 168>77
       ∴ 28^2≡168-2*77=14 (mod 77)
       3n、4n也可照此计算。

   1403：(1403-1)/2=701^2≡351 (mod 1403)
   ⑴ n的情况：  1403-351=1052
       √1052≈32.43
       取整数部分32，与32相邻数为31、33，两数之积分别为：32*33=1056>1052
         32*31=992<1052
        ∴ 701–31=670^2≡(351+992)=1343 (mod 1403)
        701-32=669^2≡1056–1052=4 (mod 1403)
     ⑵  2n的情况：  2*1403-351=2455
       √2455≈49.55
       取整数部分49，与49相邻数为50，两数之积：49*50=2450<2455
         50*51=2550>2455
        ∴ 701–49=652^2≡(351+2450)=2801 (mod 1403)
       ∵ 2801>1403
       ∴ 652^2≡2801-1403=1398 (mod 1403)
       701-50=651^2≡(351+2550)=2901 (mod 1403)
       ∵ 2901>1403
       ∴ 651^2≡2901-2*1403=95 (mod 1403)
       3n、4n也可照此计算。

scsongls

九、伪单位元
     对素数p而言，在[1,p-1]范围内有必存在单位元e，使a*aˉ=e，或a*e=aˉ
     对合数n(n=2j+1)而言，在[1,n-1]范围內不是所有的元素都有逆元的存在。但我们可以构造出合数(非a^k形式的合数)的伪单位元e，使a*e=aˉ，且a^2≡aˉ^2 (mod n)。而伪单位元e定义为e^2≡1 (mod n)(e≠±1)。
    先看上面的例：
    35；伪单位元为 6^2≡1 (mod 35)
           8^2≡29 (mod 35)
           8*6=48≡13 (mod 35)
           8^2≡13^2 (mod 35)
           9^2≡11 (mod 35)
           9*6=54≡19 (mod 35)
           9^2≡19^2 (mod 35)或
        在[1,(n-1)/2]范围，即[1,17]
           9^2≡16^2 (mod 35)

     77；伪单位元为 34^2≡1 (mod 77)
           10^2≡23 (mod 77)
           10*34=340≡32 (mod 77)
           10^2≡32^2 (mod 77)
           17^2≡58 (mod 77)
           17*34=578≡39 (mod 77)
           17^2≡39^2 (mod 77)或
        在[1,(n-1)/2]范围，即[1,38]
           17^2≡38^2 (mod 77)

  下面我们来分析：
   根据费马分解法，可知对于奇合数n=ts(n≠a^k)有：
      a=(t+s)/2    c=(t-s)/2
      得：a^2≡c^2 (mod n)
   对上式我们可知在[√n]<a≤(n-1)/2范围必有一对配对数，
       a^2≡d  (mod n)    (n,a)=1
       c^2≡d  (mod n)    (n,c)=1
    这对配对数的平方剩余相等。上面两式相除得：
     (a/c)^2≡1 (mod n)
     又 ∵ (n,c)=1   (n,c)|a
       ∴ cx≡a (mod n)必有解：
            x≡e (e≠±1)
       即a/c≡e (mod n) (e≠±1)
    得存在伪单位元： e^2≡1 (mod n)
    由伪单位元知，对于其它的元素：a^2≡c^2 (mod n)  (其中a^2>n，c^2>n)，有：
    上式两边同时乘以1：
     a^2*1≡c^2*1 (mod n)
     ∵ e^2≡1 (mod n)
     ∴ a^2*e^2≡c^2*1 (mod n)
        (ae)^2≡c^2 (mod n)
        (ae+c)(ae-c)≡0 (mod n)
        上式必有一式成立
       ae+c≡0 (mod n) 或
       ae-c≡0 (mod n)
      得：ae≡-c (mod n)
               ae≡c (mod n)
    但绝大多数情况下ac≠e (mod n)
    这样可以知道在[√n]<a≤(n-1)/2范围内任意给定一个值a，它只有三种可能性(n=2j+1,n≠a^k)：
      1、gcd(n,a)>1
      2、a^2≡d (mod n)且d=b^2<√n
      3、a^2≡c^2 (mod n)

    按上述描述也可以设计出一种算法来，先看一例：
   93：10^2≡7 (mod 93)
            11^2≡28 (mod 93)
      两式相除得：
           (11/10)^2≡4 (mod 93)
         ∵ 4=2^2
          又∵ (93,10)|11
           ∴ 11/10≡29 (mod 93)
            29^2≡4 (mod 93)
           得 (93,31)=31
                (93,27)=3
                93=31*3
    当然如果两个平方剩余相除是完全平方数，平方剩余的乘积也是完全平方数：
      (10*11)^2≡7*28=14^2 (mod 93)
      17^2≡14^2 (mod 93)
      (17+14)(17-14)≡0 (mod 93)
      得：93=31*3

    算法三：
    Ⅰ在√n<a≤(n-1)/2范围内，任选两个数(从√n开始)：
         a^2≡b (mod n)
         c^2≡d (mod n)
    Ⅱif gcd(n,a)>1or gcd(n,c)>1
             exit
    Ⅲ if b or d 是完全平方数
              exit
    Ⅳ  if b>d
              f=b/d
           else
              f=d/b
           if f是完全平方数
                 exit
           else
                 goto Ⅰ
   
   在本文中，未涉及a^k的判断，对于a^k的判断在√n<a≤(n-1)/2的范围内，必有一个平方剩余：
         c^2≡0 (mod n)
  这个是与素数的差别。

     断断续续暂时先写到这里，文中还有不对的地方，愿大家指出来，便于以后修改，谢谢！

scsongls

   附上1403的平方剩余，供大家参考。
  1403   a∈[38,701]
38^2≡41 , 39^2≡118 , 40^2≡197 , 41^2≡278 , 42^2≡361 , 43^2≡446 , 44^2≡533 , 45^2≡622 ,
46^2≡713 , 47^2≡806 , 48^2≡901 , 49^2≡998 ,50^2≡1097 , 51^2≡1198 , 52^2≡1301 , 53^2≡3 ,
54^2≡110 , 55^2≡219 , 56^2≡330 , 57^2≡443 ,58^2≡558 , 59^2≡675 , 60^2≡794 , 61^2≡915 ,
62^2≡1038 , 63^2≡1163 , 64^2≡1290 , 65^2≡16 , 66^2≡147 , 67^2≡280 , 68^2≡415 , 69^2≡552 ,
70^2≡691 , 71^2≡832 , 72^2≡975 , 73^2≡1120 , 74^2≡1267 , 75^2≡13 , 76^2≡164 , 77^2≡317 ,
78^2≡472 , 79^2≡629 , 80^2≡788 , 81^2≡949 , 82^2≡1112 , 83^2≡1277 , 84^2≡41 , 85^2≡210 ,
86^2≡381 , 87^2≡554 , 88^2≡729 , 89^2≡906 , 90^2≡1085 , 91^2≡1266 , 92^2≡46 , 93^2≡231 ,
94^2≡418 , 95^2≡607 , 96^2≡798 , 97^2≡991 , 98^2≡1186 , 99^2≡1383 , 100^2≡179 , 101^2≡380 ,
102^2≡583 , 103^2≡788 , 104^2≡995 , 105^2≡1204 , 106^2≡12 , 107^2≡225 , 108^2≡440 , 109^2≡657 ,
110^2≡876 , 111^2≡1097 , 112^2≡1320 , 113^2≡142 , 114^2≡369 , 115^2≡598 , 116^2≡829 , 117^2≡1062 ,
118^2≡1297 , 119^2≡131 , 120^2≡370 , 121^2≡611 , 122^2≡854 , 123^2≡1099 , 124^2≡1346 , 125^2≡192 ,
126^2≡443 , 127^2≡696 , 128^2≡951 , 129^2≡1208 , 130^2≡64 , 131^2≡325 , 132^2≡588 , 133^2≡853 ,
134^2≡1120 , 135^2≡1389 , 136^2≡257 , 137^2≡530 , 138^2≡805 , 139^2≡1082 , 140^2≡1361 , 141^2≡239 ,
142^2≡522 , 143^2≡807 , 144^2≡1094 , 145^2≡1383 , 146^2≡271 , 147^2≡564 , 148^2≡859 , 149^2≡1156 ,
150^2≡52 , 151^2≡353 , 152^2≡656 , 153^2≡961 , 154^2≡1268 , 155^2≡174 , 156^2≡485 , 157^2≡798 ,
158^2≡1113 , 159^2≡27 , 160^2≡346 , 161^2≡667 , 162^2≡990 , 163^2≡1315 , 164^2≡239 , 165^2≡568 ,
166^2≡899 , 167^2≡1232 , 168^2≡164 , 169^2≡501 , 170^2≡840 , 171^2≡1181 , 172^2≡121 , 173^2≡466 ,
174^2≡813 , 175^2≡1162 , 176^2≡110 , 177^2≡463 , 178^2≡818 , 179^2≡1175 , 180^2≡131 , 181^2≡492 ,
182^2≡855 , 183^2≡1220 , 184^2≡184 , 185^2≡553 , 186^2≡924 , 187^2≡1297 , 188^2≡269 , 189^2≡646 ,
190^2≡1025 , 191^2≡3 , 192^2≡386 , 193^2≡771 , 194^2≡1158 , 195^2≡144 , 196^2≡535 , 197^2≡928 ,
198^2≡1323 , 199^2≡317 , 200^2≡716 , 201^2≡1117 , 202^2≡117 , 203^2≡522 , 204^2≡929 , 205^2≡1338 ,
206^2≡346 , 207^2≡759 , 208^2≡1174 , 209^2≡188 , 210^2≡607 , 211^2≡1028 , 212^2≡48 , 213^2≡473 ,
214^2≡900 , 215^2≡1329 , 216^2≡357 , 217^2≡790 , 218^2≡1225 , 219^2≡259 , 220^2≡698 , 221^2≡1139 ,
222^2≡179 , 223^2≡624 , 224^2≡1071 , 225^2≡117 , 226^2≡568 , 227^2≡1021 , 228^2≡73 , 229^2≡530 ,
230^2≡989 , 231^2≡47 , 232^2≡510 , 233^2≡975 , 234^2≡39 , 235^2≡508 , 236^2≡979 , 237^2≡49 ,
238^2≡524 , 239^2≡1001 , 240^2≡77 , 241^2≡558 , 242^2≡1041 , 243^2≡123 , 244^2≡610 , 245^2≡1099 ,
246^2≡187 , 247^2≡680 , 248^2≡1175 , 249^2≡269 , 250^2≡768 , 251^2≡1269 , 252^2≡369 , 253^2≡874 ,
254^2≡1381 , 255^2≡487 , 256^2≡998 , 257^2≡108 , 258^2≡623 , 259^2≡1140 , 260^2≡256 , 261^2≡777 ,
262^2≡1300 , 263^2≡422 , 264^2≡949 , 265^2≡75 , 266^2≡606 , 267^2≡1139 , 268^2≡271 , 269^2≡808 ,
270^2≡1347 , 271^2≡485 , 272^2≡1028 , 273^2≡170 , 274^2≡717 , 275^2≡1266 , 276^2≡414 , 277^2≡967 ,
278^2≡119 , 279^2≡676 , 280^2≡1235 , 281^2≡393 , 282^2≡956 , 283^2≡118 , 284^2≡685 , 285^2≡1254 ,
286^2≡422 , 287^2≡995 , 288^2≡167 , 289^2≡744 , 290^2≡1323 , 291^2≡501 , 292^2≡1084 , 293^2≡266 ,
294^2≡853 , 295^2≡39 , 296^2≡630 , 297^2≡1223 , 298^2≡415 , 299^2≡1012 , 300^2≡208 , 301^2≡809 ,
302^2≡9 , 303^2≡614 , 304^2≡1221 , 305^2≡427 , 306^2≡1038 , 307^2≡248 , 308^2≡863 , 309^2≡77 ,

scsongls

310^2≡696 , 311^2≡1317 , 312^2≡537 , 313^2≡1162 , 314^2≡386 , 315^2≡1015 , 316^2≡243 , 317^2≡876 ,
318^2≡108 , 319^2≡745 , 320^2≡1384 , 321^2≡622 , 322^2≡1265 , 323^2≡507 , 324^2≡1154 , 325^2≡400 ,
326^2≡1051 , 327^2≡301 , 328^2≡956 , 329^2≡210 , 330^2≡869 , 331^2≡127 , 332^2≡790 , 333^2≡52 ,
334^2≡719 , 335^2≡1388 , 336^2≡656 , 337^2≡1329 , 338^2≡601 , 339^2≡1278 , 340^2≡554 , 341^2≡1235 ,
342^2≡515 , 343^2≡1200 , 344^2≡484 , 345^2≡1173 , 346^2≡461 , 347^2≡1154 , 348^2≡446 , 349^2≡1143 ,
350^2≡439 , 351^2≡1140 , 352^2≡440 , 353^2≡1145 , 354^2≡449 , 355^2≡1158 , 356^2≡466 , 357^2≡1179 ,
358^2≡491 , 359^2≡1208 , 360^2≡524 , 361^2≡1245 , 362^2≡565 , 363^2≡1290 , 364^2≡614 , 365^2≡1343 ,
366^2≡671 , 367^2≡1 , 368^2≡736 , 369^2≡70 , 370^2≡809 , 371^2≡147 , 372^2≡890 , 373^2≡232 ,
374^2≡979 , 375^2≡325 , 376^2≡1076 , 377^2≡426 , 378^2≡1181 , 379^2≡535 , 380^2≡1294 , 381^2≡652 ,
382^2≡12 , 383^2≡777 , 384^2≡141 , 385^2≡910 , 386^2≡278 , 387^2≡1051 , 388^2≡423 , 389^2≡1200 ,
390^2≡576 , 391^2≡1357 , 392^2≡737 , 393^2≡119 , 394^2≡906 , 395^2≡292 , 396^2≡1083 , 397^2≡473 ,
398^2≡1268 , 399^2≡662 , 400^2≡58 , 401^2≡859 , 402^2≡259 , 403^2≡1064 , 404^2≡468 , 405^2≡1277 ,
406^2≡685 , 407^2≡95 , 408^2≡910 , 409^2≡324 , 410^2≡1143 , 411^2≡561 , 412^2≡1384 , 413^2≡806 ,
414^2≡230 , 415^2≡1059 , 416^2≡487 , 417^2≡1320 , 418^2≡752 , 419^2≡186 , 420^2≡1025 , 421^2≡463 ,
422^2≡1306 , 423^2≡748 , 424^2≡192 , 425^2≡1041 , 426^2≡489 , 427^2≡1342 , 428^2≡794 , 429^2≡248 ,
430^2≡1107 , 431^2≡565 , 432^2≡25 , 433^2≡890 , 434^2≡354 , 435^2≡1223 , 436^2≡691 , 437^2≡161 ,
438^2≡1036 , 439^2≡510 , 440^2≡1389 , 441^2≡867 , 442^2≡347 , 443^2≡1232 , 444^2≡716 , 445^2≡202 ,
446^2≡1093 , 447^2≡583 , 448^2≡75 , 449^2≡972 , 450^2≡468 , 451^2≡1369 , 452^2≡869 , 453^2≡371 ,
454^2≡1278 , 455^2≡784 , 456^2≡292 , 457^2≡1205 , 458^2≡717 , 459^2≡231 , 460^2≡1150 , 461^2≡668 ,
462^2≡188 , 463^2≡1113 , 464^2≡637 , 465^2≡163 , 466^2≡1094 , 467^2≡624 , 468^2≡156 , 469^2≡1093 ,
470^2≡629 , 471^2≡167 , 472^2≡1110 , 473^2≡652 , 474^2≡196 , 475^2≡1145 , 476^2≡693 , 477^2≡243 ,
478^2≡1198 , 479^2≡752 , 480^2≡308 , 481^2≡1269 , 482^2≡829 , 483^2≡391 , 484^2≡1358 , 485^2≡924 ,
486^2≡492 , 487^2≡62 , 488^2≡1037 , 489^2≡611 , 490^2≡187 , 491^2≡1168 , 492^2≡748 , 493^2≡330 ,
494^2≡1317 , 495^2≡903 , 496^2≡491 , 497^2≡81 , 498^2≡1076 , 499^2≡670 , 500^2≡266 , 501^2≡1267 ,
502^2≡867 , 503^2≡469 , 504^2≡73 , 505^2≡1082 , 506^2≡690 , 507^2≡300 , 508^2≡1315 , 509^2≡929 ,
510^2≡545 , 511^2≡163 , 512^2≡1186 , 513^2≡808 , 514^2≡432 , 515^2≡58 , 516^2≡1089 , 517^2≡719 ,
518^2≡351 , 519^2≡1388 , 520^2≡1024 , 521^2≡662 , 522^2≡302 , 523^2≡1347 , 524^2≡991 , 525^2≡637 ,
526^2≡285 , 527^2≡1338 , 528^2≡990 , 529^2≡644 , 530^2≡300 , 531^2≡1361 , 532^2≡1021 , 533^2≡683 ,
534^2≡347 , 535^2≡13 , 536^2≡1084 , 537^2≡754 , 538^2≡426 , 539^2≡100 , 540^2≡1179 , 541^2≡857 ,
542^2≡537 , 543^2≡219 , 544^2≡1306 , 545^2≡992 , 546^2≡680 , 547^2≡370 , 548^2≡62 , 549^2≡1159 ,
550^2≡855 , 551^2≡553 , 552^2≡253 , 553^2≡1358 , 554^2≡1062 , 555^2≡768 , 556^2≡476 , 557^2≡186 ,
558^2≡1301 , 559^2≡1015 , 560^2≡731 , 561^2≡449 , 562^2≡169 , 563^2≡1294 , 564^2≡1018 , 565^2≡744 ,
566^2≡472 , 567^2≡202 , 568^2≡1337 , 569^2≡1071 , 570^2≡807 , 571^2≡545 , 572^2≡285 , 573^2≡27 ,
574^2≡1174 , 575^2≡920 , 576^2≡668 , 577^2≡418 , 578^2≡170 , 579^2≡1327 , 580^2≡1083 , 581^2≡841 ,
582^2≡601 , 583^2≡363 , 584^2≡127 , 585^2≡1296 , 586^2≡1064 , 587^2≡834 , 588^2≡606 , 589^2≡380 ,
590^2≡156 , 591^2≡1337 , 592^2≡1117 , 593^2≡899 , 594^2≡683 , 595^2≡469 , 596^2≡257 , 597^2≡47 ,
598^2≡1242 , 599^2≡1036 , 600^2≡832 , 601^2≡630 , 602^2≡430 , 603^2≡232 , 604^2≡36 , 605^2≡1245 ,
606^2≡1053 , 607^2≡863 , 608^2≡675 , 609^2≡489 , 610^2≡305 , 611^2≡123 , 612^2≡1346 , 613^2≡1168 ,
614^2≡992 , 615^2≡818 , 616^2≡646 , 617^2≡476 , 618^2≡308 , 619^2≡142 , 620^2≡1381 , 621^2≡1219 ,
622^2≡1059 , 623^2≡901 , 624^2≡745 , 625^2≡591 , 626^2≡439 , 627^2≡289 , 628^2≡141 , 629^2≡1398

scsongls

630^2≡1254 , 631^2≡1112 , 632^2≡972 , 633^2≡834 , 634^2≡698 , 635^2≡564 , 636^2≡432 , 637^2≡302 ,
638^2≡174 , 639^2≡48 , 640^2≡1327 , 641^2≡1205 , 642^2≡1085 , 643^2≡967 , 644^2≡851 , 645^2≡737 ,
646^2≡625 , 647^2≡515 , 648^2≡407 , 649^2≡301 , 650^2≡197 , 651^2≡95 , 652^2≡1398 , 653^2≡1300 ,
654^2≡1204 , 655^2≡1110 , 656^2≡1018 , 657^2≡928 , 658^2≡840 , 659^2≡754 , 660^2≡670 , 661^2≡588 ,
662^2≡508 , 663^2≡430 , 664^2≡354 , 665^2≡280 , 666^2≡208 , 667^2≡138 , 668^2≡70 , 669^2≡4 ,
670^2≡1343 , 671^2≡1281 , 672^2≡1221 , 673^2≡1163 , 674^2≡1107 , 675^2≡1053 , 676^2≡1001 , 677^2≡951 ,
678^2≡903 , 679^2≡857 , 680^2≡813 , 681^2≡771 , 682^2≡731 , 683^2≡693 , 684^2≡657 , 685^2≡623 ,
686^2≡591 , 687^2≡561 , 688^2≡533 , 689^2≡507 , 690^2≡483 , 691^2≡461 , 692^2≡441 , 693^2≡423 ,
694^2≡407 , 695^2≡393 , 696^2≡381 , 697^2≡371 , 698^2≡363 , 699^2≡357 , 700^2≡353 , 701^2≡351 ,