数学建模社区-数学中国

标题: 二次剩余值的关联计算(上) [打印本页]

作者: songls    时间: 2023-11-15 20:10
标题: 二次剩余值的关联计算(上)
        二次剩余值的关联计算(上)
9 s6 @. K: X' p5 [. a, i
$ [8 @8 U7 }+ P  @ 一、 二次剩余中\frac{1}{2} 相关值的计算:
3 h) g+ A8 [7 l. |- {   对于完全平方公式:
. d7 G! F: e  _   (1/2 -m)^2  = 1/4 -m+m^2 = 1/4 +m(m-1)   (m≥1)  (1-1)" _: V* ~; m% k/ y3 ]4 a4 y) R
5 |) S/ n4 s, k7 d7 b" H! l- I
    在n为奇数时, 上式的同余可以分为:5 s% n# v  @+ |1 ]6 M
    ① 当n=4k-1时,对(1-1)求同余得:
9 i+ C4 B) `/ w+ Z, u- \$ ^    (1/2-m)^2  ≡ (2k-m)^2 ≡ k+m(m-1) (mod n)    (1-2)7 e" s9 t& s0 j3 ]/ s( ^( k  }+ y
    ② 当n=4k+1时, 对(1-1)求同余得:
. L1 K* {  V% [/ ]" p, n, |    (1/2 -m)^2  ≡ (2k+1-m)^2 ≡ -k+m(m-1) ≡ n-k+m(m-1) (mod n)    (1-3)
2 V: T$ O' V+ {  Q+ \+ M7 a4 \! s8 I* [0 q: C3 n+ N, @2 z( @& T/ ]
  为以后叙述方便,我们对 1/2-1  1/2-2  ...  1/2-m (m >=1)  这类数称为二次剩余的后序序列, 即1/2  减小的方向的数列.
+ y9 I+ F: k% p& ?, e/ i
- h# }6 T! ]" ?0 P+ L4 Q/ ~' Y  二次剩余后序序列的二次剩余值有个特点, 与k(k>0)值相关, 是k值与两个连续整数积的和,与k值同奇同偶。
6 B9 C# S' l/ O$ A0 x) G  如n=299=4*75-1    k=75    2k=150 , 二次剩余后序序列为:4 w  u, q+ P% f+ O8 J9 u
   (150-1)^2 ≡ 75+1*(1-1) ≡ 75 +0 ≡ 75 (mod 299)  =>  149^2 ≡ 75 (mod 299)  / h9 A: f0 r# w2 y
   (150-2)^2 ≡ 75+2*(2-1) ≡ 75 +2 ≡ 77 (mod 299)  =>  148^2 ≡ 77 (mod 299)  . p5 X+ M) _: y  P
   (150-3)^2 ≡ 75+3*(3-1) ≡ 75 +6 ≡ 81 (mod 299)  =>  147^2 ≡ 81 (mod 299)
9 K' e: ]# x6 r' y5 B$ O' [! f3 i0 W; O& A2 j! q
  .
6 w4 S; A- u/ |; ^) ~, x" r$ ?) m5 [  .% G6 K" x* p. n3 ]
   根据后序序列,可以得到一个分解整数的方法:
, E( i# A) d& r   设n为奇合数, 如果 c^2-k=m(m-1)  m>0  => (2k-m)^2 ≡ c^2 (mod n)  , 或者 : N' @3 A/ a1 j7 r6 g
    c^2-k=m(m-1) => 4c^2-4k+1=4m(m-1)+1 => (2c)^2 ≡ (2m-1)^2 (mod n)  
) I" y0 e0 ?# h   上述等式,由费马分解即可得到n的因子, 不过效率较低.6 I4 [7 f: l" B+ K
    例1: n=299-4*75-1 ,  k=75
( J2 Q+ x" H$ x7 I- x* W      根据后序序列,大于75且与75同奇同偶的完全平方:9^2-81$ k( |/ H& i) ?4 D5 \% n
      81-75=6=2*3 为连续两个整数积,在后序序列上: y  x+ ]; U( s/ G0 D" z
      ∴ (150-3)^2≡81 (mod 299)  => 147^2≡81 (mod 299)5 @% Y, I4 i$ H5 x9 ?* F
      或者 (2*9)^2≡(2*2+1)^2 (mod 299) => 18^2≡5^2(mod 299)
' A" ~" g% z8 {1 |4 L
' Q' K: _8 _) [" n5 e) B6 z 二、连续两个整数积的分解方法
/ l4 ^0 H- I5 q0 O4 ~6 x   1、分解方法介绍
$ [7 E9 v8 i$ b9 |- @2 H   例2: n=299=4*75-1
- d" N- ]8 y; u- u" B      25^2 ≡ 27 (mod 299)   => 5 g4 ^, O. W2 s
     25^2 ≡ 25+2 (mod 299)  =>  
; v2 ?9 V! }5 m( Q2 ?  M/ {# {6 _     25^2-25-2 ≡ 0 (mod 299) =>  # T' r4 c$ m5 y& R& c
     (25-2)(25+1) ≡ 0 (mod 299) => " W) z# Z+ z4 k
     23*26 ≡ 0 (mod 299)   ) {( L" \2 K5 i$ Q
     (23,299)=23   (26,299)=13      299=13*23
4 f6 f8 y2 p/ a$ a/ b1 {3 r' H8 {0 A3 [8 ?3 j3 ]
   分解方法:  设n为奇合数,  a^2 ≡ b (mod n)  , 如果 b=a+i(i+1) (i ≥ 0 )  , 则可得到:
. U; M: Y; w( Y      a^2 ≡ b (mod n)  => 6 t6 E! b' w( k& P# r: b
     a^2-b-i(i+1) ≡ 0 (mod n)  => * k8 I, B- w: S+ \
     (a-(i+1))(a+i) ≡ 0 (mod n) 6 |0 I9 k0 X5 r0 q8 }
     (a-(i+1),n)>1   (a+i , n)>1    即可分解n- G# z' p  n, s  D0 I

6 U( m2 X9 c1 @* u   2、分解方法的另一个解释
# P8 ~. A5 T5 C3 M, Y    设n为奇数, a^2 ≡ b(mod n),  如果m=a, 则由(1-1)公式得:
) _0 ~% i* R! ~6 }2 H( f$ _2 t     (1/2 -a)^2  ≡ 1/4 +a^2-a (mod n)   => : W( B  C, M4 }6 d1 j3 Y6 A& c
       (1/2 -a)^2  ≡ 1/4 +b-a (mod n)    (2-1)
! |5 K  j; p- f+ W1 M' r     
( N; {/ W) K# e% L) W1 \# s+ B     ① n=4k-1 , 2-1式得:- B) B6 z: f0 Q* r# q0 d! u5 ~
     (2k-a)^2 ≡ k+b-a(mod n)     (2-2)
0 d+ S7 g! H" G1 i% s% i     ① n=4k+1 , 2-1式得:2 _( P3 b: \& v' V4 Y( A
     (2k+1-a)^2 ≡ n-k+b-a (mod n)   (2-3)& ]/ {" I" k3 e( Z+ S
+ U4 I7 M2 d9 S- T: n* R
   从(2-1(式, 可知二次剩余的计算,  在[1,1/4]范围内, 计算出[1,n-1]的二次剩余值.
# M5 Q+ a+ @5 a& f9 H2 Q1 Q3 E, p3 [' e   在例2中, 按(2-2)式的计算, 可得: , C9 b9 ^7 B, r/ b
    (150-25)^2 ≡ 75+27-25 (mod 299) =>  125^2 ≡ 77 (mod 299)  
& u* e: @; H5 B3 @# {    所以, a^2 ≡ b (mod n)  ,如果b=a+i(i+1) ,其相对1/2的剩余值在后序序列上.# ~9 C: b. _: c) G

0 i$ N; u% B$ ~1 ^6 L4 S5 `, g 三、1/j (j >=3)的计算方法
+ \  {  i/ X. F  上面的是计算 1/2, 即j=2, 如果j>2时,  有如下的1/j计算方法:
) O+ _- [5 K3 S, k   (1/j ± ij)^2 = (ij)^2 ± 2i + (1/j)^2 (i >= 1 ) (j ≥3)   (3-1)
+ y3 o! x6 F: n, a- V8 V5 ]
( ?5 ~9 p5 K+ L/ e: ?   而对于\frac{1}{j}相邻, 有两种计算,
5 |- S% n" U, t# q+ r! L    1)  1/j    1+1/j  2+1/j ... t+1/j    (t<j)  
6 O' k9 @0 w3 t3 u# G( X    2) t-1/j ... 1-1/j  1/j  1+1/j ...  t+1/j   (t < j/2)  3 d- y) a/ c8 T! Z) F
    t+1/j= (1+tj)/j = m/j ,  m=1+tj
/ `; `# o: r5 m4 Q  Y7 }" t" [8 `
    按m/j , (3-1)式变成:
# ?- Q9 b8 j, z" A6 J) H! u    (m/j± ij )^2 = (ij)^2 ± 2mi + (m/j )^2  (i≥ 1 ) (j ≥ 3)   (3-2)
( B7 T" X5 b' g# u9 R8 W8 `' b, ?6 h# z8 D2 ]6 q( f' H: B5 ^
   例3: n=299    \frac{1}{3} ≡ 100 (mod 299)   100^2 ≡ 133 (mod 299)  
0 J6 I& H) |" o/ |7 j3 h   (100-3)^2 ≡ 3^2-2+133  (mod 299)    =>  97^2 ≡ 140  (mod 299)
8 h+ |0 U4 x: {  R7 D   (100+3)^2 ≡ 3^2+2+133  (mod 299)    =>  103^2 ≡ 144  (mod 299)
+ g) \9 Q# A7 m( f   1+1/3=4/3 ≡ 1+100=101 (mod 299)     101^2 ≡ 35 (mod 299)0 B' M4 N$ H  M% y) o
   (101-3)^2 ≡ 3^2-2*4+35  (mod 299)    =>  98^2 ≡ 36  (mod 299) ' ^6 x2 r  h& V* w+ M
   (101+3)^2 ≡ 3^2+2*4+35  (mod 299)    =>  104^2 ≡ 52  (mod 299) " D$ H" P' ~8 B
   1-1/3=-2/3 ≡ 1-100=-99 (mod 299)     99^2 ≡ 233 (mod 299)  * ]3 b6 y. g  ?4 x" q# T5 j7 `
   (99-3)^2 ≡ 3^2-2*(-2)+233  (mod 299)    =>  96^2 ≡ 246  (mod 299) ! Z8 Z8 o+ F- H/ `+ {2 j* G
   (101+3)^2 ≡ 3^2+2*(-2)+233  (mod 299)    =>  102^2 ≡ 238  (mod 299)   8 u# ?4 N( @+ ]2 {$ p
   按2+1/3也能得到相同结果,这里不在验证.
- `7 w& Q/ ?6 g- c  x8 f# g; e6 H* a5 K. N2 D0 \5 Q! U. h
   当然如果j=2s, 即为偶数, 可以计算一半的值, (3-2)式得  :   z& C" o8 q$ b
    (m/j ± i*s)^2=(is)^2±mi+(m/j)^2   (i ≥ 1)   (j ≥ 3)   (3-3)
* q) \: b9 \8 T  更一般的公式: 当为 g/j    g <j/2  , (g, j)=1, 这里就不再给出.
# |8 b& ~6 U8 |% q1 I
: i9 n1 Q, x, Z6 k

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

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






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