乘法逆元

①乘法逆元的定义即应用

     ①定: a*b≡1( mod p),我们称b为a在 mod p意义下的逆元,记作 inv[ a ]=b.

   ②应:介绍一种.对于取摸运算 ( a / b ) mod p ! =( ( a mod p)/(b modp))mod p,应化为( ( a mod p )*( inv[ b ] mod p ) ) mod p.

②求乘法逆元的三种方法

  ①费马小定理:若 p 为素数,且gcd( a , p )=1,有 a^( p -1 )≡1( mod p).

 我们发现,在满足前面两个条件下,将原公式变形为a*a^( p -2 )≡1( mod p),此时a^( p -2 )即a在 mod p定义下的逆元,快速幂求解.

  ②扩展欧几里得( exgcd ):用于求解 ax+by=gcd( a,b )的一组解.

  前置知识:欧几里得辗转相除求最大公约数

1 int x, y;
2 void gcd(int x,int y)
3 {
4    if(y == 0)
5       return x;
6    else return gcd(y,x%y);             
7 }

 

  个人理解:对于整数x,y,存在最大公约数z,  z | x , z | y , z|( mx + ny), z|( mx - ny).我们不妨设 x=ky+p.所以我们得到x%y = p = x-ky.我们发现x-ky即是( mx -ny)的一种特殊形式,也就是说z | p.可证明 gcd(x,y)=gcd(y,x%y).w我们可以发现x,y都更新过程中,不断向构成的基本元素z靠近.当y=0时,x一定变为了z.

  扩展欧几里得( exgcd )求逆元

  ①联系证明:

    ①a*inv[ a ]≡ 1 ( mod p).

    ②a*inv[ a ] = py+1

    ③a*inv[ a ] - py=1

    ④a*inv[ a ] + py' =1.

    当 gcd( a,p )=1时, a*inv[ a ] + py' =gcd( a, p ), inv[ a ]即为exgcd求得一个解.

  ②求逆元过程证明:

    ①  ax1 + by1 = gcd( a,b ) , bx2 + ( a%b )y2 = gcd( b,a%b).

    ②  gcd( a,b ) = gcd( b,a%b).

    ③  ax1 + by1 = bx2 + ( a%b)y2.

    ④  ax1 + by1 = bx2 +  (a-[a/b]*b)y2.

    ⑤  ax1 + by1 = bx2 + ay2-[a/b]*b*y2.

    ⑥ ax1 + by1 =  ay2 + b( x2-[a/b]y2).

    所以我们推出: x1=y2 , y1=x2-[a/b]y2.我们不断作gcd时,当b=0时,我们令y1=0,x1=1,显然是一组解,回溯即可.

 1 void exgcd(int a,int b)
 2 {
 3     if(!b)
 4     {
 5         x1=1;
 6         y1=0;
 7         return;
 8     }
 9     exgcd(b,a%b);
10     x2=x1,y2=y1;
11     x1=y2;
12     y1=x2-a/b*y2;
13     return;
14 }

   ③线性递推公式.

    推导:① [ p/i ] * i = p -p mod i.

       ②  [p/i ] * i = - p mod i (模数出现负数的等价 )

       ③  -inv [ p mod i ] * [ p/i ] = inv[ i ] (同乘 inv[ i ]*( -inv[ p mod i ] ),记住这是在mod p意义下的).

      p mod i < i,从小到大递推即可,初始值 inv[ 1 ]=1.

  ④补充:Miller Rabin判断素数.

      a^(p-1) ≡ 1 (mod p) ,逆用费马小定理,看p是不是素数.

      

 

  

  

 

上一篇:.c 和 .cpp 的区别


下一篇:线性二次型控制器(LQR)——轨迹跟踪器