数学建模社区-数学中国

标题: 二次剩余值的关联计算(上) [打印本页]
作者: songls    时间: 2023-11-15 20:10
标题: 二次剩余值的关联计算(上)
        二次剩余值的关联计算(上)
5 w7 g4 V! G2 y+ {& N1 f9 A" R( [1 F) B) q6 c& ]
一、 二次剩余中\frac{1}{2} 相关值的计算：7 t6 J* N, r7 a6 T6 X# U
   对于完全平方公式：
! i% o9 b7 J- ~   (1/2 -m)^2  = 1/4 -m+m^2 = 1/4 +m(m-1)   (m≥1)  (1-1)
% {: L7 D& l) e; |" b
1 I4 H  @" s" z, k    在n为奇数时, 上式的同余可以分为:! g3 g5 X+ |9 q2 q1 u
    ① 当n=4k-1时，对(1-1)求同余得: / {" u! Q1 R$ H8 [. {
    (1/2-m)^2  ≡ (2k-m)^2 ≡ k+m(m-1) (mod n)    (1-2)8 i1 S: b; A) m7 Q. c3 R! q
    ② 当n=4k+1时, 对(1-1)求同余得:
' t, k0 ~4 X" c0 e) \) c- \    (1/2 -m)^2  ≡ (2k+1-m)^2 ≡ -k+m(m-1) ≡ n-k+m(m-1) (mod n)    (1-3), F0 q% u% b' B4 u$ f6 r1 d& T
% {; \' q5 Y4 m3 C
  为以后叙述方便，我们对 1/2-1  1/2-2  ...  1/2-m (m >=1)  这类数称为二次剩余的后序序列, 即1/2  减小的方向的数列.' X+ w  y+ q4 y1 T, p$ S- d3 a
7 y- S( b4 ]3 Q# ~" M
  二次剩余后序序列的二次剩余值有个特点, 与k(k>0)值相关, 是k值与两个连续整数积的和，与k值同奇同偶。$ J) e5 D8 R  W8 c. U( o; t. s3 H
  如n=299=4*75-1    k=75    2k=150 , 二次剩余后序序列为:
9 K5 M, \! K) R( z1 K- O: B   (150-1)^2 ≡ 75+1*(1-1) ≡ 75 +0 ≡ 75 (mod 299)  =>  149^2 ≡ 75 (mod 299)  
& {6 H+ d3 }( x   (150-2)^2 ≡ 75+2*(2-1) ≡ 75 +2 ≡ 77 (mod 299)  =>  148^2 ≡ 77 (mod 299)    D. A' M3 N+ L, S( w
   (150-3)^2 ≡ 75+3*(3-1) ≡ 75 +6 ≡ 81 (mod 299)  =>  147^2 ≡ 81 (mod 299)
9 f& P$ n3 z8 Y8 j  k1 }
3 J; P3 N) k/ c) ?; _  .
2 I5 {$ B* z$ z  .
9 }# \! T% a) x   根据后序序列，可以得到一个分解整数的方法:
- i0 N6 a& `$ p* v   设n为奇合数, 如果 c^2-k=m(m-1)  m>0  => (2k-m)^2 ≡ c^2 (mod n)  , 或者 7 |6 ^( q" p" A3 D1 ~
    c^2-k=m(m-1) => 4c^2-4k+1=4m(m-1)+1 => (2c)^2 ≡ (2m-1)^2 (mod n)  - I- H/ E) F) ?; y6 e4 e6 h
   上述等式，由费马分解即可得到n的因子, 不过效率较低.
7 d/ F* s5 A" ~    例1: n=299-4*75-1 ,  k=75
, z) `" B% l* O1 p) U# W      根据后序序列，大于75且与75同奇同偶的完全平方：9^2-81- s" a, x- G- ?3 w
      81-75=6=2*3 为连续两个整数积，在后序序列上7 v2 E$ \+ T5 L( L. ~
      ∴ (150-3)^2≡81 (mod 299)  => 147^2≡81 (mod 299)
; E2 K" X; A% T" u5 U+ x$ i      或者 (2*9)^2≡(2*2+1)^2 (mod 299) => 18^2≡5^2(mod 299)
2 {2 T; P: Z" l  D) O
5 T+ B/ J/ i5 `# N( D* m$ y 二、连续两个整数积的分解方法; s# s+ [* ^# ~1 e. {- F7 m1 H. [
   1、分解方法介绍
2 T0 R2 x' L$ ]   例2: n=299=4*75-1
# q" n8 ?: r" b) |: B      25^2 ≡ 27 (mod 299)   =>
" A, }4 G/ b' ~$ o' y4 p, a     25^2 ≡ 25+2 (mod 299)  =>  
9 N: B, t7 M6 }: b! Z     25^2-25-2 ≡ 0 (mod 299) =>  
. \, U1 ?2 F8 D! f0 Q' d     (25-2)(25+1) ≡ 0 (mod 299) => 9 D. F7 I! i7 [2 x& d8 @9 z
     23*26 ≡ 0 (mod 299)   / X% i! z& [+ @
     (23,299)=23   (26,299)=13      299=13*230 s7 v$ J8 o* R" z# e8 u
. g6 o6 J" D- F& p' i9 a) X
   分解方法:  设n为奇合数,  a^2 ≡ b (mod n)  , 如果 b=a+i(i+1) (i ≥ 0 )  , 则可得到:
# q2 I$ A$ x7 v: x5 I/ _* a. g      a^2 ≡ b (mod n)  => 7 Q* R8 u" f0 j
     a^2-b-i(i+1) ≡ 0 (mod n)  =>
0 s( e0 _0 i6 C     (a-(i+1))(a+i) ≡ 0 (mod n) 1 b3 N" f1 G- L) c4 k
     (a-(i+1),n)>1   (a+i , n)>1    即可分解n( a. T8 O8 k6 ?, o
: a* ^' H% d! u: ]3 O; A
   2、分解方法的另一个解释 , _& Q( C' L% ?& E! W' X6 ^
    设n为奇数, a^2 ≡ b(mod n),  如果m=a, 则由(1-1)公式得:
3 o2 n) i% _5 v     (1/2 -a)^2  ≡ 1/4 +a^2-a (mod n)   =>
  ]. r6 L, T" f6 e4 V& w       (1/2 -a)^2  ≡ 1/4 +b-a (mod n)    (2-1)
% m1 H& g2 u* T4 F, j     
- w! ]& g! l- K3 E9 a     ① n=4k-1 , 2-1式得：* `7 J- N9 {2 o) F% U
     (2k-a)^2 ≡ k+b-a(mod n)     (2-2)7 g; `: v, K) F4 |( ?+ l& l  A3 w
     ① n=4k+1 , 2-1式得：/ k5 z9 g1 S9 ?! E
     (2k+1-a)^2 ≡ n-k+b-a (mod n)   (2-3)
8 S, k  D' s/ @- t  F; h2 S8 W9 m, F6 s) c2 X& u4 W
   从(2-1(式, 可知二次剩余的计算,  在[1,1/4]范围内, 计算出[1,n-1]的二次剩余值.
* b- `  p9 K, N4 X1 e5 T! X   在例2中, 按(2-2)式的计算, 可得: $ o8 g* M7 E4 ^8 V$ m( X' \9 _
    (150-25)^2 ≡ 75+27-25 (mod 299) =>  125^2 ≡ 77 (mod 299)  . R, ]9 p0 M6 Y! D% L& L5 t
    所以, a^2 ≡ b (mod n)  ，如果b=a+i(i+1) ,其相对1/2的剩余值在后序序列上.
" e0 b% J+ N6 Q- p) F/ i
$ _5 u6 R' r1 x7 K% ^ 三、1/j (j >=3)的计算方法
. i+ O4 a% h; f/ F/ Y  上面的是计算 1/2， 即j=2, 如果j>2时,  有如下的1/j计算方法:
7 ?; Y- N! x5 J  t& V0 e, c: x9 _' M8 E   (1/j ± ij)^2 = (ij)^2 ± 2i + (1/j)^2 (i >= 1 ) (j ≥3)   (3-1)
* P2 j, f6 I8 \+ N& O
( o) z8 Q# s/ Y6 m  p2 c   而对于\frac{1}{j}相邻, 有两种计算,
$ y$ S$ z. o+ D    1)  1/j    1+1/j  2+1/j ... t+1/j    (t<j)  
1 y3 W$ n9 A+ I4 A    2) t-1/j ... 1-1/j  1/j  1+1/j ...  t+1/j   (t < j/2)  ( Y+ X3 l" E7 L/ j+ F
    t+1/j= (1+tj)/j = m/j ,  m=1+tj
8 U* |1 J0 y/ v: Z! L& M5 m2 ^. J0 }- f, N/ H
    按m/j , (3-1)式变成: 5 u# @/ T  Q, I# C6 D% h
    (m/j± ij )^2 = (ij)^2 ± 2mi + (m/j )^2  (i≥ 1 ) (j ≥ 3)   (3-2), ^; X) ^+ H& Y3 i* N" G

# S, ~! U) s) S5 L8 V8 `   例3: n=299    \frac{1}{3} ≡ 100 (mod 299)   100^2 ≡ 133 (mod 299)  
5 b7 o2 N) p, w! y) K. Y( w6 J   (100-3)^2 ≡ 3^2-2+133  (mod 299)    =>  97^2 ≡ 140  (mod 299)
7 J/ X& K" P! J+ z   (100+3)^2 ≡ 3^2+2+133  (mod 299)    =>  103^2 ≡ 144  (mod 299)7 R4 w" @$ C' |( x+ Y1 h
   1+1/3=4/3 ≡ 1+100=101 (mod 299)     101^2 ≡ 35 (mod 299)
7 M7 E! p2 U+ l4 s/ m2 L4 g   (101-3)^2 ≡ 3^2-2*4+35  (mod 299)    =>  98^2 ≡ 36  (mod 299)
% j" h. M: M: ]( M6 f( v/ h   (101+3)^2 ≡ 3^2+2*4+35  (mod 299)    =>  104^2 ≡ 52  (mod 299) ; P- i  B/ h, ?7 Z: V/ ]
   1-1/3=-2/3 ≡ 1-100=-99 (mod 299)     99^2 ≡ 233 (mod 299)  2 _  ^) R+ t* o) A, }
   (99-3)^2 ≡ 3^2-2*(-2)+233  (mod 299)    =>  96^2 ≡ 246  (mod 299)
* [2 y1 T9 N7 R8 B  S' n4 {   (101+3)^2 ≡ 3^2+2*(-2)+233  (mod 299)    =>  102^2 ≡ 238  (mod 299)   
; j4 W, K) m, w, D$ t   按2+1/3也能得到相同结果，这里不在验证.$ e! D7 m1 k- P4 F2 y

; J' A6 }+ c9 u. V+ c   当然如果j=2s, 即为偶数, 可以计算一半的值, (3-2)式得  :
; P$ q  M+ a. c- z+ _  `: s    (m/j ± i*s)^2=(is)^2±mi+(m/j)^2   (i ≥ 1)   (j ≥ 3)   (3-3) - i: [! K& d7 g4 o3 L9 x1 \( i
  更一般的公式: 当为 g/j    g <j/2  , (g, j)=1, 这里就不再给出.3 P; W2 n2 l5 m; p3 L

4 \3 C, f1 x+ Y2 b, }5 H

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

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



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