整数分解随笔-特殊k值的计算

scsongls

整数分解随笔-特殊k值的计算

一、本节讨论连续两个整数积的一般式(见整数分解随笔(3))
先看一个例:
例1: 67^2≡23(mod 319) =>
  67^2≡69/3(mod 319) =>
  3*67^2-67-2≡0 (mod 319)
  (3*67+2)(67-1)≡0 (mod 319)
   203*66≡0(mod 319)
   (203,319)=29  (66,319)=11
    29*11=319
  也可以: 67^2≡23 (mod 319) =>
              (3*23-2)^2≡23 (mod 319) =>
              9*23^2-13*23+4≡0 (mod 319) =>
              (9*23-4)(23-1)≡0 (mod 319) =>
               203*22≡0 (mod 319)     
          得到相同的结果
  例2: 35^2≡29 (mod 299) =>
         35^2≡35-6(mod 299) =>
         35^2≡35-(35+1)/6 (mod 299) =>
        6*35^2-5*35+1≡0 (mod 299)  =>
        (2*35-1)(3*35-1)=0 (mod 299) =>
         39*69≡0 (mod 299)
         (39,299)=13   (69,299)=23      
设n为奇数, a^2≡b(mod n), 如果可以变换成
  Aa^2+Ba+C≡0(mod n) A<>0  =>
  4(Aa)^2+4ABa≡-4AC(mod n) =>
  4(Aa)^2+4ABa+B^2≡B^2-4AC (mod n) =>
  (2Aa+B)^2≡B^2-4AC (mod n)   (1-1)
  即: Aa^2+Ba+C≡0(mod n) A<>0的一元二次方程的根，必为二次剩余值
  例1也可以化为: (2*3*67-1)^3≡1^2+4*3*2 (mod 319) =>
       82^2≡5^2 (mod 319)

二、本节讨论k为两个连续整数积时的特殊情况下的计算，其中本节的 n=4k-1, k>=1
  1、k=i(i-1)时
    k=i(i-1) =>   4k=4i(i-1)  => 4k+1=4i(i-1)+1 对该式求同余
    (2i-1)^2≡2 (mod n)
    因2k-k=k=i(i-1),  所以2k必在后序序列上
  2、2k=i(i-1)时
    2k=i(i-1) =>   2*4k=4i(i-1)  => 2*4k+1=4i(i-1)+1 对该式求同余
    (2i-1)^2≡3 (mod n)
    因3k-k=2k=i(i-1),所以3k必在后序序列上
  3、3k=i(i-1)时
    3k=i(i-1) =>   3*4k=4i(i-1)  => 3*4k+1=4i(i-1)+1 对该式求同余
    (2i-1)^2≡4 (mod n)
    对于后序序列
   (2k-i)^2≡k-i+i^2 (mod n)  =>
           ≡k+3k=4k≡1(mod n)
   即: (2k-i)^2≡1(mod n)
   当然，也可以得到:
   (2k)^2≡k(mod n)  => (2k)^2≡3k-2k (mod n) =>
     (2k)^2+2k-i(i-1)≡0(mod n) => (2k+i)(2k-(i-1))≡0 (mod n)
  3k为两个连续整数积时，n为合数，必被分解
   例:n=319=4*80-1   k=80  3k=240=15*16
   这类可以得到一般式:
   设n=4k-1>10, 如果有(j^2-1)k=i(i-1), j>1, i>1 可得:
   (j^2-1)k≡i(i-1) (mod n)  =>
   (j^2-1)*4k+1≡4*i(i-1)+1 (mod n)  =>
   (2i-1)^2≡j^2 (mod n)
   如果从后序序列计算，可得:  (2k-i)^2≡k+i(i-1) (mod n)
    ① i=2t t>0 , 上式:
     (2k-j)^2≡k+((2t)^2-1)k (mod n)  =>
             ≡ 4k * t^2 (mod n)  =>
             ≡ t^2 (mod n)
    ② i=2t+1 t>0 , 上式:
     (2k-j)^2≡k+((2t+1)^2-1)k (mod n)  =>
             ≡ (4t^2+4t+1)k (mod n)  =>
             ≡k+t(t+1) (mod n)
  这里，可以得到一个后序序列完全平方与连续两个整数积的关联关系:
  设n=4k-1, n>=10, 如果有 (2k-m)^2≡j^2 (mod n)  m>=1  j>=1, 有如下的计算:
   (2k-j)^2≡k+j(j-1) (mod n)  根据a^2≡b (mod n) b-a, 可得:
    k+j(j-1)-(2k-))≡-k+j^2  =>
         -k+(2k-m)^2≡-k+k+m(m-1)≡m(m-1) (mod n)
   例3: n=319=4*80-1
     3k=3*80=240=15*16  => (160-16)^2≡1(mod 319) =>144^2≡1^2 (mod 319) => 160^2≡80(mod 319)  =>
  160^2+160-240≡0 (mod 319) => (160+16)(160-15)≡0 (mod 319)  

   上述中的j与费马分解得关联关系如下：
   费马分解: 设 n=ab  t=(a+b)/2  s=(a-b)/2  则  t^2≡s^2(mod n)
   t/2-s=j 即： (t/2-s)^2+3k-1=m(m-1)
                      (t/2+s)^2+3k-1=g(g-1)
   例4: 319=29*11  t=(29+11)/2=20  s=(29-11)/2=9   所以  20^2≡=9^2 (mod 319)
   20/2-9=1  即  144^2≡1^2 (mod 319)
   (20/2+9)^2+3*80-1  = 600=24*25
   (20/2-9)^2+3*80-1  = 240=14*15

  对于3k值，本人有一个算法，因极其不成熟，这里就不再给出，以上仅为本人的一点想法，还存在不足，欢迎大家批评指正。