数学建模社区-数学中国

标题: 二次剩余值的关联计算(上) [打印本页]
作者: songls    时间: 2023-11-15 20:10
标题: 二次剩余值的关联计算(上)
        二次剩余值的关联计算(上)6 l3 r0 s7 y& p+ y0 ~& [
; v0 y: ~0 i& U& H( u; F+ Y
一、 二次剩余中\frac{1}{2} 相关值的计算：
0 a; x2 u$ ]" V8 n6 w$ H   对于完全平方公式：
, U$ W. m% }0 @6 p0 M, c$ ]   (1/2 -m)^2  = 1/4 -m+m^2 = 1/4 +m(m-1)   (m≥1)  (1-1)
, C. Z. d: o  A! [4 x: [: t# o: Y
3 w* z5 K) Z" o3 M. P: u% H    在n为奇数时, 上式的同余可以分为:$ ~4 \: s5 ?3 N% K7 x
    ① 当n=4k-1时，对(1-1)求同余得: - y4 ~! J, w+ j! E
    (1/2-m)^2  ≡ (2k-m)^2 ≡ k+m(m-1) (mod n)    (1-2)
" w# c+ _$ h* o. U    ② 当n=4k+1时, 对(1-1)求同余得: & Z/ E* r2 _7 Y. d$ \1 K
    (1/2 -m)^2  ≡ (2k+1-m)^2 ≡ -k+m(m-1) ≡ n-k+m(m-1) (mod n)    (1-3)
& P& |+ B" u% I: R/ J/ @+ _
: }# Y# ?: Q! X$ s1 k2 U0 G  为以后叙述方便，我们对 1/2-1  1/2-2  ...  1/2-m (m >=1)  这类数称为二次剩余的后序序列, 即1/2  减小的方向的数列.
3 x% p. q! j3 h; e
; ?3 `% D) G9 m  二次剩余后序序列的二次剩余值有个特点, 与k(k>0)值相关, 是k值与两个连续整数积的和，与k值同奇同偶。: \, @6 X7 ]4 M  k% Z/ K4 E. r
  如n=299=4*75-1    k=75    2k=150 , 二次剩余后序序列为:
( W0 X, L! ~9 l) b" C   (150-1)^2 ≡ 75+1*(1-1) ≡ 75 +0 ≡ 75 (mod 299)  =>  149^2 ≡ 75 (mod 299)  ( I6 L3 v7 V, q2 G" L- k
   (150-2)^2 ≡ 75+2*(2-1) ≡ 75 +2 ≡ 77 (mod 299)  =>  148^2 ≡ 77 (mod 299)    |, }3 U; Q  p
   (150-3)^2 ≡ 75+3*(3-1) ≡ 75 +6 ≡ 81 (mod 299)  =>  147^2 ≡ 81 (mod 299)
* }1 ^1 U8 A' @
$ x$ Z2 y  _1 E- ^7 g# `  .
# _: F3 _/ x3 V% p$ o" v+ W  .% s" q" ~  m. G4 I" n5 v$ m
   根据后序序列，可以得到一个分解整数的方法:
; V) j: i7 ]: k1 T3 j& u   设n为奇合数, 如果 c^2-k=m(m-1)  m>0  => (2k-m)^2 ≡ c^2 (mod n)  , 或者
+ C* v% Z0 I" X; O: M    c^2-k=m(m-1) => 4c^2-4k+1=4m(m-1)+1 => (2c)^2 ≡ (2m-1)^2 (mod n)  1 M7 l+ I4 A, o8 i/ U
   上述等式，由费马分解即可得到n的因子, 不过效率较低.
: w% M9 p# G. R, \  c! A    例1: n=299-4*75-1 ,  k=75- B8 p9 g" _* M$ Y  m  s
      根据后序序列，大于75且与75同奇同偶的完全平方：9^2-81% ~4 V9 b6 [2 x4 |( }
      81-75=6=2*3 为连续两个整数积，在后序序列上
* ^$ d$ r+ M  a) G      ∴ (150-3)^2≡81 (mod 299)  => 147^2≡81 (mod 299)( u8 z  j/ Y! I
      或者 (2*9)^2≡(2*2+1)^2 (mod 299) => 18^2≡5^2(mod 299)
: z/ t  s/ c  u8 u  y+ m
" c3 o: Q5 n7 h, ^; e 二、连续两个整数积的分解方法
: D) P, s5 j- g( R* t   1、分解方法介绍9 _- G2 K+ }9 c6 [7 n0 P% e: [7 Y
   例2: n=299=4*75-1
2 G& g6 M6 I/ S4 d: P      25^2 ≡ 27 (mod 299)   => ) P- x; T7 F" C" q5 m" \; v
     25^2 ≡ 25+2 (mod 299)  =>  ' E9 B4 e5 ]+ h& L& \
     25^2-25-2 ≡ 0 (mod 299) =>  9 X; M4 q/ t% i' O. d0 p
     (25-2)(25+1) ≡ 0 (mod 299) => & Z0 t4 o- \! o2 }# H0 G
     23*26 ≡ 0 (mod 299)   ! O; k8 A2 R$ h+ Q
     (23,299)=23   (26,299)=13      299=13*23
  b* w# g* ?4 j$ o# X$ ]
- U; i* @  Z4 F& y# c# U0 O   分解方法:  设n为奇合数,  a^2 ≡ b (mod n)  , 如果 b=a+i(i+1) (i ≥ 0 )  , 则可得到:% X( ~4 N  t' U$ ]4 Y" z
      a^2 ≡ b (mod n)  => - Z" F; z- K5 H0 e
     a^2-b-i(i+1) ≡ 0 (mod n)  =>
' [) L0 }8 i/ Q9 w# f& @1 l% I; M& S     (a-(i+1))(a+i) ≡ 0 (mod n) ! O4 j0 `6 l8 s: ~$ f
     (a-(i+1),n)>1   (a+i , n)>1    即可分解n5 @) L% A: S% N3 x

8 M; ?& ?% J  q6 `2 [5 {( V   2、分解方法的另一个解释 / J4 M* h5 m% c' i. n2 e
    设n为奇数, a^2 ≡ b(mod n),  如果m=a, 则由(1-1)公式得:
* r' k9 e: H' A$ Y. o8 g0 p5 Q9 c     (1/2 -a)^2  ≡ 1/4 +a^2-a (mod n)   =>
" T, H' S; J6 O2 @6 E' |       (1/2 -a)^2  ≡ 1/4 +b-a (mod n)    (2-1) 0 E" T* e" p. y8 B
     
7 ]! O; {# M  }, r% Q& @     ① n=4k-1 , 2-1式得：2 Y' x4 l6 d/ _' g7 _3 Y
     (2k-a)^2 ≡ k+b-a(mod n)     (2-2)+ [) s2 w) m6 ]; b
     ① n=4k+1 , 2-1式得：  r- a  n6 \8 y0 V" F
     (2k+1-a)^2 ≡ n-k+b-a (mod n)   (2-3)
1 ]& z9 _/ c' d% \& J* P. i
7 l" x0 g" W8 v! V6 f   从(2-1(式, 可知二次剩余的计算,  在[1,1/4]范围内, 计算出[1,n-1]的二次剩余值.
5 t# C! ^, a' B7 I, @7 S7 q$ f& Q   在例2中, 按(2-2)式的计算, 可得: 3 r! U2 `# s2 l" |5 X! P
    (150-25)^2 ≡ 75+27-25 (mod 299) =>  125^2 ≡ 77 (mod 299)  
9 F% R  q6 b  B9 ^+ K+ d' e) \7 U    所以, a^2 ≡ b (mod n)  ，如果b=a+i(i+1) ,其相对1/2的剩余值在后序序列上.; Q' G& R) U" K9 B% K# w
: ?- v  p5 f: |8 s6 ^
三、1/j (j >=3)的计算方法 : p* s. L$ V9 {0 T/ g2 s
  上面的是计算 1/2， 即j=2, 如果j>2时,  有如下的1/j计算方法:
1 t& Q' @/ ^8 v% c+ D   (1/j ± ij)^2 = (ij)^2 ± 2i + (1/j)^2 (i >= 1 ) (j ≥3)   (3-1)0 G, N5 ]9 [( Q) U8 B1 N
& J" n% ~+ O+ O9 n+ S( F2 S
   而对于\frac{1}{j}相邻, 有两种计算, * _8 B( J" ^3 ]* x9 K
    1)  1/j    1+1/j  2+1/j ... t+1/j    (t<j)  
9 r' t( w0 [5 B* S* ]8 [' k    2) t-1/j ... 1-1/j  1/j  1+1/j ...  t+1/j   (t < j/2)  
9 M2 @5 y) w' ~, H    t+1/j= (1+tj)/j = m/j ,  m=1+tj
) M9 X$ b' L* x" |
- V9 J* k" b: ^    按m/j , (3-1)式变成:   m$ }! r+ X$ F4 |+ P  G
    (m/j± ij )^2 = (ij)^2 ± 2mi + (m/j )^2  (i≥ 1 ) (j ≥ 3)   (3-2)
/ ]( a/ K& Z: v9 j. r( {, p4 }  b& C7 V& K7 e5 V
   例3: n=299    \frac{1}{3} ≡ 100 (mod 299)   100^2 ≡ 133 (mod 299)  , E. u( M. Z2 x. `9 _
   (100-3)^2 ≡ 3^2-2+133  (mod 299)    =>  97^2 ≡ 140  (mod 299): t! e# j  P" j( l, C
   (100+3)^2 ≡ 3^2+2+133  (mod 299)    =>  103^2 ≡ 144  (mod 299); O+ P0 J3 K4 m# A5 {; m2 U: b
   1+1/3=4/3 ≡ 1+100=101 (mod 299)     101^2 ≡ 35 (mod 299)
" O2 Y1 r5 c8 T1 [   (101-3)^2 ≡ 3^2-2*4+35  (mod 299)    =>  98^2 ≡ 36  (mod 299)
7 e6 ?  m1 U. j! q4 F   (101+3)^2 ≡ 3^2+2*4+35  (mod 299)    =>  104^2 ≡ 52  (mod 299)
( x- A: f9 N- A0 D   1-1/3=-2/3 ≡ 1-100=-99 (mod 299)     99^2 ≡ 233 (mod 299)  ) w8 H) j& ?1 b( t
   (99-3)^2 ≡ 3^2-2*(-2)+233  (mod 299)    =>  96^2 ≡ 246  (mod 299) % g0 t, P$ {' s. V; l1 Z
   (101+3)^2 ≡ 3^2+2*(-2)+233  (mod 299)    =>  102^2 ≡ 238  (mod 299)   , f0 ]3 J4 P; Z3 h5 i) k8 {  ]
   按2+1/3也能得到相同结果，这里不在验证.
" f* C3 Y. a" v/ _; R. L1 F4 W
" U; k1 I9 p( r   当然如果j=2s, 即为偶数, 可以计算一半的值, (3-2)式得  :
4 L1 ^5 l! d$ n# H6 Z* R0 X; ]    (m/j ± i*s)^2=(is)^2±mi+(m/j)^2   (i ≥ 1)   (j ≥ 3)   (3-3)
7 q  z) w7 D' n2 e6 L0 X  j+ E+ T  更一般的公式: 当为 g/j    g <j/2  , (g, j)=1, 这里就不再给出./ o8 d1 d- C& x2 A

$ j4 F2 E. X! |- ~

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

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



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