QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 3055|回复: 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
            二次剩余值的关联计算(上)9 Y# n( Z0 s, |4 b8 q$ Z

    / q4 E  _  B1 A/ f 一、 二次剩余中\frac{1}{2} 相关值的计算:$ `) N+ N* b( S( H
       对于完全平方公式:
    0 h" r5 g) v. J: D4 [2 j   (1/2 -m)^2  = 1/4 -m+m^2 = 1/4 +m(m-1)   (m≥1)  (1-1)
    & ~3 N% r" T' ]1 L5 o7 D! _  o& S% e4 [$ a' f& ~5 q
        在n为奇数时, 上式的同余可以分为:; d) W0 V# c" f3 ^7 ^* W6 t8 n
        ① 当n=4k-1时,对(1-1)求同余得: 1 w: y( S9 M7 d
        (1/2-m)^2  ≡ (2k-m)^2 ≡ k+m(m-1) (mod n)    (1-2)
    2 A, W& x/ U4 o  P. G! \    ② 当n=4k+1时, 对(1-1)求同余得: % z1 R% R# o6 `* }9 m
        (1/2 -m)^2  ≡ (2k+1-m)^2 ≡ -k+m(m-1) ≡ n-k+m(m-1) (mod n)    (1-3)7 u0 i+ f, a' E6 Z$ s: w
    9 q+ F+ f0 S. i: E
      为以后叙述方便,我们对 1/2-1  1/2-2  ...  1/2-m (m >=1)  这类数称为二次剩余的后序序列, 即1/2  减小的方向的数列.. v! }% `4 u$ n+ C5 N8 \

      T; ?+ H, v- H- p+ K  二次剩余后序序列的二次剩余值有个特点, 与k(k>0)值相关, 是k值与两个连续整数积的和,与k值同奇同偶。
    ; }' v- ]& b6 L2 d% w* _  如n=299=4*75-1    k=75    2k=150 , 二次剩余后序序列为:  c9 M( I! v6 n3 F
       (150-1)^2 ≡ 75+1*(1-1) ≡ 75 +0 ≡ 75 (mod 299)  =>  149^2 ≡ 75 (mod 299)  6 h$ y$ T& ]  h
       (150-2)^2 ≡ 75+2*(2-1) ≡ 75 +2 ≡ 77 (mod 299)  =>  148^2 ≡ 77 (mod 299)  
    + f! ^5 z$ e' h9 r& y   (150-3)^2 ≡ 75+3*(3-1) ≡ 75 +6 ≡ 81 (mod 299)  =>  147^2 ≡ 81 (mod 299) * F  J! F0 \3 c- `) a6 l  @

    5 |5 a/ F) m  h" P- b- S, ^! H4 }  .  v0 e# k4 I/ {
      .3 Z+ G9 u8 X; l3 t6 e
       根据后序序列,可以得到一个分解整数的方法:
    , H$ l3 F- y* h' Z; {   设n为奇合数, 如果 c^2-k=m(m-1)  m>0  => (2k-m)^2 ≡ c^2 (mod n)  , 或者   f6 f, ]9 e' c/ x
        c^2-k=m(m-1) => 4c^2-4k+1=4m(m-1)+1 => (2c)^2 ≡ (2m-1)^2 (mod n)  
    ( X) n. _4 q' Z# a   上述等式,由费马分解即可得到n的因子, 不过效率较低.4 y7 l/ E0 b9 e) i* T
        例1: n=299-4*75-1 ,  k=75
    " ^: L/ [9 n8 C6 O      根据后序序列,大于75且与75同奇同偶的完全平方:9^2-815 ]- D6 D4 f$ \5 }
          81-75=6=2*3 为连续两个整数积,在后序序列上7 v1 D0 Y9 d% u/ I( U) A# ?9 \4 c9 _  T
          ∴ (150-3)^2≡81 (mod 299)  => 147^2≡81 (mod 299)
      X/ {/ r4 ]0 l5 e. b1 G& y, e0 n      或者 (2*9)^2≡(2*2+1)^2 (mod 299) => 18^2≡5^2(mod 299). `: P6 g- y" c* @7 T
    * k1 v, x( g2 L' b. F: r
    二、连续两个整数积的分解方法
    1 u5 s7 g' N2 L) c! B1 k0 F   1、分解方法介绍
    % R1 u: f5 l% J$ F! I) T: H8 w0 m% u   例2: n=299=4*75-1% D% h9 `$ k8 H4 a: o
          25^2 ≡ 27 (mod 299)   =>
    ; j6 |4 u! ^. G' Y     25^2 ≡ 25+2 (mod 299)  =>  
    8 `1 B* `' \; r" q* B  L' N     25^2-25-2 ≡ 0 (mod 299) =>  ; ?9 Z; Z; M1 o+ n/ u$ `8 @# E  c1 g
         (25-2)(25+1) ≡ 0 (mod 299) =>
    4 K5 @& n& {' e! F, p+ e4 u( c0 ^     23*26 ≡ 0 (mod 299)   9 e! q9 ?8 L1 I+ h# F
         (23,299)=23   (26,299)=13      299=13*23
    0 @" |3 d, C3 r1 I2 \+ U9 w& D: |0 a9 U: P6 n
       分解方法:  设n为奇合数,  a^2 ≡ b (mod n)  , 如果 b=a+i(i+1) (i ≥ 0 )  , 则可得到:& F: a! k; \  R# v
          a^2 ≡ b (mod n)  =>
    , n7 P0 e9 V; [. B! K- `- b     a^2-b-i(i+1) ≡ 0 (mod n)  => ! C/ e$ A1 ^" x! L, F. w( g
         (a-(i+1))(a+i) ≡ 0 (mod n)
    ' [1 b; k$ k- b' }. P) c# d     (a-(i+1),n)>1   (a+i , n)>1    即可分解n
    & I3 [( s; M3 m) K; d$ ?- ]' X$ z0 |+ F* x( _" Q
       2、分解方法的另一个解释
    % ^4 k3 i$ i1 P    设n为奇数, a^2 ≡ b(mod n),  如果m=a, 则由(1-1)公式得: : P# J0 w* F1 p  c6 L" _
         (1/2 -a)^2  ≡ 1/4 +a^2-a (mod n)   =>
    6 b- _; K2 a! G" X; V       (1/2 -a)^2  ≡ 1/4 +b-a (mod n)    (2-1) 7 e8 Q( ]4 A1 }. }4 o) t; L- F
         
    * u4 F" `! c$ _* @0 u7 L     ① n=4k-1 , 2-1式得:
    ' C$ t) y3 V) g( c3 x     (2k-a)^2 ≡ k+b-a(mod n)     (2-2)
    / f/ H2 V+ E  _+ q( w1 Q5 j     ① n=4k+1 , 2-1式得:: v$ B. Y& o3 y2 H9 @+ z
         (2k+1-a)^2 ≡ n-k+b-a (mod n)   (2-3)
      [, e& }/ ?- |6 O5 ^# k* s, v+ ?/ ]% }6 p& h6 s; A( n
       从(2-1(式, 可知二次剩余的计算,  在[1,1/4]范围内, 计算出[1,n-1]的二次剩余值.
    7 A8 q1 u) l, S( B' d& j   在例2中, 按(2-2)式的计算, 可得:
    9 q% _3 @3 y7 D1 v1 N7 E* A    (150-25)^2 ≡ 75+27-25 (mod 299) =>  125^2 ≡ 77 (mod 299)  * G1 W/ b* U0 P, _
        所以, a^2 ≡ b (mod n)  ,如果b=a+i(i+1) ,其相对1/2的剩余值在后序序列上.6 _/ g( p" M, d

    ! i9 w* j4 i1 N' w8 I* V+ N" g: A# N 三、1/j (j >=3)的计算方法
    : Y6 b0 O( q# P+ B0 @: [. V5 x5 q  上面的是计算 1/2, 即j=2, 如果j>2时,  有如下的1/j计算方法:0 W  N! s* f- f! x. ^) O4 h
       (1/j ± ij)^2 = (ij)^2 ± 2i + (1/j)^2 (i >= 1 ) (j ≥3)   (3-1)
    ( ?6 v! B# g7 E% P7 P, ]
    8 M- [; i) S- q: k# B   而对于\frac{1}{j}相邻, 有两种计算, . f: w7 \; t; y, M8 A
        1)  1/j    1+1/j  2+1/j ... t+1/j    (t<j)  + A* R" x% O% @2 T* {4 X
        2) t-1/j ... 1-1/j  1/j  1+1/j ...  t+1/j   (t < j/2)  
    5 e; C' _" r; p8 j3 V    t+1/j= (1+tj)/j = m/j ,  m=1+tj
    # n/ v1 v1 B6 X% `. _
    . c. @1 V2 k% u" Z& q    按m/j , (3-1)式变成:
    ' Z/ {' |' Y+ O6 d  n  u. _    (m/j± ij )^2 = (ij)^2 ± 2mi + (m/j )^2  (i≥ 1 ) (j ≥ 3)   (3-2)
    0 m8 L* `  u+ s8 K3 q9 V% Z; n
       例3: n=299    \frac{1}{3} ≡ 100 (mod 299)   100^2 ≡ 133 (mod 299)  
    4 Z' U5 a& u$ x, B* a  n   (100-3)^2 ≡ 3^2-2+133  (mod 299)    =>  97^2 ≡ 140  (mod 299)
    " Q8 A! ?, x. ^; y5 p: D) ~9 B/ E  t   (100+3)^2 ≡ 3^2+2+133  (mod 299)    =>  103^2 ≡ 144  (mod 299)
    4 Y' j' d: {9 F- M8 s7 K. e8 @   1+1/3=4/3 ≡ 1+100=101 (mod 299)     101^2 ≡ 35 (mod 299)
    + [& ]8 Z9 `: z, }# N. b$ a   (101-3)^2 ≡ 3^2-2*4+35  (mod 299)    =>  98^2 ≡ 36  (mod 299)
    . r: e; t6 D. w; J, Y: L   (101+3)^2 ≡ 3^2+2*4+35  (mod 299)    =>  104^2 ≡ 52  (mod 299)
    - _7 c2 b! y5 h% F, ~( m   1-1/3=-2/3 ≡ 1-100=-99 (mod 299)     99^2 ≡ 233 (mod 299)  
    3 L) N, E6 h: _: k/ C$ T# s   (99-3)^2 ≡ 3^2-2*(-2)+233  (mod 299)    =>  96^2 ≡ 246  (mod 299) ; m7 E: K! F$ i3 g: p: K. q
       (101+3)^2 ≡ 3^2+2*(-2)+233  (mod 299)    =>  102^2 ≡ 238  (mod 299)   ! n$ X6 v% n' V6 {$ ^
       按2+1/3也能得到相同结果,这里不在验证.5 `! d- G# D" x6 g. t/ m
    $ H9 H/ T5 t7 E
       当然如果j=2s, 即为偶数, 可以计算一半的值, (3-2)式得  :
    & M8 b6 ?9 m5 t4 G, [  v    (m/j ± i*s)^2=(is)^2±mi+(m/j)^2   (i ≥ 1)   (j ≥ 3)   (3-3) ' b# o9 _9 H/ ~2 o2 l- w2 o' J% j
      更一般的公式: 当为 g/j    g <j/2  , (g, j)=1, 这里就不再给出.1 ~* [( e3 [" R. [* ~. e  h/ z

    ' F6 V; i1 B: k9 U9 [! k

    二次剩余值的关联计算(上).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 12:47 , Processed in 0.447459 second(s), 53 queries .

    回顶部