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

songls

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

一、 二次剩余中\frac{1}{2} 相关值的计算：
( B# ^* s3 x/ g& g+ E  P2 r/ o% Q+ {   对于完全平方公式：
* d$ w+ ]5 ]% ~6 q1 ]   (1/2 -m)^2  = 1/4 -m+m^2 = 1/4 +m(m-1)   (m≥1)  (1-1)
/ _, m. h( V& j' u6 G( E
; O& s+ W( T' X" j1 b$ a- V8 ~    在n为奇数时, 上式的同余可以分为:
. i$ l8 ^, y8 ~: A. ?* j    ① 当n=4k-1时，对(1-1)求同余得:
  [9 [9 T0 O; Y9 S+ K* k+ O7 k    (1/2-m)^2  ≡ (2k-m)^2 ≡ k+m(m-1) (mod n)    (1-2)
$ l: v: R+ H8 c' s, V, v    ② 当n=4k+1时, 对(1-1)求同余得:
# u* T) [: B, U' ?3 a    (1/2 -m)^2  ≡ (2k+1-m)^2 ≡ -k+m(m-1) ≡ n-k+m(m-1) (mod n)    (1-3)
  c/ ^# ?7 a1 D; s# j" G
) I5 l9 j/ T1 I- U3 h2 g  为以后叙述方便，我们对 1/2-1  1/2-2  ...  1/2-m (m >=1)  这类数称为二次剩余的后序序列, 即1/2  减小的方向的数列.
& \4 Z7 r& i1 s- i1 d5 A. d
  二次剩余后序序列的二次剩余值有个特点, 与k(k>0)值相关, 是k值与两个连续整数积的和，与k值同奇同偶。
5 N3 T2 Z: c; U2 k, ~9 s  如n=299=4*75-1    k=75    2k=150 , 二次剩余后序序列为:
5 Z) V' p( d& h! Y* F& P  v   (150-1)^2 ≡ 75+1*(1-1) ≡ 75 +0 ≡ 75 (mod 299)  =>  149^2 ≡ 75 (mod 299)  
   (150-2)^2 ≡ 75+2*(2-1) ≡ 75 +2 ≡ 77 (mod 299)  =>  148^2 ≡ 77 (mod 299)  
5 ~  z- i7 l  x( C' M   (150-3)^2 ≡ 75+3*(3-1) ≡ 75 +6 ≡ 81 (mod 299)  =>  147^2 ≡ 81 (mod 299)
+ a0 g# B8 h9 B  p% C; t% Z
" v  j; y) Y. [4 m. b% P( ]  .
  .
" r  o& Z' A. b7 }3 L# j   根据后序序列，可以得到一个分解整数的方法:
& u5 b$ i& E, I$ q" L   设n为奇合数, 如果 c^2-k=m(m-1)  m>0  => (2k-m)^2 ≡ c^2 (mod n)  , 或者
# G/ |( n' ^3 Z6 V! Y$ c    c^2-k=m(m-1) => 4c^2-4k+1=4m(m-1)+1 => (2c)^2 ≡ (2m-1)^2 (mod n)  
   上述等式，由费马分解即可得到n的因子, 不过效率较低.
4 [* E8 x# ~3 F9 r) V) o* E    例1: n=299-4*75-1 ,  k=75
      根据后序序列，大于75且与75同奇同偶的完全平方：9^2-81
( `3 D- v  a9 F& c. N; t" [& ]) \      81-75=6=2*3 为连续两个整数积，在后序序列上
! V5 @# [2 ~% u5 Y9 y* P6 e6 _      ∴ (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、分解方法介绍
- v7 ^: \: t2 S& q   例2: n=299=4*75-1
      25^2 ≡ 27 (mod 299)   =>
     25^2 ≡ 25+2 (mod 299)  =>  
     25^2-25-2 ≡ 0 (mod 299) =>  
# O# i" F9 f4 Z* x5 J3 H9 d     (25-2)(25+1) ≡ 0 (mod 299) =>
     23*26 ≡ 0 (mod 299)   
9 O; A1 T: v/ d0 j$ E4 j     (23,299)=23   (26,299)=13      299=13*23
; Z5 Q7 f# ?. h, P
9 D6 N- h9 O' M8 _% J$ P! u! \   分解方法:  设n为奇合数,  a^2 ≡ b (mod n)  , 如果 b=a+i(i+1) (i ≥ 0 )  , 则可得到:
' F. m! k: p+ v9 a$ n( ]& `      a^2 ≡ b (mod n)  =>
     a^2-b-i(i+1) ≡ 0 (mod n)  =>
     (a-(i+1))(a+i) ≡ 0 (mod n)
     (a-(i+1),n)>1   (a+i , n)>1    即可分解n

   2、分解方法的另一个解释
    设n为奇数, a^2 ≡ b(mod n),  如果m=a, 则由(1-1)公式得:
: B9 d' @8 R" _- X( _     (1/2 -a)^2  ≡ 1/4 +a^2-a (mod n)   =>
       (1/2 -a)^2  ≡ 1/4 +b-a (mod n)    (2-1)
     
/ Z$ i6 d6 i2 I: k5 |) c     ① n=4k-1 , 2-1式得：
, Y$ A' R% j: M8 t& A0 Q4 S5 f     (2k-a)^2 ≡ k+b-a(mod n)     (2-2)
, z" b& a* ?" v- T( F. @( D; w     ① n=4k+1 , 2-1式得：
7 G) K8 ?# }* n# p     (2k+1-a)^2 ≡ n-k+b-a (mod n)   (2-3)
6 T. c* f. O) O
7 v) _1 j6 L5 l: J   从(2-1(式, 可知二次剩余的计算,  在[1,1/4]范围内, 计算出[1,n-1]的二次剩余值.
# g- u# g. j/ E9 {; n( ]   在例2中, 按(2-2)式的计算, 可得:
5 b. z. h# H7 U9 d/ v    (150-25)^2 ≡ 75+27-25 (mod 299) =>  125^2 ≡ 77 (mod 299)  
6 g" p2 O8 ~4 m/ X- e    所以, a^2 ≡ b (mod n)  ，如果b=a+i(i+1) ,其相对1/2的剩余值在后序序列上.
, N# ]; ?* _8 E, Q3 \! w7 v2 A
9 q- W) [+ }7 f6 S9 j* `6 O/ g 三、1/j (j >=3)的计算方法
( ~1 l  k# T4 \4 M1 k1 H  上面的是计算 1/2， 即j=2, 如果j>2时,  有如下的1/j计算方法:
/ D* ?, p, D- V* |  O. Y! t. f  F   (1/j ± ij)^2 = (ij)^2 ± 2i + (1/j)^2 (i >= 1 ) (j ≥3)   (3-1)
# w+ V! Z" D; L7 H* N) _7 c( o$ u
   而对于\frac{1}{j}相邻, 有两种计算,
) E' R# D4 j8 _1 S: A    1)  1/j    1+1/j  2+1/j ... t+1/j    (t<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
1 v9 [: c; \( y0 m  a3 j6 ^+ o
. w0 Y' N! I$ _1 l2 Z    按m/j , (3-1)式变成:
    (m/j± ij )^2 = (ij)^2 ± 2mi + (m/j )^2  (i≥ 1 ) (j ≥ 3)   (3-2)
! J6 C: W0 f8 Q/ q& g
   例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)
   (100+3)^2 ≡ 3^2+2+133  (mod 299)    =>  103^2 ≡ 144  (mod 299)
   1+1/3=4/3 ≡ 1+100=101 (mod 299)     101^2 ≡ 35 (mod 299)
8 [) o# {$ v( L4 L6 d7 A, {4 h   (101-3)^2 ≡ 3^2-2*4+35  (mod 299)    =>  98^2 ≡ 36  (mod 299)
   (101+3)^2 ≡ 3^2+2*4+35  (mod 299)    =>  104^2 ≡ 52  (mod 299)
   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)   
1 L( K. V+ c! O: C/ j   按2+1/3也能得到相同结果，这里不在验证.
" H2 N! r6 V* x: p" m
6 H5 X: u  o% M$ S5 e9 E7 d& [) H   当然如果j=2s, 即为偶数, 可以计算一半的值, (3-2)式得  :
' h# ]) [4 ?% b$ Z' M" e! z) m; M    (m/j ± i*s)^2=(is)^2±mi+(m/j)^2   (i ≥ 1)   (j ≥ 3)   (3-3)
8 N! v, Z$ q3 A- {2 ]" [; [  更一般的公式: 当为 g/j    g <j/2  , (g, j)=1, 这里就不再给出.
3 b4 I1 Q4 Z! _4 T' N' [" I3 G
# R) B( I; c! w% I; @& C' \