数学建模社区-数学中国

标题: 二次剩余值的关联计算(上) [打印本页]
作者: songls    时间: 2023-11-15 20:10
标题: 二次剩余值的关联计算(上)
        二次剩余值的关联计算(上)
+ t9 U1 W! w2 B& ^( g+ b) K1 m4 F, D* H3 N
一、 二次剩余中\frac{1}{2} 相关值的计算：
" P1 A' `: t6 B: m2 X5 i3 C# c" p* y* J   对于完全平方公式：) h& d/ W9 A2 _' u4 D. `' A
   (1/2 -m)^2  = 1/4 -m+m^2 = 1/4 +m(m-1)   (m≥1)  (1-1)& ]" d5 j) i6 R) {7 X$ Q
) a! D: M1 F( ?; D! l
    在n为奇数时, 上式的同余可以分为:
3 j; w1 Q, ]; z: z  ?1 W    ① 当n=4k-1时，对(1-1)求同余得:
. p) v( I- z4 }5 m2 |3 ]6 Q/ l    (1/2-m)^2  ≡ (2k-m)^2 ≡ k+m(m-1) (mod n)    (1-2)! Y" \3 F; G* R5 t: T# P' N( t
    ② 当n=4k+1时, 对(1-1)求同余得:
1 X# z+ l; ^, G) Z# {4 ?3 c    (1/2 -m)^2  ≡ (2k+1-m)^2 ≡ -k+m(m-1) ≡ n-k+m(m-1) (mod n)    (1-3), b3 ]# ~( m* {  Z7 g4 |

5 R& J: S6 x, J' G; ^  为以后叙述方便，我们对 1/2-1  1/2-2  ...  1/2-m (m >=1)  这类数称为二次剩余的后序序列, 即1/2  减小的方向的数列.+ T6 D8 J! q+ f/ s
- p  Q9 D  V6 h6 @
  二次剩余后序序列的二次剩余值有个特点, 与k(k>0)值相关, 是k值与两个连续整数积的和，与k值同奇同偶。
, H. l# O) B. E9 b2 v% `4 s  如n=299=4*75-1    k=75    2k=150 , 二次剩余后序序列为:
. d  ~# p5 n4 f" O+ O3 R7 |8 L   (150-1)^2 ≡ 75+1*(1-1) ≡ 75 +0 ≡ 75 (mod 299)  =>  149^2 ≡ 75 (mod 299)  
; _+ d! v0 Q' z- i# Y   (150-2)^2 ≡ 75+2*(2-1) ≡ 75 +2 ≡ 77 (mod 299)  =>  148^2 ≡ 77 (mod 299)  
: |) k/ {2 R% \& G- T6 E5 X   (150-3)^2 ≡ 75+3*(3-1) ≡ 75 +6 ≡ 81 (mod 299)  =>  147^2 ≡ 81 (mod 299)
. O4 D; |: [% Y) U2 g4 E8 J- U6 j9 a) ]- [( v- x$ Q  M* B
  .
5 |; ~) X4 L. r3 P9 V  .
( s' s/ j4 F; c/ n  q0 z; ~   根据后序序列，可以得到一个分解整数的方法:) o( {2 p4 b' t. Y/ Y
   设n为奇合数, 如果 c^2-k=m(m-1)  m>0  => (2k-m)^2 ≡ c^2 (mod n)  , 或者 4 l% K" f' A4 i/ h. L5 V: b% {
    c^2-k=m(m-1) => 4c^2-4k+1=4m(m-1)+1 => (2c)^2 ≡ (2m-1)^2 (mod n)  
6 p( y6 l; Z' r4 `8 h   上述等式，由费马分解即可得到n的因子, 不过效率较低.
  v' l7 ?, |( `    例1: n=299-4*75-1 ,  k=75* R. N4 r0 A. _, q% {! p
      根据后序序列，大于75且与75同奇同偶的完全平方：9^2-81
+ X4 B- j. @4 H) f      81-75=6=2*3 为连续两个整数积，在后序序列上* N3 r( f: B7 a8 m" o
      ∴ (150-3)^2≡81 (mod 299)  => 147^2≡81 (mod 299)6 S. a9 |7 |& k, ^
      或者 (2*9)^2≡(2*2+1)^2 (mod 299) => 18^2≡5^2(mod 299)2 G/ G  Z0 @/ J9 W) @1 ?: b) s
7 i4 ^; h/ @9 |9 X, P
二、连续两个整数积的分解方法
+ Z* _- \! O& l7 N% H- j% V3 f   1、分解方法介绍
  ]5 O  X9 Y8 a' V3 m$ ]$ M   例2: n=299=4*75-1
- G4 o# ^* g5 Y+ f9 U! O6 Q      25^2 ≡ 27 (mod 299)   => 4 q, X- W1 }2 M! J8 Y, d; \- O
     25^2 ≡ 25+2 (mod 299)  =>  " A  R4 V$ G5 L' `# ^
     25^2-25-2 ≡ 0 (mod 299) =>  
! z) c& d, y. i: R+ C$ d     (25-2)(25+1) ≡ 0 (mod 299) => 4 e/ w; w* ^, _4 ?4 S, y
     23*26 ≡ 0 (mod 299)   6 h$ v  T+ v3 X, F& @
     (23,299)=23   (26,299)=13      299=13*23- w' q4 U4 c" g8 k* L

3 {% r5 f% H5 d( Y) U# h   分解方法:  设n为奇合数,  a^2 ≡ b (mod n)  , 如果 b=a+i(i+1) (i ≥ 0 )  , 则可得到:
3 j( W* M3 \! k( I1 i6 e      a^2 ≡ b (mod n)  =>
, i& P7 x+ [+ F, \: O9 Q     a^2-b-i(i+1) ≡ 0 (mod n)  =>
" P# P: n" Q8 B8 Q     (a-(i+1))(a+i) ≡ 0 (mod n) / G0 {3 n& z: r" |- |% \- l5 }
     (a-(i+1),n)>1   (a+i , n)>1    即可分解n/ x, `4 ]$ ~+ }9 ~
' z) ?. t% ]' y3 z0 w% _
   2、分解方法的另一个解释 7 J. ?6 h# L- B4 {; D: V: E
    设n为奇数, a^2 ≡ b(mod n),  如果m=a, 则由(1-1)公式得: 3 [* E- a2 N6 i# @# a
     (1/2 -a)^2  ≡ 1/4 +a^2-a (mod n)   => 1 w5 b8 c, \+ T% \3 U* p2 T
       (1/2 -a)^2  ≡ 1/4 +b-a (mod n)    (2-1) - R* e2 R7 e; U* G
     9 B; n7 g2 A5 H5 ~* P
     ① n=4k-1 , 2-1式得：+ o# c, x* Z4 X4 A& E8 b) ~9 D; k' }
     (2k-a)^2 ≡ k+b-a(mod n)     (2-2): s: b$ [$ g4 E' p2 Z+ T1 `
     ① n=4k+1 , 2-1式得：* \$ ~3 R" \$ m$ x. ~
     (2k+1-a)^2 ≡ n-k+b-a (mod n)   (2-3)- G( q- H( j! P

) h) W. I: ^1 k* }2 {   从(2-1(式, 可知二次剩余的计算,  在[1,1/4]范围内, 计算出[1,n-1]的二次剩余值.
0 T# U6 N0 B1 h) N0 l+ [   在例2中, 按(2-2)式的计算, 可得: 4 `+ R! k( c" L& S* i0 f- c1 b
    (150-25)^2 ≡ 75+27-25 (mod 299) =>  125^2 ≡ 77 (mod 299)  . x! Z% L* @1 ~, z
    所以, a^2 ≡ b (mod n)  ，如果b=a+i(i+1) ,其相对1/2的剩余值在后序序列上.* f) E; m# a5 g

4 d6 D3 F. _- n1 i% C+ W) E 三、1/j (j >=3)的计算方法
( o9 Y( y& ^7 Q+ R, k( x6 g  `3 H! V  上面的是计算 1/2， 即j=2, 如果j>2时,  有如下的1/j计算方法:3 Q2 r2 K" H+ T! Q
   (1/j ± ij)^2 = (ij)^2 ± 2i + (1/j)^2 (i >= 1 ) (j ≥3)   (3-1)5 P3 s7 _9 v5 L; Q0 r
: l; y7 c9 Q6 r7 ?- f& K7 n1 _$ r
   而对于\frac{1}{j}相邻, 有两种计算,
( b( A2 W; Q4 ^' l' V9 f, m! m    1)  1/j    1+1/j  2+1/j ... t+1/j    (t<j)    B1 p0 T2 J0 T% G. ?* `. S. @6 {
    2) t-1/j ... 1-1/j  1/j  1+1/j ...  t+1/j   (t < j/2)  
+ a: X6 y3 d; `, k( T  B  P    t+1/j= (1+tj)/j = m/j ,  m=1+tj) T3 _" i/ y$ s' K/ B& z, `
4 R7 L0 G# H7 r, M1 ^( s. I, g% _
    按m/j , (3-1)式变成:
7 u$ d4 _4 \8 g$ ]" t- ~    (m/j± ij )^2 = (ij)^2 ± 2mi + (m/j )^2  (i≥ 1 ) (j ≥ 3)   (3-2)
3 \. j$ _' {' v' h4 F
  X# O# I6 Z1 l! J2 u5 e0 O   例3: n=299    \frac{1}{3} ≡ 100 (mod 299)   100^2 ≡ 133 (mod 299)  
( f; A; ~& f3 m8 y4 g   (100-3)^2 ≡ 3^2-2+133  (mod 299)    =>  97^2 ≡ 140  (mod 299)
  ?# |2 M9 S  e* [! M. H   (100+3)^2 ≡ 3^2+2+133  (mod 299)    =>  103^2 ≡ 144  (mod 299)
( d- x$ L8 m% e6 x6 v   1+1/3=4/3 ≡ 1+100=101 (mod 299)     101^2 ≡ 35 (mod 299)
3 d# _  f5 b3 U5 l7 I4 O   (101-3)^2 ≡ 3^2-2*4+35  (mod 299)    =>  98^2 ≡ 36  (mod 299) ' g# f7 l- y# S6 p
   (101+3)^2 ≡ 3^2+2*4+35  (mod 299)    =>  104^2 ≡ 52  (mod 299)
. X  M, m, T7 w* L- \* A   1-1/3=-2/3 ≡ 1-100=-99 (mod 299)     99^2 ≡ 233 (mod 299)  
+ h' o0 v$ F! s' |$ Q   (99-3)^2 ≡ 3^2-2*(-2)+233  (mod 299)    =>  96^2 ≡ 246  (mod 299)
4 o0 A# w: \! C) w   (101+3)^2 ≡ 3^2+2*(-2)+233  (mod 299)    =>  102^2 ≡ 238  (mod 299)   
0 j9 q# S- W1 u+ _( @* i5 R   按2+1/3也能得到相同结果，这里不在验证.
8 }5 n) `# n$ l" P
$ @$ ~0 Y/ q& w0 L( L3 s7 |: f0 ~   当然如果j=2s, 即为偶数, 可以计算一半的值, (3-2)式得  :
3 x: G1 o: n) N  |    (m/j ± i*s)^2=(is)^2±mi+(m/j)^2   (i ≥ 1)   (j ≥ 3)   (3-3) - |0 w; w, Y. b) m+ Y/ y6 C" q2 j
  更一般的公式: 当为 g/j    g <j/2  , (g, j)=1, 这里就不再给出.+ V$ k( I! f! k, O" ^$ K  `( F2 I
& o, Z1 H' Y0 S  B! A4 N/ `

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

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



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