QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2645|回复: 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
            二次剩余值的关联计算(上)
    ( D4 L* D( b. D5 [$ o) u1 ]" |3 l1 Y2 r* q+ X4 R) C4 Y* f
    一、 二次剩余中\frac{1}{2} 相关值的计算:* V; I5 \; a2 a# O, `* [1 \
       对于完全平方公式:9 L1 m/ b2 n) j$ t+ j
       (1/2 -m)^2  = 1/4 -m+m^2 = 1/4 +m(m-1)   (m≥1)  (1-1)
    5 A$ n1 c! y" ^  e$ e+ T2 d6 |4 @: y4 E, c! t
        在n为奇数时, 上式的同余可以分为:. {! k# P, x$ y9 @8 z
        ① 当n=4k-1时,对(1-1)求同余得: 8 h9 f1 s( w3 Y0 T" ]
        (1/2-m)^2  ≡ (2k-m)^2 ≡ k+m(m-1) (mod n)    (1-2)* O3 y1 Y) u7 ], \7 ?# f. m
        ② 当n=4k+1时, 对(1-1)求同余得: 7 l/ g4 i- ^2 ?
        (1/2 -m)^2  ≡ (2k+1-m)^2 ≡ -k+m(m-1) ≡ n-k+m(m-1) (mod n)    (1-3)0 n- r2 Q8 G# g

      b2 w2 A; S" T: g  为以后叙述方便,我们对 1/2-1  1/2-2  ...  1/2-m (m >=1)  这类数称为二次剩余的后序序列, 即1/2  减小的方向的数列.1 R. K3 l& M- m# [$ B/ F5 ^7 d
    ) e* s% `5 ~& J) l4 R- r
      二次剩余后序序列的二次剩余值有个特点, 与k(k>0)值相关, 是k值与两个连续整数积的和,与k值同奇同偶。( k& e, U' j( s2 \6 w1 Z$ ^
      如n=299=4*75-1    k=75    2k=150 , 二次剩余后序序列为:2 c* |; L; c# n) a/ a, d. W
       (150-1)^2 ≡ 75+1*(1-1) ≡ 75 +0 ≡ 75 (mod 299)  =>  149^2 ≡ 75 (mod 299)  
    ; o- V6 [; j" @* a   (150-2)^2 ≡ 75+2*(2-1) ≡ 75 +2 ≡ 77 (mod 299)  =>  148^2 ≡ 77 (mod 299)  
    & h% t7 Q6 D5 V8 n   (150-3)^2 ≡ 75+3*(3-1) ≡ 75 +6 ≡ 81 (mod 299)  =>  147^2 ≡ 81 (mod 299)
    $ c# G2 r# D0 L4 K8 }/ z0 E4 W
    / |* K0 V( m+ Z1 I' P  .
    $ L5 D8 c" w3 T- F* y  .
    0 F/ [5 G% B/ `& d3 a' F- Z0 w   根据后序序列,可以得到一个分解整数的方法:) P+ q' `9 l* C/ ]2 C6 M
       设n为奇合数, 如果 c^2-k=m(m-1)  m>0  => (2k-m)^2 ≡ c^2 (mod n)  , 或者 ; m8 h5 O3 Q; M" @# p5 j! r
        c^2-k=m(m-1) => 4c^2-4k+1=4m(m-1)+1 => (2c)^2 ≡ (2m-1)^2 (mod n)  
    . O6 K0 L( [2 C. a' Q+ v9 j+ G   上述等式,由费马分解即可得到n的因子, 不过效率较低.
    5 C- @4 W- P, Q: y* }: N    例1: n=299-4*75-1 ,  k=751 t, q* R! H$ ?: @/ Z: H1 u
          根据后序序列,大于75且与75同奇同偶的完全平方:9^2-81
    $ Y0 A4 e* K3 E* J  h      81-75=6=2*3 为连续两个整数积,在后序序列上+ S. b3 F7 U0 ~, L4 }2 W6 @
          ∴ (150-3)^2≡81 (mod 299)  => 147^2≡81 (mod 299)
    . j( W/ J1 c9 n; T      或者 (2*9)^2≡(2*2+1)^2 (mod 299) => 18^2≡5^2(mod 299)
    $ l8 _- F" W* n5 e' M0 W# y- v' }/ J6 o0 z1 L% _* k  g1 ^, L
    二、连续两个整数积的分解方法
    9 h3 p4 `7 G: y0 |   1、分解方法介绍
    7 q  z) f- h4 t. M: F2 ?; R' ?   例2: n=299=4*75-1
    1 H+ c1 D7 r% B      25^2 ≡ 27 (mod 299)   =>
    8 O( `* ]8 B- Q; `     25^2 ≡ 25+2 (mod 299)  =>  4 T+ n3 j0 G3 q# @8 P2 l6 W
         25^2-25-2 ≡ 0 (mod 299) =>  
    . ~8 Y4 _4 b6 e7 O     (25-2)(25+1) ≡ 0 (mod 299) =>
    ) ]& {& J9 p/ B7 o4 `+ }% i' a( P     23*26 ≡ 0 (mod 299)   
    2 @" i& k9 V) L' S% i# m     (23,299)=23   (26,299)=13      299=13*23
    7 u) L) R3 {4 o) u2 o0 u0 x* ~
    - [4 q! r7 |. I+ `/ ]% u" c   分解方法:  设n为奇合数,  a^2 ≡ b (mod n)  , 如果 b=a+i(i+1) (i ≥ 0 )  , 则可得到:
    5 {! k8 b9 I, y. l; j# D      a^2 ≡ b (mod n)  =>
    8 K8 ?. a- ~& s3 M     a^2-b-i(i+1) ≡ 0 (mod n)  =>
    & w# |* F, L2 L8 A     (a-(i+1))(a+i) ≡ 0 (mod n) . o. N1 u' y1 k6 R, s9 T
         (a-(i+1),n)>1   (a+i , n)>1    即可分解n
    2 U/ h6 G: V7 ~4 C6 s3 r$ J" a8 d. [* O% X/ r7 g
       2、分解方法的另一个解释
    % h0 R  x' p0 c9 T3 f& R    设n为奇数, a^2 ≡ b(mod n),  如果m=a, 则由(1-1)公式得: # i( k5 f4 X: _
         (1/2 -a)^2  ≡ 1/4 +a^2-a (mod n)   => % x/ i3 L: E6 v/ ~+ t% X3 ^3 t
           (1/2 -a)^2  ≡ 1/4 +b-a (mod n)    (2-1) ' |6 Q3 E7 L9 F) U! `
         5 J& p* C, E# s0 l: g% y, F' s2 s
         ① n=4k-1 , 2-1式得:+ Z, j/ Z7 F( y
         (2k-a)^2 ≡ k+b-a(mod n)     (2-2)
    " [' }3 a6 _. i7 ^9 h     ① n=4k+1 , 2-1式得:
    * c, M0 Z- T$ j     (2k+1-a)^2 ≡ n-k+b-a (mod n)   (2-3)5 |+ H4 o  s- u$ o1 _. m

    $ p" p! h% w- V  w9 F8 v( m4 v   从(2-1(式, 可知二次剩余的计算,  在[1,1/4]范围内, 计算出[1,n-1]的二次剩余值.
    5 K0 {; F6 ?0 B( Q   在例2中, 按(2-2)式的计算, 可得: 0 ^0 M' ^$ ]3 Z& C8 i
        (150-25)^2 ≡ 75+27-25 (mod 299) =>  125^2 ≡ 77 (mod 299)  
    4 N1 p: x9 C) T    所以, a^2 ≡ b (mod n)  ,如果b=a+i(i+1) ,其相对1/2的剩余值在后序序列上.
      }9 M# _' E( J3 @1 Z
    7 @$ p+ N' P4 R  X7 W  u- F 三、1/j (j >=3)的计算方法
      V( b3 A# P+ C/ L- d1 _  上面的是计算 1/2, 即j=2, 如果j>2时,  有如下的1/j计算方法:7 z9 i+ j: L  f: F
       (1/j ± ij)^2 = (ij)^2 ± 2i + (1/j)^2 (i >= 1 ) (j ≥3)   (3-1)9 t5 S8 q+ Z2 X/ y2 a# u0 r' Z

    , l- s6 J7 {! q! o   而对于\frac{1}{j}相邻, 有两种计算, # H9 q$ X0 R% h
        1)  1/j    1+1/j  2+1/j ... t+1/j    (t<j)  0 n! x' E3 U3 z" {- F$ ^% p
        2) t-1/j ... 1-1/j  1/j  1+1/j ...  t+1/j   (t < j/2)  9 I) p" R5 [7 M
        t+1/j= (1+tj)/j = m/j ,  m=1+tj
    + U  S& p# a( }$ Z! q( P. Z8 X9 r; @, J" C; ?
        按m/j , (3-1)式变成: ' `  J$ r) z3 e
        (m/j± ij )^2 = (ij)^2 ± 2mi + (m/j )^2  (i≥ 1 ) (j ≥ 3)   (3-2)
    + k7 y9 q9 j/ ~
    - i$ \; n1 p6 X% Z5 d- e   例3: n=299    \frac{1}{3} ≡ 100 (mod 299)   100^2 ≡ 133 (mod 299)  8 z7 U6 F' l+ ?* j9 _3 n
       (100-3)^2 ≡ 3^2-2+133  (mod 299)    =>  97^2 ≡ 140  (mod 299)
    3 T* Q( C6 a( F$ [  R! @   (100+3)^2 ≡ 3^2+2+133  (mod 299)    =>  103^2 ≡ 144  (mod 299)
    ' W# t. N5 q+ e( n" _0 U$ a   1+1/3=4/3 ≡ 1+100=101 (mod 299)     101^2 ≡ 35 (mod 299)7 m: Y+ E* h. S: f1 E
       (101-3)^2 ≡ 3^2-2*4+35  (mod 299)    =>  98^2 ≡ 36  (mod 299)
    1 w" c- v4 ?$ D   (101+3)^2 ≡ 3^2+2*4+35  (mod 299)    =>  104^2 ≡ 52  (mod 299) 4 K/ ]1 ~* @6 c2 _
       1-1/3=-2/3 ≡ 1-100=-99 (mod 299)     99^2 ≡ 233 (mod 299)  
    7 Z8 e# B( x8 \4 R" n) G+ Y9 B   (99-3)^2 ≡ 3^2-2*(-2)+233  (mod 299)    =>  96^2 ≡ 246  (mod 299) 0 j; v, w7 a2 m8 _3 o5 Z' Y9 X
       (101+3)^2 ≡ 3^2+2*(-2)+233  (mod 299)    =>  102^2 ≡ 238  (mod 299)   0 x4 t! E! r/ S! _8 b
       按2+1/3也能得到相同结果,这里不在验证.' W' h$ f5 R0 ~9 o7 R6 ?7 Q: N: {
    ) h/ F) _8 [5 V0 d" s
       当然如果j=2s, 即为偶数, 可以计算一半的值, (3-2)式得  :
    9 D5 Y1 s$ T# i* A- s2 o# Z    (m/j ± i*s)^2=(is)^2±mi+(m/j)^2   (i ≥ 1)   (j ≥ 3)   (3-3)
    + ^  m! P& W; e% L/ S3 ^  更一般的公式: 当为 g/j    g <j/2  , (g, j)=1, 这里就不再给出.+ f/ l' U8 g' L' E

    6 N  u3 Y* \9 w8 ^- w

    二次剩余值的关联计算(上).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, 2025-11-7 16:41 , Processed in 0.746708 second(s), 52 queries .

    回顶部