二次剩余值的关联计算(上)

songls

        二次剩余值的关联计算(上)
2 ]5 g( G& M; V+ h5 p
4 X2 S3 x% N2 E2 ^2 `  { 一、 二次剩余中\frac{1}{2} 相关值的计算：
   对于完全平方公式：
5 F& H. u; W4 \8 s$ ^) H   (1/2 -m)^2  = 1/4 -m+m^2 = 1/4 +m(m-1)   (m≥1)  (1-1)

    在n为奇数时, 上式的同余可以分为:
    ① 当n=4k-1时，对(1-1)求同余得:
6 E3 a2 W* y/ g& d4 c8 F. l3 b    (1/2-m)^2  ≡ (2k-m)^2 ≡ k+m(m-1) (mod n)    (1-2)
* E; [9 Z" _/ T/ W7 L* K    ② 当n=4k+1时, 对(1-1)求同余得:
    (1/2 -m)^2  ≡ (2k+1-m)^2 ≡ -k+m(m-1) ≡ n-k+m(m-1) (mod n)    (1-3)

+ K1 m; K5 {. u7 ~0 K' z8 W& y# ]  为以后叙述方便，我们对 1/2-1  1/2-2  ...  1/2-m (m >=1)  这类数称为二次剩余的后序序列, 即1/2  减小的方向的数列.

  二次剩余后序序列的二次剩余值有个特点, 与k(k>0)值相关, 是k值与两个连续整数积的和，与k值同奇同偶。
6 i+ ]9 R  z5 w+ N- W* N  如n=299=4*75-1    k=75    2k=150 , 二次剩余后序序列为:
' i# @; O9 c. |1 i% n   (150-1)^2 ≡ 75+1*(1-1) ≡ 75 +0 ≡ 75 (mod 299)  =>  149^2 ≡ 75 (mod 299)  
% ^, a$ n5 e% R/ j, `   (150-2)^2 ≡ 75+2*(2-1) ≡ 75 +2 ≡ 77 (mod 299)  =>  148^2 ≡ 77 (mod 299)  
4 @8 n0 a4 w, b+ I' d* t; K  u, k   (150-3)^2 ≡ 75+3*(3-1) ≡ 75 +6 ≡ 81 (mod 299)  =>  147^2 ≡ 81 (mod 299)
. `" h0 r* t2 P2 C2 i
1 g; L9 n3 x7 P7 w  |  .
  .
   根据后序序列，可以得到一个分解整数的方法:
$ k5 }* p+ j: Z# J; P" a; h% [, X# R   设n为奇合数, 如果 c^2-k=m(m-1)  m>0  => (2k-m)^2 ≡ c^2 (mod n)  , 或者
8 j2 @2 w( B0 U2 G. g    c^2-k=m(m-1) => 4c^2-4k+1=4m(m-1)+1 => (2c)^2 ≡ (2m-1)^2 (mod n)  
   上述等式，由费马分解即可得到n的因子, 不过效率较低.
    例1: n=299-4*75-1 ,  k=75
      根据后序序列，大于75且与75同奇同偶的完全平方：9^2-81
      81-75=6=2*3 为连续两个整数积，在后序序列上
      ∴ (150-3)^2≡81 (mod 299)  => 147^2≡81 (mod 299)
      或者 (2*9)^2≡(2*2+1)^2 (mod 299) => 18^2≡5^2(mod 299)
1 V& [' P6 b. h& h7 n- y: w" j
二、连续两个整数积的分解方法
   1、分解方法介绍
   例2: n=299=4*75-1
2 t5 m/ W7 ^3 K6 e+ o" v      25^2 ≡ 27 (mod 299)   =>
' I2 Q9 W0 s9 U7 m: Q     25^2 ≡ 25+2 (mod 299)  =>  
     25^2-25-2 ≡ 0 (mod 299) =>  
     (25-2)(25+1) ≡ 0 (mod 299) =>
0 I6 k  M4 o& _+ [, K, Y     23*26 ≡ 0 (mod 299)   
     (23,299)=23   (26,299)=13      299=13*23
1 ?& M" [& Q6 a; G0 @
   分解方法:  设n为奇合数,  a^2 ≡ b (mod n)  , 如果 b=a+i(i+1) (i ≥ 0 )  , 则可得到:
% \. G4 O* u8 z( e) \      a^2 ≡ b (mod n)  =>
     a^2-b-i(i+1) ≡ 0 (mod n)  =>
- D" d6 Q  x1 ~! E  Z+ J( m     (a-(i+1))(a+i) ≡ 0 (mod n)
4 w$ s, a$ k3 Q! Q  \     (a-(i+1),n)>1   (a+i , n)>1    即可分解n
- Z" N5 ]/ Z/ w, s5 y# |# r+ n# }
* E4 z3 g6 f: L) L- H9 V. S1 M/ Q   2、分解方法的另一个解释
( h" ]* \* e8 `! u+ ^    设n为奇数, a^2 ≡ b(mod n),  如果m=a, 则由(1-1)公式得:
% ]. h* v: K" L2 \7 g/ b     (1/2 -a)^2  ≡ 1/4 +a^2-a (mod n)   =>
       (1/2 -a)^2  ≡ 1/4 +b-a (mod n)    (2-1)
     
     ① n=4k-1 , 2-1式得：
: L% d- _3 H. Q6 M; L/ }     (2k-a)^2 ≡ k+b-a(mod n)     (2-2)
, e' s* m7 m$ ^7 g1 P     ① n=4k+1 , 2-1式得：
% f: ~9 J# ?8 A  }2 ]2 u     (2k+1-a)^2 ≡ n-k+b-a (mod n)   (2-3)

0 p0 o) b6 {4 q' t% R: P0 a4 y8 h3 A   从(2-1(式, 可知二次剩余的计算,  在[1,1/4]范围内, 计算出[1,n-1]的二次剩余值.
   在例2中, 按(2-2)式的计算, 可得:
    (150-25)^2 ≡ 75+27-25 (mod 299) =>  125^2 ≡ 77 (mod 299)  
" ]0 f" ^, [; z9 `5 O# B8 D" b0 c9 S    所以, a^2 ≡ b (mod n)  ，如果b=a+i(i+1) ,其相对1/2的剩余值在后序序列上.

0 S- z: x0 Z' X( P8 [# j 三、1/j (j >=3)的计算方法
" |4 a- c+ c5 X1 I+ C# I  上面的是计算 1/2， 即j=2, 如果j>2时,  有如下的1/j计算方法:
   (1/j ± ij)^2 = (ij)^2 ± 2i + (1/j)^2 (i >= 1 ) (j ≥3)   (3-1)

+ B7 t; n" m, q; U2 M+ @- z" ?9 I+ @$ U   而对于\frac{1}{j}相邻, 有两种计算,
7 l6 ?" A2 w+ t6 E" A/ Q3 x    1)  1/j    1+1/j  2+1/j ... t+1/j    (t<j)  
/ ^( }% e. {9 p! g8 j    2) t-1/j ... 1-1/j  1/j  1+1/j ...  t+1/j   (t < j/2)  
    t+1/j= (1+tj)/j = m/j ,  m=1+tj
3 k0 G- z) q2 _7 D
+ m5 a' Y. b. P8 ~4 P* J2 m7 ]    按m/j , (3-1)式变成:
& I2 u( G" e" Y9 h  f    (m/j± ij )^2 = (ij)^2 ± 2mi + (m/j )^2  (i≥ 1 ) (j ≥ 3)   (3-2)
1 }: ~: D  ~. K9 n% M" l0 \
* Z8 B. X1 C1 P! `; X3 O   例3: n=299    \frac{1}{3} ≡ 100 (mod 299)   100^2 ≡ 133 (mod 299)  
   (100-3)^2 ≡ 3^2-2+133  (mod 299)    =>  97^2 ≡ 140  (mod 299)
8 g8 e6 U$ X7 k0 B8 L   (100+3)^2 ≡ 3^2+2+133  (mod 299)    =>  103^2 ≡ 144  (mod 299)
0 n7 t) l0 ]( H: w   1+1/3=4/3 ≡ 1+100=101 (mod 299)     101^2 ≡ 35 (mod 299)
6 d: |3 T* A* z$ d8 s   (101-3)^2 ≡ 3^2-2*4+35  (mod 299)    =>  98^2 ≡ 36  (mod 299)
/ ?- f! C) i0 u8 j2 m1 l' _   (101+3)^2 ≡ 3^2+2*4+35  (mod 299)    =>  104^2 ≡ 52  (mod 299)
* H2 v0 m+ B6 o4 M( O( i   1-1/3=-2/3 ≡ 1-100=-99 (mod 299)     99^2 ≡ 233 (mod 299)  
   (99-3)^2 ≡ 3^2-2*(-2)+233  (mod 299)    =>  96^2 ≡ 246  (mod 299)
   (101+3)^2 ≡ 3^2+2*(-2)+233  (mod 299)    =>  102^2 ≡ 238  (mod 299)   
   按2+1/3也能得到相同结果，这里不在验证.

3 n% b+ |! Q# u" {   当然如果j=2s, 即为偶数, 可以计算一半的值, (3-2)式得  :
6 Z4 q4 O2 n2 b! `# X, J6 j    (m/j ± i*s)^2=(is)^2±mi+(m/j)^2   (i ≥ 1)   (j ≥ 3)   (3-3)
$ |: c. Q5 J- b" ]  更一般的公式: 当为 g/j    g <j/2  , (g, j)=1, 这里就不再给出.