设模数$p=k*i+r(r<i,i<p,k\in \operatorname{N*})$，则
$$k*i+r\equiv 0(mod ~p)$$
同乘$i^{-1}*r^{-1}$，有
$$i^{-1}\equiv -k*r^{-1}(mod~ p)$$
$$inv[i]\equiv -\left\lfloor\frac{p}{i}\right\rfloor *inv[p ~mod ~i](mod~ p)$$
最后一次更新于2020-02-17
设模数$p=k*i+r(r<i,i<p,k\in \operatorname{N*})$，则
$$k*i+r\equiv 0(mod ~p)$$
同乘$i^{-1}*r^{-1}$，有
$$i^{-1}\equiv -k*r^{-1}(mod~ p)$$
$$inv[i]\equiv -\left\lfloor\frac{p}{i}\right\rfloor *inv[p ~mod ~i](mod~ p)$$
0 条评论