整数分解随笔(三)

scsongls

本次文中未注明处n≥3，且为奇数。
一、对称数
    上次文中，我们找到了中间数，这里我们来定义一下平方剩余中的对称数。
   设a^2≡b (mod n)，其中a的对称数定义为(1≤a≤(n－1)/2)：
         k+中间数－a，即：
    ①  n=4k－1时，中间数为k，对称数为：
          k+k－a=2k－a
       对称数的平方剩余为：(4k≡1 (mod n))
        (2k－a)^2≡4kk－4ka+a^2
                          ≡k－a+b
                          ≡k+b－a
               ( 注：((n－1)/2)^2≡k)
    ②  n=4k+1时，中间数为k+1，对称数为：
          k+k+1－a=2k+1－a
       对称数的平方剩余为：(4k≡－1 (mod n))
        (2k+1－a)^2≡(2k+1)^2－2(2k+1)a+a^2
                          ≡4kk+4k+1－4ka－2a+b
                          ≡－k+a－2a+b
                          ≡n－k+b－a
                (注：((n－1)/2)^2≡n－k)
   根据上述可知：a的对称数的平方剩余为b－a加上(n－1)/2的平方剩余。
   现在来看看以下例子：
  ⅰ n=119=7*17
1^2≡1 , 2^2≡4 , 3^2≡9 , 4^2≡16 ,
5^2≡25 , 6^2≡36 , 7^2≡49, 8^2≡64,
9^2≡81, 10^2≡100, 11^2≡2 , 12^2≡25 ,
13^2≡50 , 14^2≡77 , 15^2≡106 , 16^2≡18 ,
17^2≡51 , 18^2≡86 , 19^2≡4 , 20^2≡43 ,
21^2≡84 , 22^2≡8 , 23^2≡53 , 24^2≡100 ,
25^2≡30 , 26^2≡81 , 27^2≡15 , 28^2≡70 ,
29^2≡8 , 30^2≡67 , 31^2≡9 , 32^2≡72 ,
33^2≡18 , 34^2≡85 , 35^2≡35 , 36^2≡106 ,
37^2≡60 , 38^2≡16 , 39^2≡93 , 40^2≡53 ,
41^2≡15 , 42^2≡98 , 43^2≡64 , 44^2≡32 ,
45^2≡2 , 46^2≡93 , 47^2≡67 , 48^2≡43 ,
49^2≡21 , 50^2≡1 , 51^2≡102 , 52^2≡86 ,
53^2≡72 , 54^2≡60 , 55^2≡50 , 56^2≡42 ,
57^2≡36 , 58^2≡32 , 59^2≡30
   13及对称数的平方剩余为：
      13^2≡50
      (2*30－13)^2≡47^2≡30+50－13≡67
      对照上面平方剩余，47^2≡67

     ⅱ n=93=3*31
1^2≡1 , 2^2≡4 , 3^2≡9 , 4^2≡16 ,
5^2≡25 , 6^2≡36 , 7^2≡49 , 8^2≡64 ,
9^2≡81 , 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 ,
    14及对称数的平方剩余：
       14^2≡10
       (2*23+1－14)^2=33^2≡70+10－14≡66
        对照上面平方剩余：33^2≡66

scsongls

二、对称性、传递性及自反性(名字暂定)
     根据上节可知a^2≡b的对称数是相对K及K+1的对称性，而平方剩余是通过k及n-k来传递的，如果b±a正好为连续两个整数乘积，其对称数的平方剩余则正好与逆序数列一个数的平方剩余相等，根据费马分解法，整数被分解。或
      设a^2≡b (mod n)，c^2≡d (mod n)，如果b－a=d－c，则其对称数的平方剩余相等，其对称数相匹配。
     如 n=119
      ⑴  16^2≡18 (mod 119)，其对称数
      (2*30－16)^2=44^2≡30+18－16≡32
      该数与59－1=58的平方剩余相等
      ∴  58^2≡44^2 (mod 119)
       即18－16=2=1*2时，找到一个匹配数。
      
       ⑵  22^2≡8 (mod 119)
       ∵ 22+8=30 =5*6
      ∴23的对称数与逆序数列一个数相匹配。
       23对称数：(2*30－23)=37
       逆序数列：(59－5)=54
       54^2≡37^2 (mod 119)
     
     通过对称数，可以知道平方剩余俱有对称性和传递性，平方剩余是否也俱备自反性？
    我们来看下面的例子：
     16^2≡18 (mod 119)
     16的平方剩余等于18，18等于16加2，即：18=16+2，代入得
          16^2≡16+2  (mod 119)  =>
          16^2-16-2≡0  (mod 119)   =>
          (16－2)(16+1)≡0 (mod 119)  =>
          14*17≡0 (mod 119)
          14、17与119俱有非平凡因子。
   那么如果 a^2≡b (mod n)，b=a+i(i+1)，把b代入同余式得：
       a^2≡a+i(i+1) (mod n)   =>
       a^2-a-i(i+1)≡0 (mod n)  =>
       (a-(i+1))(a+i)≡0 (mod n)
    即可知道a-(i+1)、a-i这两个数必与n有非平凡因子，即平方剩余俱有自反性。
    这样根据自反性特性，现在来设计一种新的分解n的方法：
    设 a^2≡b (mod n)
    如果按一定的方法构造一个一元二次方程Aa^2+Ba+C≡0 (mod n)，使得这个一元二次方程B^2-4AC是完全平方数，则两个根a1=B1/A1、a2=B2/A2必然可以与a写成(A1*a-B1)(A2*a-B2) ≡0，则gcd(A1*a-B1，n)>1且gcd(A2*a-B2，n)>1，n被分解，其中A、A1、A2、B、B1、B2、C为整数，b=-(Ba+C)/A，A≠0，A1*A2=A。
     现在来看几个例：
①  22^2≡8 (mod 119)   =>
      22^2≡127 (mod 119)  =>
      22^2≡6*22-5 (mod 119)  =>
      22^2-6*22+5≡0 (mod 119)  =>
      (22-5)(22-1)≡0  (mod 119)  =>
       17*21≡0 (mod 119)
       17、21与119有非平凡因子。
      当然也可以：
      22^2≡8 (mod 119)   =>
      22^2≡-22+30 (mod 119)  =>
      22^2+22-30≡0 (mod 119)  =>
      (22-5)(22+6)≡0  (mod 119)  =>
       17*28≡0 (mod 119)
       gcd(17，119)=17
       gcd(28，119)=7
②  102^2≡199 (mod 2041) 该数不容易配方，求该数对称数：
       919^2≡1628 (mod 2041)    =>
       919^2≡-413 (mod 2041)    =>
       919^2≡-919+506 (mod 2041)  =>
       (919+23)(919-22)≡0  (mod 2041)  =>
        942*897≡0 (mod 2041)
        gcd(2041，942)=157
        gcd(2041，897)=13
      
    现在也可以根据这种自反性做进一步的扩展：
    设 x^c≡b (mod n)，c≥2，如果能按一定方法构造一个函数，使得该函数俱有整数解，则解与x的和跟n有非平凡因子，n被分解。

   本次文中提出了分解整数的一个方法，希望大家能对这种方法多提宝贵意见。
    我个人认为该方法应优于费马分解法。