数学建模社区-数学中国

标题: 二次剩余值的关联计算(上) [打印本页]
作者: songls    时间: 2023-11-15 20:10
标题: 二次剩余值的关联计算(上)
        二次剩余值的关联计算(上)( i5 d7 l0 m) s) K
! I$ _8 y( P* t; z. C1 _
一、 二次剩余中\frac{1}{2} 相关值的计算：; R9 `7 k1 @* n: i* y1 ?6 C
   对于完全平方公式：; t& n+ J( Z8 [3 G* S
   (1/2 -m)^2  = 1/4 -m+m^2 = 1/4 +m(m-1)   (m≥1)  (1-1)
& L9 d, G2 P) |8 l, `8 s8 G1 d, Q! E9 m4 j
    在n为奇数时, 上式的同余可以分为:* e: J( B" S# G' Q! T9 D$ Q4 @7 H% Z
    ① 当n=4k-1时，对(1-1)求同余得: * F; _$ r, t# k9 i
    (1/2-m)^2  ≡ (2k-m)^2 ≡ k+m(m-1) (mod n)    (1-2)2 X9 {2 N* s5 V6 k1 z3 [5 K
    ② 当n=4k+1时, 对(1-1)求同余得:
* h  w6 U: e* O    (1/2 -m)^2  ≡ (2k+1-m)^2 ≡ -k+m(m-1) ≡ n-k+m(m-1) (mod n)    (1-3)5 g' i: N8 r- V# k% F" o/ f  y

4 v& |# V7 g) b# r3 W; D4 y4 j% g  为以后叙述方便，我们对 1/2-1  1/2-2  ...  1/2-m (m >=1)  这类数称为二次剩余的后序序列, 即1/2  减小的方向的数列.& b& v6 u5 p' B2 Y8 N2 Y) [

- [3 ]. K6 F2 w* K  `  二次剩余后序序列的二次剩余值有个特点, 与k(k>0)值相关, 是k值与两个连续整数积的和，与k值同奇同偶。
. }8 _% w% d5 R) w  如n=299=4*75-1    k=75    2k=150 , 二次剩余后序序列为:+ l# b( }3 O% J0 T$ P
   (150-1)^2 ≡ 75+1*(1-1) ≡ 75 +0 ≡ 75 (mod 299)  =>  149^2 ≡ 75 (mod 299)  * G/ i& o" ~2 Z3 _# H& w2 v# i
   (150-2)^2 ≡ 75+2*(2-1) ≡ 75 +2 ≡ 77 (mod 299)  =>  148^2 ≡ 77 (mod 299)  7 D) v! f' b% |
   (150-3)^2 ≡ 75+3*(3-1) ≡ 75 +6 ≡ 81 (mod 299)  =>  147^2 ≡ 81 (mod 299) ! }' C1 x. |. A) A+ a. j3 ?. A

1 b6 ^( Y* z+ r3 I( t0 |  .! {# M* t7 _7 T8 C0 q% Y  g* ?7 r
  .6 B5 T1 T& V& V4 M! @
   根据后序序列，可以得到一个分解整数的方法:+ \& N7 t' o9 f% V) q2 ?. g$ e
   设n为奇合数, 如果 c^2-k=m(m-1)  m>0  => (2k-m)^2 ≡ c^2 (mod n)  , 或者 + h1 G, A  v& r" N  ~: V+ v
    c^2-k=m(m-1) => 4c^2-4k+1=4m(m-1)+1 => (2c)^2 ≡ (2m-1)^2 (mod n)  , ^  r  f1 l4 Q, ~  k' U: C" j2 v
   上述等式，由费马分解即可得到n的因子, 不过效率较低.' u( D4 B6 J' [0 |0 c# V8 F
    例1: n=299-4*75-1 ,  k=75+ A8 H& m, t3 Z2 u: u" G4 r
      根据后序序列，大于75且与75同奇同偶的完全平方：9^2-812 l' R! R. ~+ B9 D' U, d+ a: f! L* a
      81-75=6=2*3 为连续两个整数积，在后序序列上, f  |( k  w% y, O
      ∴ (150-3)^2≡81 (mod 299)  => 147^2≡81 (mod 299)# S2 ?7 v* m/ U, j
      或者 (2*9)^2≡(2*2+1)^2 (mod 299) => 18^2≡5^2(mod 299)! ~; L# ~2 ]( \* m" @1 m# E
0 ]- y% q2 E5 _) d( H1 }1 w
二、连续两个整数积的分解方法
  R3 X  ]7 k. ]( N   1、分解方法介绍8 I  a- K6 g( P; o" W$ W
   例2: n=299=4*75-16 O- k) f7 G. y/ t9 w# W2 i) z
      25^2 ≡ 27 (mod 299)   =>
8 C5 q/ D/ J+ r4 q' c' Z7 i3 p8 i     25^2 ≡ 25+2 (mod 299)  =>  
/ Z, R) I. N3 p1 N) b3 ?     25^2-25-2 ≡ 0 (mod 299) =>  
& g. M4 [; r/ W% J     (25-2)(25+1) ≡ 0 (mod 299) =>
$ o1 ^( G, T! w/ X2 H# p4 ^0 Z/ ?' N     23*26 ≡ 0 (mod 299)   + I  A8 w& ]; z/ y$ v) g
     (23,299)=23   (26,299)=13      299=13*23" S- ]. m2 Z2 j" \- Q& ^$ s

5 h% b! I7 P, m: J   分解方法:  设n为奇合数,  a^2 ≡ b (mod n)  , 如果 b=a+i(i+1) (i ≥ 0 )  , 则可得到:+ d5 j4 t- W9 h' @: |" V1 \
      a^2 ≡ b (mod n)  => 2 T9 f+ ^! p3 Q: Y5 s: J, P  O+ c+ j
     a^2-b-i(i+1) ≡ 0 (mod n)  =>
: R) {% n& h- n  N' H6 `" R8 j     (a-(i+1))(a+i) ≡ 0 (mod n) ' t( z" h( m$ u" p/ }1 f
     (a-(i+1),n)>1   (a+i , n)>1    即可分解n
9 a* @' j) F4 q9 h9 Q) k+ o; A
2 ?# N, s- P- _; D   2、分解方法的另一个解释 " K+ J5 s* c$ s- ?
    设n为奇数, a^2 ≡ b(mod n),  如果m=a, 则由(1-1)公式得: / g( s$ W. V" g$ j: S
     (1/2 -a)^2  ≡ 1/4 +a^2-a (mod n)   =>
0 V# l6 ]2 [- r" z       (1/2 -a)^2  ≡ 1/4 +b-a (mod n)    (2-1)
) ]+ U8 g$ t. i/ v3 \     : ~7 F3 O. }0 z( s
     ① n=4k-1 , 2-1式得：  B6 h0 f* b( H7 Q* k  D' g
     (2k-a)^2 ≡ k+b-a(mod n)     (2-2)
* H6 b/ G* I  _/ ?3 q+ q     ① n=4k+1 , 2-1式得：
$ {( P# V- @6 d$ u. y     (2k+1-a)^2 ≡ n-k+b-a (mod n)   (2-3)
( B1 z# B- l7 B" n" T) Q& g
5 e4 ?2 W' Y$ s. W% V4 U4 r7 p# e   从(2-1(式, 可知二次剩余的计算,  在[1,1/4]范围内, 计算出[1,n-1]的二次剩余值. 5 M- e) i9 ?7 j; Z2 P
   在例2中, 按(2-2)式的计算, 可得:
0 X" C+ U; U" N, V( {, f    (150-25)^2 ≡ 75+27-25 (mod 299) =>  125^2 ≡ 77 (mod 299)  
& _  t# \+ O% m+ s$ l    所以, a^2 ≡ b (mod n)  ，如果b=a+i(i+1) ,其相对1/2的剩余值在后序序列上.! M. `3 i5 }! e0 T
7 B" I$ E3 P: a7 L4 |
三、1/j (j >=3)的计算方法 * G4 l  k* L4 z* L
  上面的是计算 1/2， 即j=2, 如果j>2时,  有如下的1/j计算方法:; [* N9 Y# k( W8 C( D$ b
   (1/j ± ij)^2 = (ij)^2 ± 2i + (1/j)^2 (i >= 1 ) (j ≥3)   (3-1)
) ?$ }& I; o3 \2 J+ E$ m0 ]5 b0 l* i$ b: m, `9 h6 _5 M: j* ~
   而对于\frac{1}{j}相邻, 有两种计算,
  c$ @4 ?2 q  d" _3 v* C! ?& Q0 p    1)  1/j    1+1/j  2+1/j ... t+1/j    (t<j)  
1 L0 \( K; p2 y( Z/ x- x9 q    2) t-1/j ... 1-1/j  1/j  1+1/j ...  t+1/j   (t < j/2)  
' J+ k$ H6 r) M% K' ~  ?    t+1/j= (1+tj)/j = m/j ,  m=1+tj
# _6 D. v3 {5 g/ Q; p- d4 w7 s7 C; g* h6 t
    按m/j , (3-1)式变成: ( @9 Z9 K* X. A3 o* t3 _8 L
    (m/j± ij )^2 = (ij)^2 ± 2mi + (m/j )^2  (i≥ 1 ) (j ≥ 3)   (3-2)- _( h& Y  }6 o" b7 R. d
: y0 r3 U- L) e
   例3: n=299    \frac{1}{3} ≡ 100 (mod 299)   100^2 ≡ 133 (mod 299)  
: Z# n2 ^& t4 B) a   (100-3)^2 ≡ 3^2-2+133  (mod 299)    =>  97^2 ≡ 140  (mod 299)
6 ?2 s' Z. Q2 ]0 {$ i' p! @   (100+3)^2 ≡ 3^2+2+133  (mod 299)    =>  103^2 ≡ 144  (mod 299)3 h4 ^7 s/ t% q1 i1 V
   1+1/3=4/3 ≡ 1+100=101 (mod 299)     101^2 ≡ 35 (mod 299), R; s  x3 O' C5 b% w
   (101-3)^2 ≡ 3^2-2*4+35  (mod 299)    =>  98^2 ≡ 36  (mod 299) # D4 Q; d( ?8 w- l
   (101+3)^2 ≡ 3^2+2*4+35  (mod 299)    =>  104^2 ≡ 52  (mod 299) 5 w, o$ m# G- M9 Q
   1-1/3=-2/3 ≡ 1-100=-99 (mod 299)     99^2 ≡ 233 (mod 299)  4 _; e3 U. N, e! i
   (99-3)^2 ≡ 3^2-2*(-2)+233  (mod 299)    =>  96^2 ≡ 246  (mod 299)
4 X# m3 u' P- J2 s0 u$ T   (101+3)^2 ≡ 3^2+2*(-2)+233  (mod 299)    =>  102^2 ≡ 238  (mod 299)   
! k# m  W5 @+ n! b+ i   按2+1/3也能得到相同结果，这里不在验证.
! I3 L9 m# v# ?4 N4 [+ k9 O* ]5 \( S( h
   当然如果j=2s, 即为偶数, 可以计算一半的值, (3-2)式得  :
( o8 v( a+ }3 F% S: g0 g" G1 v    (m/j ± i*s)^2=(is)^2±mi+(m/j)^2   (i ≥ 1)   (j ≥ 3)   (3-3) * Y4 s  Z& e6 Z% z4 @/ G
  更一般的公式: 当为 g/j    g <j/2  , (g, j)=1, 这里就不再给出.
& T* {. \, ^3 f) n; J
7 Y2 ?# E  k0 ]; b# \9 X9 M

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

52.4 KB, 下载次数: 0, 下载积分: 体力 -2 点



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5