乘法逆元及其应用

2020-06-02 14:39:02 浏览数 (1)

  满足 a * k ≡ 1 (mod p) k 叫做 a关于p的乘法逆元。另一种表达方法是 k ≡ a-1 (mod p)

逆元在密码学中有广泛应用,AES密码体系的字节替代就是运用了逆元。(不知道说的smg)

应用:

我们知道(a b)%p=(a%p b%p)%p

    (a*b)%p=(a%p)*(b%p)%p

而求(a/b)%p时,可能会因为a是一个很大的数,不能直接算出来,却又不能(a/b)%p=(a%p/b%p)%p。

但是可以通过 k ≡ b-1 (mod p) 

a / b

= a * b-1 (mod p )

= (a mod p ) * (b-1 mod p ) mod p

= (a mod p ) * (k mod p )  mod p

= a * k mod p

转换为a*k % p 的问题,然后a是一个加减乘的式子,就可以用上面两个取余公式了。

0 人点赞