首页
社区
课程
招聘
[原创]整数分解随笔(六)
发表于: 2017-5-26 19:44 5975

[原创]整数分解随笔(六)

2017-5-26 19:44
5975

                整数分解随笔(六)


本次文中未注明处,n≥3,且为奇数。

一、平方剩余相邻两数除法的唯一性及互逆间的相互相关性:


  1、相邻两数除法的唯一性

      在随笔word版中,曾经推出相邻两数平方剩余除法的一个公式,这里把公式重新整理一下。

     设a^2≡b(mod n),根据公式可知:

      c≡(a-1)/(b-1) (mod n)     =>

      c^2≡d,(c+1)^2≡bd (mod n)

      即根据a^2≡b(mod n)可以反推出该平方剩余是由哪两个相邻数相除得到,其中a、b、c∈(1,n-1),而且是唯一的。

    以下证明唯一性:

    设a^2≡b(mod n),(c+1)/c≡a(mod n),如果不唯一,即还存在另外一个相邻数的平方剩余(d+1)/d≡a(mod n),可得:

    (c+1)/c≡(d+1)/d (mod n)   =>

    c≡d (mod n)

    这里a、b、c、d∈[1,n-1]

    即平方剩余的除法具有唯一性。

    现在再对相邻两数平方剩余的除法进行相应的变化。

    设a^2≡b(mod n),(a+1)^2≡c(mod n),两式相除得:

    ((a+1)/a)^2≡c/b(mod n)    =>

    (1+1/a)^2≡j(mod n)  这里j≡c/b(mod n)

    

   如果两式相乘得:

    (a^2+a)^2≡bc(mod n)     =>

    (a+b)^2≡bc(mod n)

    又∵j≡c/b(mod n)

    ∴上式变为:(a+b)^2≡jb^2(mod n)  =>

       (1+a/b)^2≡j(mod n)

     当然也可以由a^2≡b(mod n)   =>

       a/b≡1/a(mod n),其中(a,n)=1

     得到上面两式是相等的。

     举例说明三个公式:

     例1、60^2≡12(mod 299)

      a≡(60-1)/(12-1)≡59/11≡250(mod 299)

      250^2≡9(mod 299)

      251^2≡108(mod 299)

      其中  9*12≡108(mod 299)


     1+1/a≡60(mod 299)    =>

     a≡1/59(mod 299)        =>

     a≡223(mod 299)

     223^2≡95(mod 299)

     224^2≡243(mod 299)

     其中 95*12≡243(mod 299)


     1+a/b≡60(mod 299)    =>


[招生]科锐逆向工程师培训(2024年11月15日实地,远程教学同时开班, 第51期)

收藏
免费 1
支持
分享
最新回复 (4)
雪    币: 842
活跃值: (487)
能力值: ( LV9,RANK:150 )
在线值:
发帖
回帖
粉丝
2

    二、相邻两平方剩余的乘法
    设a^2≡b(mod  n),(a+1)^2≡c(mod  n),a+b≡d(mod  n),其中d=j(j+1),d^2≡f(mod  n),相邻两平方剩余相乘得:
    (a(a+1))^2≡bc(mod  n)        =>
    (a+b)^2≡bc(mod  n)
    而c≡2a+1+b(mod  n)    代入得:
    (a+b)^2≡b(2a+1+b)(mod  n)      =>
    (a+b)^2≡2ab+b+b^2  (mod  n)
    又∵d=a+b  =>a=d-b      且d^2≡f(mod  n),代入上式得:
    2ab+b+b^2≡f(mod  n)      =>
    b^2-(2d+1)b+f≡0(mod  n)    =>
    b^2-(2j(j+1)+1)b+f≡0(mod  n)    ①
    对于上式,一定有一个已知解,即s^2≡s^2(mod  n),s≤√n,但根据上面一元二次方程在平方剩余中如何求另外一个解,目前不清楚,以下举例说明:
      n=299:
      72^2≡101(mod  299)
      72=8*9  其中一个解为:
      8^2≡64(mod  299),代入①得
      b^2-145b+101≡0  (mod  299)
      当b=64时,上式成立,但另一解d=12也成立,但无法求出。

2017-5-26 19:45
0
雪    币: 842
活跃值: (487)
能力值: ( LV9,RANK:150 )
在线值:
发帖
回帖
粉丝
3

    三、连续两整数之和与之积的性质
      1、相邻两整数之和与n因子的关系
        先看例,再说明。
        例1、n=299=13*23
          6+7=13              11+12=23
          19+20=39      32+33=65
          …
          上述相邻两整数之和皆与299有因子关系,这样的原因是什么?下面来说明:
          设n为奇数(这里只证明n=4k-1,4k+1也是相同情况,不再证明),n=4k-1,a∈[1,(n-1)/2],a^2≡b(mod  n),如果gcd(a,n)>1,则其对称数及其对称数减1之和与n也必有因子。
      证明:    a^2≡b(mod  n)
              其对称数为:  2k-a
              其对称数减1为:  2k-a-1
              相邻两数之和为:2k-a

2017-5-26 19:46
0
雪    币: 2575
活跃值: (502)
能力值: ( LV2,RANK:85 )
在线值:
发帖
回帖
粉丝
4
很专业
2017-5-26 22:24
0
雪    币: 3241
活跃值: (2074)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
5
有所获得
2017-5-27 01:12
0
游客
登录 | 注册 方可回帖
返回
//