QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2976|回复: 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
            二次剩余值的关联计算(上)
    0 r% K7 c1 D, Q5 K- ]2 G% d$ L
    1 i5 U+ p% T% i. A( s0 E 一、 二次剩余中\frac{1}{2} 相关值的计算:
    ) l8 w$ h" B9 T) o: o( h# f- p# Q   对于完全平方公式:0 I+ u0 F6 ^+ n' k
       (1/2 -m)^2  = 1/4 -m+m^2 = 1/4 +m(m-1)   (m≥1)  (1-1)/ R  P; u% F5 m& Z2 M% M9 ?
    " i" |3 g$ B% U
        在n为奇数时, 上式的同余可以分为:
    " n3 M3 a& _9 u3 @1 N7 U+ X2 Q    ① 当n=4k-1时,对(1-1)求同余得: - Q0 w' B  s1 d0 F( N  B! c5 s; {
        (1/2-m)^2  ≡ (2k-m)^2 ≡ k+m(m-1) (mod n)    (1-2)
    ; h. s$ h2 D" G6 Z9 ^6 E) q    ② 当n=4k+1时, 对(1-1)求同余得:
    * s4 D4 Z9 i2 ?& A+ R    (1/2 -m)^2  ≡ (2k+1-m)^2 ≡ -k+m(m-1) ≡ n-k+m(m-1) (mod n)    (1-3)7 b4 E  ?6 [: C2 f5 u

      j5 |# o2 X" R  为以后叙述方便,我们对 1/2-1  1/2-2  ...  1/2-m (m >=1)  这类数称为二次剩余的后序序列, 即1/2  减小的方向的数列.7 J- p+ Z, |+ o: j
    / O1 s2 D) b0 G
      二次剩余后序序列的二次剩余值有个特点, 与k(k>0)值相关, 是k值与两个连续整数积的和,与k值同奇同偶。/ d/ g/ s) `5 q+ u
      如n=299=4*75-1    k=75    2k=150 , 二次剩余后序序列为:
    3 M: s$ B6 k6 D5 V7 A4 @   (150-1)^2 ≡ 75+1*(1-1) ≡ 75 +0 ≡ 75 (mod 299)  =>  149^2 ≡ 75 (mod 299)  % T$ e% t5 s4 P4 c- y8 a
       (150-2)^2 ≡ 75+2*(2-1) ≡ 75 +2 ≡ 77 (mod 299)  =>  148^2 ≡ 77 (mod 299)  7 r3 @7 l6 N% {7 P
       (150-3)^2 ≡ 75+3*(3-1) ≡ 75 +6 ≡ 81 (mod 299)  =>  147^2 ≡ 81 (mod 299)
    ; k6 \% Y4 L6 e9 R: r4 i! ]0 n) J: t- i/ i+ q8 M# T5 w* _( z
      .' R7 F. g' H/ o1 b
      .
    8 X! t  c* y8 v2 u$ U   根据后序序列,可以得到一个分解整数的方法:2 l6 |1 m3 d% k# E' r8 _2 \
       设n为奇合数, 如果 c^2-k=m(m-1)  m>0  => (2k-m)^2 ≡ c^2 (mod n)  , 或者 4 y. v$ j# L. M8 U# X
        c^2-k=m(m-1) => 4c^2-4k+1=4m(m-1)+1 => (2c)^2 ≡ (2m-1)^2 (mod n)  ! a) ?* q. B* O. I3 a
       上述等式,由费马分解即可得到n的因子, 不过效率较低.- C; Z1 {5 c* o) c! d8 c* H! r9 [
        例1: n=299-4*75-1 ,  k=75, |6 Q' O( |) a
          根据后序序列,大于75且与75同奇同偶的完全平方:9^2-81
      s: C. h6 v3 K9 C4 I1 Y, \      81-75=6=2*3 为连续两个整数积,在后序序列上
    3 h  N& ^$ z- b: S: y$ a, W      ∴ (150-3)^2≡81 (mod 299)  => 147^2≡81 (mod 299)
    $ C2 @* e- M$ Q$ n& b" W      或者 (2*9)^2≡(2*2+1)^2 (mod 299) => 18^2≡5^2(mod 299)- e9 b+ E1 j8 U& g3 w& {
    & N7 r9 x" X% z9 a" R8 K! v1 T
    二、连续两个整数积的分解方法
    : t2 x" P6 u2 V6 `4 A) _5 `: D   1、分解方法介绍: K, k% d2 J5 W3 l8 {
       例2: n=299=4*75-1$ b. ]2 j& Q' t* D7 A1 }$ \
          25^2 ≡ 27 (mod 299)   => " |6 [# q! x7 X& G, X) Z( c
         25^2 ≡ 25+2 (mod 299)  =>  ; ^' Y7 V- U2 j/ m- N% T: f( }  ~
         25^2-25-2 ≡ 0 (mod 299) =>  
    ; b' [: s& A# i2 L8 c9 N     (25-2)(25+1) ≡ 0 (mod 299) =>
    ; ~; J/ C' D& L     23*26 ≡ 0 (mod 299)   
    8 _* k4 a0 @/ U9 K6 H2 M9 R     (23,299)=23   (26,299)=13      299=13*235 i9 ?6 P: c$ z! `+ e6 {& ^4 p
    $ P- ^' ]: W7 e7 y: x, S  K
       分解方法:  设n为奇合数,  a^2 ≡ b (mod n)  , 如果 b=a+i(i+1) (i ≥ 0 )  , 则可得到:
    5 n' L0 m' ]8 @: J3 ]8 X8 }      a^2 ≡ b (mod n)  => 9 c% p6 v3 d% f5 y! }
         a^2-b-i(i+1) ≡ 0 (mod n)  =>
    4 ]. ?! Q9 ~: l) o- P2 j     (a-(i+1))(a+i) ≡ 0 (mod n) 4 K- z4 Z: A0 C
         (a-(i+1),n)>1   (a+i , n)>1    即可分解n, S+ J( M4 n7 b) G8 E9 _$ p

    ; e6 S3 f9 O# k   2、分解方法的另一个解释
    1 C  O, m9 F' y. q# n5 T    设n为奇数, a^2 ≡ b(mod n),  如果m=a, 则由(1-1)公式得: - n' V; [" j' G6 Z# v0 p% s, i$ L
         (1/2 -a)^2  ≡ 1/4 +a^2-a (mod n)   =>
    : O4 o2 U# H' z1 [/ R       (1/2 -a)^2  ≡ 1/4 +b-a (mod n)    (2-1)
    ; e: i* r1 t) X2 J- D5 E3 a     * B# j8 Q' p# a2 c' K4 C3 j9 l
         ① n=4k-1 , 2-1式得:
    + d/ B! T4 U1 n! W9 X  X     (2k-a)^2 ≡ k+b-a(mod n)     (2-2)! Y. r' U4 q. _1 W* U
         ① n=4k+1 , 2-1式得:; Z+ K1 u3 e4 P3 F% H
         (2k+1-a)^2 ≡ n-k+b-a (mod n)   (2-3)& G0 g% U& p6 E4 }) N
    - w2 O/ Y$ |5 i3 l3 c# e
       从(2-1(式, 可知二次剩余的计算,  在[1,1/4]范围内, 计算出[1,n-1]的二次剩余值. 7 v3 n0 Q% N8 t2 m& Z! M
       在例2中, 按(2-2)式的计算, 可得:
    ( G* z- {! h4 Y    (150-25)^2 ≡ 75+27-25 (mod 299) =>  125^2 ≡ 77 (mod 299)  % n1 O7 _5 M7 }* y% k9 _' |: m
        所以, a^2 ≡ b (mod n)  ,如果b=a+i(i+1) ,其相对1/2的剩余值在后序序列上.
    # y: T$ f# m) N
    3 f' J0 N6 O' `5 Y: \5 J 三、1/j (j >=3)的计算方法
    ' D, p* P. b4 m; \  上面的是计算 1/2, 即j=2, 如果j>2时,  有如下的1/j计算方法:8 o7 f9 l/ D' B' N0 q
       (1/j ± ij)^2 = (ij)^2 ± 2i + (1/j)^2 (i >= 1 ) (j ≥3)   (3-1): c7 N) B% Z0 M6 }1 }) @; a8 V
    $ R* ^* j: q! S" l# g; R- `: w
       而对于\frac{1}{j}相邻, 有两种计算,
    6 ~9 V: T3 u& d, ~7 v    1)  1/j    1+1/j  2+1/j ... t+1/j    (t<j)  ' u& f5 X- G/ l  {1 L! _
        2) t-1/j ... 1-1/j  1/j  1+1/j ...  t+1/j   (t < j/2)  
    , @2 H9 s7 w0 P, ?% ?    t+1/j= (1+tj)/j = m/j ,  m=1+tj
    & {3 p& Q5 J) [# \4 Y* Y. R$ ]# y4 ]
        按m/j , (3-1)式变成: 3 p7 v* m7 w8 ~0 {* g8 ?7 _
        (m/j± ij )^2 = (ij)^2 ± 2mi + (m/j )^2  (i≥ 1 ) (j ≥ 3)   (3-2)! \' v2 y% `- ]. V* P2 j
    & G& U- w) D( k  {+ ~
       例3: n=299    \frac{1}{3} ≡ 100 (mod 299)   100^2 ≡ 133 (mod 299)  7 g- G- e; v) I3 N# Q
       (100-3)^2 ≡ 3^2-2+133  (mod 299)    =>  97^2 ≡ 140  (mod 299)
    : q  u1 v# N$ k8 F2 t   (100+3)^2 ≡ 3^2+2+133  (mod 299)    =>  103^2 ≡ 144  (mod 299)
    $ A# T' U$ Y  j7 [   1+1/3=4/3 ≡ 1+100=101 (mod 299)     101^2 ≡ 35 (mod 299)3 q0 z! b! ~5 y! d8 J5 d
       (101-3)^2 ≡ 3^2-2*4+35  (mod 299)    =>  98^2 ≡ 36  (mod 299)
    % j+ a; u1 O6 s) F' V# @  |   (101+3)^2 ≡ 3^2+2*4+35  (mod 299)    =>  104^2 ≡ 52  (mod 299)
    6 a! ]+ i2 f. v% J. r   1-1/3=-2/3 ≡ 1-100=-99 (mod 299)     99^2 ≡ 233 (mod 299)  ; w  e2 _/ a- F. `9 q) {5 z
       (99-3)^2 ≡ 3^2-2*(-2)+233  (mod 299)    =>  96^2 ≡ 246  (mod 299)
    # H7 T/ v! Z2 B" |$ Q8 v' o   (101+3)^2 ≡ 3^2+2*(-2)+233  (mod 299)    =>  102^2 ≡ 238  (mod 299)   
    0 J9 ?* m2 w( ?   按2+1/3也能得到相同结果,这里不在验证./ r: I- H0 v! E$ ?6 Z/ B+ a/ W

    + n& v# D% ?* b8 Q# n* p; ^   当然如果j=2s, 即为偶数, 可以计算一半的值, (3-2)式得  :
    0 V. @- @& h. f3 x2 g    (m/j ± i*s)^2=(is)^2±mi+(m/j)^2   (i ≥ 1)   (j ≥ 3)   (3-3)
    * d  p, v: I& ^2 u$ i  更一般的公式: 当为 g/j    g <j/2  , (g, j)=1, 这里就不再给出.
    ( b1 I1 R9 x% g6 v) P, v! v2 S+ G; \" F( O$ a

    二次剩余值的关联计算(上).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-6-9 06:11 , Processed in 0.381577 second(s), 53 queries .

    回顶部