QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 3054|回复: 0
打印 上一主题 下一主题

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

[复制链接]
字体大小: 正常 放大
songls        

6

主题

3

听众

23

积分

升级  18.95%

  • TA的每日心情
    郁闷
    2023-12-11 09:00
  • 签到天数: 7 天

    [LV.3]偶尔看看II

    跳转到指定楼层
    1#
    发表于 2023-11-15 20:10 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
            二次剩余值的关联计算(上)
    , n, v. I+ k% _: o
    " S4 W) [. J5 r( A, } 一、 二次剩余中\frac{1}{2} 相关值的计算:3 V; `7 O$ X/ Y: {0 S4 _1 f+ J
       对于完全平方公式:
    ( k; O7 l' Q( ?1 y* T   (1/2 -m)^2  = 1/4 -m+m^2 = 1/4 +m(m-1)   (m≥1)  (1-1)
    # t3 @5 c( _7 e2 h  t; p5 n% F, x- x' R9 u1 q5 U! V8 p
        在n为奇数时, 上式的同余可以分为:4 a" p6 I. f, t2 ?! G
        ① 当n=4k-1时,对(1-1)求同余得:
    & A' j' z$ [( v4 g1 d    (1/2-m)^2  ≡ (2k-m)^2 ≡ k+m(m-1) (mod n)    (1-2)1 ]0 ^8 }7 t) @3 X6 h$ T
        ② 当n=4k+1时, 对(1-1)求同余得: 0 _1 P8 @5 m8 @& R
        (1/2 -m)^2  ≡ (2k+1-m)^2 ≡ -k+m(m-1) ≡ n-k+m(m-1) (mod n)    (1-3)
      L* `& N! ^9 g7 H/ @# |/ B4 y+ G- A1 U& h; b3 b' _0 L% P
      为以后叙述方便,我们对 1/2-1  1/2-2  ...  1/2-m (m >=1)  这类数称为二次剩余的后序序列, 即1/2  减小的方向的数列.
    2 P( X1 M/ w9 i1 U* F5 @& a2 U4 p$ O" _
      二次剩余后序序列的二次剩余值有个特点, 与k(k>0)值相关, 是k值与两个连续整数积的和,与k值同奇同偶。# p5 o+ [" Z6 _; r
      如n=299=4*75-1    k=75    2k=150 , 二次剩余后序序列为:& V; R4 f" S( j/ }
       (150-1)^2 ≡ 75+1*(1-1) ≡ 75 +0 ≡ 75 (mod 299)  =>  149^2 ≡ 75 (mod 299)  , l( ], I' e$ p- R) Z; u
       (150-2)^2 ≡ 75+2*(2-1) ≡ 75 +2 ≡ 77 (mod 299)  =>  148^2 ≡ 77 (mod 299)  
    & o2 W8 r: Y- A' e   (150-3)^2 ≡ 75+3*(3-1) ≡ 75 +6 ≡ 81 (mod 299)  =>  147^2 ≡ 81 (mod 299)   D, U( M( K; B- n! m

    # e2 y2 L. H  g  K% }9 y  .
    0 I) Y4 t( U7 `  .
    9 ?. G( F+ H4 `$ q   根据后序序列,可以得到一个分解整数的方法:
    1 h. e" [9 v1 H$ J2 |% @   设n为奇合数, 如果 c^2-k=m(m-1)  m>0  => (2k-m)^2 ≡ c^2 (mod n)  , 或者 ( D- F7 F6 Y$ ^' |/ ~
        c^2-k=m(m-1) => 4c^2-4k+1=4m(m-1)+1 => (2c)^2 ≡ (2m-1)^2 (mod n)  3 P. R3 z- M' V: B9 w* Q) _3 ~2 K4 {
       上述等式,由费马分解即可得到n的因子, 不过效率较低.
    / F+ X9 I4 S% H/ x    例1: n=299-4*75-1 ,  k=75
    # k0 s! b% d  \4 q1 H      根据后序序列,大于75且与75同奇同偶的完全平方:9^2-81" \6 @, \7 O7 a( c& j8 b
          81-75=6=2*3 为连续两个整数积,在后序序列上3 \! L# ]- S5 m" U
          ∴ (150-3)^2≡81 (mod 299)  => 147^2≡81 (mod 299)- \1 P' P% ]* R
          或者 (2*9)^2≡(2*2+1)^2 (mod 299) => 18^2≡5^2(mod 299)- ]. `  v$ o8 p$ i
    0 Y/ k' [: Q# {/ Z* p9 a
    二、连续两个整数积的分解方法5 ?) F2 |9 N0 O& o" [0 Q
       1、分解方法介绍+ O7 b# x) G+ K/ K; M$ z
       例2: n=299=4*75-1* p9 t7 h7 L) z+ }' x' ~
          25^2 ≡ 27 (mod 299)   =>
    4 d4 g1 n, F  R+ ]* s     25^2 ≡ 25+2 (mod 299)  =>  6 d, i' _5 K, }' T  H0 @& T/ m
         25^2-25-2 ≡ 0 (mod 299) =>  
    ! I! m1 z2 ?7 r' p' j; G0 V     (25-2)(25+1) ≡ 0 (mod 299) =>
    - M/ C, ]# ^( H7 y0 Q     23*26 ≡ 0 (mod 299)   
      G$ Z( p, J9 f' E% R/ M     (23,299)=23   (26,299)=13      299=13*237 Z; \3 s8 B, v8 r% w

    9 d. _- Q6 s. `* P   分解方法:  设n为奇合数,  a^2 ≡ b (mod n)  , 如果 b=a+i(i+1) (i ≥ 0 )  , 则可得到:
    " l6 d3 P3 ^+ n      a^2 ≡ b (mod n)  => 0 Q+ t! Q, x0 k9 K/ j2 U6 \
         a^2-b-i(i+1) ≡ 0 (mod n)  => " d+ N9 a: q$ B8 ]+ S
         (a-(i+1))(a+i) ≡ 0 (mod n) & g9 K; E/ F$ a2 B$ X5 W3 A
         (a-(i+1),n)>1   (a+i , n)>1    即可分解n
    7 N7 m; G& q% H
    ' d; h$ l0 ~2 Y   2、分解方法的另一个解释 2 `1 ]% F$ M7 c- z$ j
        设n为奇数, a^2 ≡ b(mod n),  如果m=a, 则由(1-1)公式得: 8 ?; A/ J& a8 U
         (1/2 -a)^2  ≡ 1/4 +a^2-a (mod n)   =>
    ( u. u5 i  d: L* ~6 L7 c2 K/ r0 x       (1/2 -a)^2  ≡ 1/4 +b-a (mod n)    (2-1)
    ) i% i& K3 D7 W9 y! i& a2 C     
    6 P9 w! \: [( O' H     ① n=4k-1 , 2-1式得:9 `  c- j8 H1 ?5 n7 S3 S5 g
         (2k-a)^2 ≡ k+b-a(mod n)     (2-2)
    ' p0 J/ i- ?6 t  A0 H9 [. f     ① n=4k+1 , 2-1式得:
    ; i3 e; H7 [7 j0 U! P! r. O7 a. H     (2k+1-a)^2 ≡ n-k+b-a (mod n)   (2-3): U! k+ @: Q9 r; z; v

    + b0 p& B3 ~" n" ]( ?) g3 Z   从(2-1(式, 可知二次剩余的计算,  在[1,1/4]范围内, 计算出[1,n-1]的二次剩余值.
    . N) O6 D; r8 X( O; F3 R( t   在例2中, 按(2-2)式的计算, 可得:
    : M6 |" P& D( ~: t: L  C5 o    (150-25)^2 ≡ 75+27-25 (mod 299) =>  125^2 ≡ 77 (mod 299)  " b5 j# }: w* C  |
        所以, a^2 ≡ b (mod n)  ,如果b=a+i(i+1) ,其相对1/2的剩余值在后序序列上.
    # Z* j" X% N) k3 M% X
    $ a/ g7 p6 F4 q, i6 Y 三、1/j (j >=3)的计算方法
    0 Y4 `$ h8 m) P4 L$ C6 k  上面的是计算 1/2, 即j=2, 如果j>2时,  有如下的1/j计算方法:3 Q. w; _/ C. z
       (1/j ± ij)^2 = (ij)^2 ± 2i + (1/j)^2 (i >= 1 ) (j ≥3)   (3-1)
    ( v- K7 ~, N( B7 [3 N
    ! x) ^1 G  ~- Q! R6 v/ t3 v2 T   而对于\frac{1}{j}相邻, 有两种计算,
    9 N" l% Y7 s$ `' D7 l    1)  1/j    1+1/j  2+1/j ... t+1/j    (t<j)  
    6 ?& I& N0 i* @    2) t-1/j ... 1-1/j  1/j  1+1/j ...  t+1/j   (t < j/2)  
    - f- r' ?  T7 t/ t    t+1/j= (1+tj)/j = m/j ,  m=1+tj
    0 h( B& a- m7 b  B$ a9 D( r0 H7 @" v4 K7 V( R1 `/ c5 T
        按m/j , (3-1)式变成: # t/ O8 w% O' {' V" G6 m% O+ B2 _* f' D
        (m/j± ij )^2 = (ij)^2 ± 2mi + (m/j )^2  (i≥ 1 ) (j ≥ 3)   (3-2)
    ; u0 I; S7 v- D- i+ J( V, U% n
    / C( x! W# h4 e3 r8 I$ S' C( e; L   例3: n=299    \frac{1}{3} ≡ 100 (mod 299)   100^2 ≡ 133 (mod 299)  
    - a, C' R' p) Y) H# _7 {   (100-3)^2 ≡ 3^2-2+133  (mod 299)    =>  97^2 ≡ 140  (mod 299)
    + V7 J0 Q% D' E   (100+3)^2 ≡ 3^2+2+133  (mod 299)    =>  103^2 ≡ 144  (mod 299)
    ( l+ n' y% ?0 W' W5 ~0 p  s' d2 o   1+1/3=4/3 ≡ 1+100=101 (mod 299)     101^2 ≡ 35 (mod 299)3 `( q) i; f: z; P& m9 p
       (101-3)^2 ≡ 3^2-2*4+35  (mod 299)    =>  98^2 ≡ 36  (mod 299)
    ; T9 x! R5 g6 S% a$ z; n( z4 d   (101+3)^2 ≡ 3^2+2*4+35  (mod 299)    =>  104^2 ≡ 52  (mod 299)
    8 ]& Z) S7 `2 ]( I! ?   1-1/3=-2/3 ≡ 1-100=-99 (mod 299)     99^2 ≡ 233 (mod 299)  
    " \, r, S' o4 N* s& J   (99-3)^2 ≡ 3^2-2*(-2)+233  (mod 299)    =>  96^2 ≡ 246  (mod 299)
    , @# }: H1 E4 ~2 P   (101+3)^2 ≡ 3^2+2*(-2)+233  (mod 299)    =>  102^2 ≡ 238  (mod 299)   
    * R4 ~# E2 z, V   按2+1/3也能得到相同结果,这里不在验证.2 f( R4 r- T9 H0 b" {
    ( G0 J6 B/ f* D& k
       当然如果j=2s, 即为偶数, 可以计算一半的值, (3-2)式得  :
    . D( N8 a, i9 l4 V2 t! \1 [. x    (m/j ± i*s)^2=(is)^2±mi+(m/j)^2   (i ≥ 1)   (j ≥ 3)   (3-3) " E" `# l2 g0 o4 n9 H  _( y3 C
      更一般的公式: 当为 g/j    g <j/2  , (g, j)=1, 这里就不再给出.
    1 X  ^8 l/ h8 C+ z5 O+ P. F2 [( J1 `* |
    + V" ^- v' l5 T% ^5 R; X) e+ O$ I

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

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

    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-7-24 10:08 , Processed in 0.850506 second(s), 53 queries .

    回顶部