数学建模社区-数学中国

标题: 二次剩余值的关联计算(上) [打印本页]
作者: songls    时间: 2023-11-15 20:10
标题: 二次剩余值的关联计算(上)
        二次剩余值的关联计算(上)  N7 {+ S* [2 I, W
$ V1 Q( r& j* z) G, X$ o
一、 二次剩余中\frac{1}{2} 相关值的计算：9 D) v8 E0 M" ~  l" P
   对于完全平方公式：
/ W* a5 M2 f' Z8 b' R  s7 D   (1/2 -m)^2  = 1/4 -m+m^2 = 1/4 +m(m-1)   (m≥1)  (1-1)
8 m1 E9 e6 b' _$ ]7 @* o* t) z; K4 |
    在n为奇数时, 上式的同余可以分为:
8 i' |# P  q  b" k) C$ z    ① 当n=4k-1时，对(1-1)求同余得: 0 G+ e- R3 w" u2 E3 q4 B
    (1/2-m)^2  ≡ (2k-m)^2 ≡ k+m(m-1) (mod n)    (1-2)
5 S0 i0 U5 y9 Y4 f% f% M. [% V    ② 当n=4k+1时, 对(1-1)求同余得:   A( z( T0 [) ~
    (1/2 -m)^2  ≡ (2k+1-m)^2 ≡ -k+m(m-1) ≡ n-k+m(m-1) (mod n)    (1-3)
1 Z- |2 m/ _* |
4 H% A* u( W% X. n& E& L7 t6 S  为以后叙述方便，我们对 1/2-1  1/2-2  ...  1/2-m (m >=1)  这类数称为二次剩余的后序序列, 即1/2  减小的方向的数列.0 s: U; V2 O, a* ?2 I$ l, z) |$ B
5 M9 j* e$ L% I" h2 l2 f; a
  二次剩余后序序列的二次剩余值有个特点, 与k(k>0)值相关, 是k值与两个连续整数积的和，与k值同奇同偶。
, d7 b" J% G3 f  如n=299=4*75-1    k=75    2k=150 , 二次剩余后序序列为:. ]' }2 Q- k& ^: }0 n
   (150-1)^2 ≡ 75+1*(1-1) ≡ 75 +0 ≡ 75 (mod 299)  =>  149^2 ≡ 75 (mod 299)  " E' {& @1 N4 u
   (150-2)^2 ≡ 75+2*(2-1) ≡ 75 +2 ≡ 77 (mod 299)  =>  148^2 ≡ 77 (mod 299)  9 l1 ~. `% ]. ^2 |5 d
   (150-3)^2 ≡ 75+3*(3-1) ≡ 75 +6 ≡ 81 (mod 299)  =>  147^2 ≡ 81 (mod 299) 5 q0 d0 A# x5 [" ]. X

! b" \+ h* K3 L0 [7 K5 L! Z: x  .
$ k. W: m6 @' w9 K1 i  ., f* a" k) V* Z0 h1 f$ k
   根据后序序列，可以得到一个分解整数的方法:; ^$ h4 J  I7 L! x
   设n为奇合数, 如果 c^2-k=m(m-1)  m>0  => (2k-m)^2 ≡ c^2 (mod n)  , 或者
: C( x$ v1 r. `; ~6 t( q    c^2-k=m(m-1) => 4c^2-4k+1=4m(m-1)+1 => (2c)^2 ≡ (2m-1)^2 (mod n)  
1 h" [. {# d9 A   上述等式，由费马分解即可得到n的因子, 不过效率较低.
8 o: k, I- k: i$ l7 t    例1: n=299-4*75-1 ,  k=75
8 L1 }8 c. K+ u! A4 B      根据后序序列，大于75且与75同奇同偶的完全平方：9^2-81
2 w- O1 n) c1 D8 A2 W8 Q      81-75=6=2*3 为连续两个整数积，在后序序列上2 t0 x! B2 @; N$ s+ R& F% s
      ∴ (150-3)^2≡81 (mod 299)  => 147^2≡81 (mod 299)' Q) ~1 }0 y- y& l
      或者 (2*9)^2≡(2*2+1)^2 (mod 299) => 18^2≡5^2(mod 299)
/ P9 U" F$ O" d
' |1 q  F% R; w* \3 F; F 二、连续两个整数积的分解方法9 ^0 k) W- B8 H" X2 q7 h' K; H
   1、分解方法介绍
8 e2 ?( h2 x% S   例2: n=299=4*75-1! t4 u' K* X& I# G1 _
      25^2 ≡ 27 (mod 299)   => . O7 |3 X; R: }
     25^2 ≡ 25+2 (mod 299)  =>  + w2 B! B: a5 V9 f  W; Y, H
     25^2-25-2 ≡ 0 (mod 299) =>  8 n) K( {0 R8 P8 x" j7 p& O6 F% W
     (25-2)(25+1) ≡ 0 (mod 299) =>
$ @# Z* q; G# y     23*26 ≡ 0 (mod 299)   ' K+ |$ L  i9 a1 A* K( ]
     (23,299)=23   (26,299)=13      299=13*23, v- k% R# \! e

8 e; R" ?% \. B9 i* Q; I   分解方法:  设n为奇合数,  a^2 ≡ b (mod n)  , 如果 b=a+i(i+1) (i ≥ 0 )  , 则可得到:
; I/ p) V3 F5 y3 q/ a      a^2 ≡ b (mod n)  => / P2 D' x4 I# @3 c' x3 C1 X5 Y
     a^2-b-i(i+1) ≡ 0 (mod n)  => . {, g* j$ m: X. Q2 C% Y7 ]8 Y/ B) d0 Q
     (a-(i+1))(a+i) ≡ 0 (mod n) . _9 ~# U8 f4 V4 W. ]( L: V
     (a-(i+1),n)>1   (a+i , n)>1    即可分解n
- k: ~1 m1 s  O+ ]4 S( z) Q, r( }4 w6 W3 L  o" I6 q
   2、分解方法的另一个解释 ' Q  |- m3 Q! k
    设n为奇数, a^2 ≡ b(mod n),  如果m=a, 则由(1-1)公式得:
3 T" I0 M; C" w# p$ s) n     (1/2 -a)^2  ≡ 1/4 +a^2-a (mod n)   =>
1 O' j' C2 j0 R6 P/ L" E       (1/2 -a)^2  ≡ 1/4 +b-a (mod n)    (2-1)
$ H/ }! V" B! B" `* b. Y* P! o     8 s. P# I' l" G8 b* M3 K4 y+ K8 b- E
     ① n=4k-1 , 2-1式得：# o! b' O, j. x. O, S9 g0 I
     (2k-a)^2 ≡ k+b-a(mod n)     (2-2)
/ {0 @! K: K0 Y6 `6 c     ① n=4k+1 , 2-1式得：
" a" p9 T2 B9 o# I6 d     (2k+1-a)^2 ≡ n-k+b-a (mod n)   (2-3)
3 c5 e6 B5 h) I7 b8 `& \$ i% c- A: c. X# ~8 W# W" I7 F6 j
   从(2-1(式, 可知二次剩余的计算,  在[1,1/4]范围内, 计算出[1,n-1]的二次剩余值.
: a9 {3 e1 |+ `' a( S( g   在例2中, 按(2-2)式的计算, 可得:
7 w" i' n! U, G. S0 T+ L9 s$ j5 ~    (150-25)^2 ≡ 75+27-25 (mod 299) =>  125^2 ≡ 77 (mod 299)  9 ]. [" M8 \7 G9 [# x/ q
    所以, a^2 ≡ b (mod n)  ，如果b=a+i(i+1) ,其相对1/2的剩余值在后序序列上.
+ y4 C/ _7 w2 M, D8 S; b: K6 K# g6 X9 q
三、1/j (j >=3)的计算方法
; |$ q6 U3 M6 R  上面的是计算 1/2， 即j=2, 如果j>2时,  有如下的1/j计算方法:
+ \, j3 H9 S0 ~& c0 w% ?* \   (1/j ± ij)^2 = (ij)^2 ± 2i + (1/j)^2 (i >= 1 ) (j ≥3)   (3-1)
& X8 \# a1 |" a8 M+ Y0 t7 ]1 Y2 q
5 p  z) i  x5 L, Y( v   而对于\frac{1}{j}相邻, 有两种计算,
( Q4 F- L% z$ X1 z, `    1)  1/j    1+1/j  2+1/j ... t+1/j    (t<j)  
. m+ w7 {7 S! W" H    2) t-1/j ... 1-1/j  1/j  1+1/j ...  t+1/j   (t < j/2)  , C8 ?; ^% V; r# n: v! x
    t+1/j= (1+tj)/j = m/j ,  m=1+tj
% R- U8 z( [: j. P6 S) h' C7 t: Z' w. z
6 |) T+ g- _- e+ O( v    按m/j , (3-1)式变成:
: f. G# S6 n& T    (m/j± ij )^2 = (ij)^2 ± 2mi + (m/j )^2  (i≥ 1 ) (j ≥ 3)   (3-2)
) l- [- _; {3 Y+ m( u6 u  ]9 {' g9 n) e+ T  f- Q/ n
   例3: n=299    \frac{1}{3} ≡ 100 (mod 299)   100^2 ≡ 133 (mod 299)  $ k0 H) h2 ?* g2 M
   (100-3)^2 ≡ 3^2-2+133  (mod 299)    =>  97^2 ≡ 140  (mod 299)
$ Q8 c2 A# @/ I/ R+ O% G% ^   (100+3)^2 ≡ 3^2+2+133  (mod 299)    =>  103^2 ≡ 144  (mod 299)+ \$ ]' c% L6 ?9 k
   1+1/3=4/3 ≡ 1+100=101 (mod 299)     101^2 ≡ 35 (mod 299)$ p+ O- ^8 i+ F0 O/ Y
   (101-3)^2 ≡ 3^2-2*4+35  (mod 299)    =>  98^2 ≡ 36  (mod 299) ( d6 `7 B; o8 N( d6 Z$ E; o* z3 h) O
   (101+3)^2 ≡ 3^2+2*4+35  (mod 299)    =>  104^2 ≡ 52  (mod 299)
% S1 f; Q( t  O+ h0 V2 x   1-1/3=-2/3 ≡ 1-100=-99 (mod 299)     99^2 ≡ 233 (mod 299)  
0 R& |' J' i& z% X1 y   (99-3)^2 ≡ 3^2-2*(-2)+233  (mod 299)    =>  96^2 ≡ 246  (mod 299)
1 t, j6 a5 X' ]3 H   (101+3)^2 ≡ 3^2+2*(-2)+233  (mod 299)    =>  102^2 ≡ 238  (mod 299)   
* V7 R8 L! l+ I" s5 j' i   按2+1/3也能得到相同结果，这里不在验证.
9 B  U! b5 o$ r, Z& k) N3 }# |* o, N+ o' t/ J% m
   当然如果j=2s, 即为偶数, 可以计算一半的值, (3-2)式得  : ; m) v4 j' x2 C( ~% W8 v) n
    (m/j ± i*s)^2=(is)^2±mi+(m/j)^2   (i ≥ 1)   (j ≥ 3)   (3-3)
# {7 L) y& f9 t& w; v  更一般的公式: 当为 g/j    g <j/2  , (g, j)=1, 这里就不再给出.; R1 b) U" L2 s- `8 E
* h( E8 A9 x( [# r2 v& v% N

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

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



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