• 周五. 12月 2nd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

【数论】求幂大法

admin

11月 28, 2021

求幂大法是可以对指数取模 而结果不变的快速求幂的方法:

A^b=A^(b mod phi(B)+phi(B)) (mod B) (条件:b>=phi(B))

证明:

我们知道A^i mod m 会存在循环节 在循环节前可能存在一段不循环的数

假设前r 为不循环的数 s为循环节的长度

也就是A^(r+i)=A^(r+i+s) (i>=0)

要证明上面求幂大法 就是要证明 A^b mod B 的r>=phi(B) 且s|phi(B)

也就是A^b mod B 当b<=phi(B)时开始循环 且循环的长度为phi(B)的因数

设A=p1^a1*p2^a2…pn^an

   rj、sj为(pj^aj)^i mod B 的开始循环的数和循环节长度

   rj’、sj’为pj^i mod B 的开始循环的数和循环节长度

显然

1、只要所有rj<=phi(B) && sj|phi(B) 则得证(感性理解一下 A的循环节开始点为rj的最大值 而A的循环节长度为所有sj的lcm)

2、rj'<=rj 且 sj’|sj

需证明rj<=phi(B) 且 sj’|phi(B)

对于某个质数p 设 B’=B/(p^r0) 满足(B’,p)=1

p^r=p^(r+s) (mod B)

->B|p^(r+s)-p^r

->B’*(p^r0)|p^r*(p^s-1)

因为(p^r0,p^s-1) 所以r至少要取r0 由定义 r=r0

所以B’|p^s-1

->p^s=1 (mod B’)

由欧拉定理可知 s|phi(B’)

又因为phi具有积性 所以phi(B’)|phi(B)

所以s|phi(B)

再证明r<=phi(B)

这里p^r|B 且(p^r,B)=1 所以phi(B)=phi(p^r)*…

所以phi(B)>=phi(p^r)

phi(p^r)=(p-1)*p(r-1)

由于p为质数 不难发现(p-1)*p^(r-1)>r

所以r<=phi(B) 得证

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注