数论之同余

  1. 云栖社区>
  2. 博客>
  3. 正文

数论之同余

feilengcui008 2016-06-04 09:02:46 浏览587
展开阅读全文
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/feilengcui008/article/details/51582198

基本性质

后面两个贼有用

  • ab(modm)a=km+b
  • ab(modm)cd(modm)a+cb+d(modm)acbd(modm)
  • (a+b)modm=((amodm)+(bmodm))modm
  • abmodm=((amodm)(bmodm))modm

一些题目的分析与证明

  • 大整数的求余与二进制字符串模3余数

    • 证明(直接证明通用x进制的字符串对整数m求余)
      A1A2A3...An
      S=A1xn1+A2xn2+...+An
      Smodm=(A1xn1+A2xn2+...+An)modm
      =((A1xn1+A2xn2)modm+(A3xn3...+An)modm)modm
      =((A1x+A2)xn2modm+(...)modm)modm
      =(((A1x+A2)modm)(xn2modm)modm+(...)modm)modm
      temp=(A1x+A2)modm
      =((temp(xn2modm))modm+(...)modm)modm
      =(((tempmodm)(xn2modm))modm+(...)modm)modm
      =((tempxn2)modm+(...)modm)modm
      =(tempxn2+A3nn3+...+An)modm

    • 由此我们可以看到递推公式temp=(tempx+Anext)modm

  • 二进制字符串模3余数,同上

  • 同余幂,求bnmodmbm
    将n表示成二进制串A1A2…An,则bn=b2A1(n1)+...
    mod
    t=(tpower)modm
    power=b2Ai(ni)modmim

同余的其他一些应用

  • 哈希
  • 生成伪随机数(比如线性同余xn=(xn1k+c)modm)
  • 加密

网友评论

登录后评论
0/500
评论
feilengcui008
+ 关注