关于第一次office hour对于s为什么模p-1的数学解释。

[Xor0v0]

s为什么模 p-1 数学解释

对于 $s=r+bx$ ，s值可能会变得很大，这样计算模幂效率是很低的，那么我们当然想把指数(幂)降低一点，于是就有下面：

• 首先A和p互素，根据费马小定理有： $A^{p-1}\equiv 1\mod p$.
• $s \equiv s' \mod (p-1)$，当然也可以写作 $s'\equiv s\mod (p-1)$
• $A^{s\mod (p-1)}=A^{s'+c*(p-1)}=A^{s'}A^{c*(p-1)}$
• 于是 $A^{s\mod (p-1)}\equiv A^{s'}\mod p$

由此，我们成功利用费马小定理将大指数模幂计算量降低下来。