都在G中有唯一的逆元a‘,意义下5的乘法逆元是3

 

 

概念:群G中自由2个成分a,都在G中有唯一的逆元a‘,具有性质aa’=a’a=e,个中e为群的单位元。例如:x*b ≡
1(%p) b是x的逆元

图片 1

定义

乘法逆元的定义:若存在正整数a,b,p, 满意ab = 1(mod p), 则称a 是b
的乘法逆元, 或称b 是a 的乘法逆元。b ≡ a-1 (mod p),a ≡
b-1 (mod p)

譬如, 在模7 意义下,3 的乘法逆元是5, 也得以说模7
意义下5的乘法逆元是3。模13含义下5的逆元是8……

应用:在求解除法取模难题(a/b)%m时,大家能够转账为(a%(b∗m))/b, 
可是一旦b一点都不小,则会冒出爆精度难题,所以大家制止使用除法直接总结。 
能够利用逆元将除法转换为乘法: 
假如b存在乘法逆元,即与m互质(充要条件)。设c是b的逆元,即b∗c≡1(modm),那么有a/b=(a/b)∗1=(a/b)∗b∗c=a∗c(modm) 
即,除以三个数取模等于乘以那一个数的逆元取模。

图片 2

存在性

看起来和同余方程很相似(其实上面真的能够用exgcd求的!),在同余方程中

ab ≡ 1(mod p)

若a 与p 互质, 则一定期存款在1个正整数解b, 满意b < p,若a 与p 不互质,
则一定不设有正整数解b.

所以逆元供给a与p互质

求逆元的办法:

焦点供给:(Ar*A2…An)%p,亦即[(A1*A2*…An)/(A1*A2*…Ar-1)]%p,由于A1*A2…An乘积过大,不能求得相除所得的结果

求法

求逆元有三种求法,

1
。逆元求解一般选用扩展欧几里得算法。

大家供给利用乘法逆元(a*k≡1 (mod
p)的k值正是a关于p的乘法逆元),而乘法逆元有如下定理®:(a*k) mod
p结果与(a/b) mod p等价,当中k为b关于p的乘法逆元

一 、扩张欧几里得

能够用扩充欧几里得求,那么是怎么个求法呢?

扩展欧几里得是用来求那样的一组解的:ax+by =
gcd(a,b),求x和y,(求出x后自然理解了y,所以算是求叁个x)。

逆元呢是求那样的二个解:ax ≡ 1 (mod
b),(为了方便清楚,改了弹指间变量名),求x,貌似并从未一小点一般处,那么大家变一下,

ax+by = gcd(a,b),变成 ax+by = c;

ax ≡ 1 (mod b),变成 ax-by = 1;假若将y看成负的,ax+by = 1;

一齐等同嘛,所以直接套用扩大欧几里得求就好了。

代码

图片 3图片 4

 1 #include<cstdio>
 2 
 3 int exgcd(int a,int b,int &x,int &y)
 4 {
 5     if (b==0)
 6     {
 7         x = 1;
 8         y = 0;
 9         return a;
10     }
11     int r = exgcd(b,a%b,x,y);
12     int tmp = x;
13     x = y;
14     y = tmp-a/b*y;
15     return r;
16 }
17 
18 int main()
19 {
20     //gcd(a,p)==1
21     int a,p,r,x,y;
22     while (scanf("%d%d",&a,&p)!=EOF)
23     {
24         r = exgcd(a,p,x,y);
25         printf("%d",(x%p+p)%p);
26     }
27     return 0;
28 }

壮大欧几里得求逆元

2.当m为质数的时候一直用费马小定理,m非质数使用欧拉函数。

而由费马小定理(已知p是质数且gcd(a, p) = 1,则 ap-1 ≡ 1 (mod
p),  所以 a*ap-2 ≡ 1 (mod
p))知,a^(p-2)正是a的逆元了求解,利用高效幂运算总结(补充:亦可用扩充欧几里得求解)

② 、线性求逆元

先核查一下变量名,再改回来ab = 1(mod p),求b

p%a = p-(p/a)*a;  在c++中/为整除。

(p/a)*a = p-(p%a);  换下地点

(p/a)*a = -(p%a);  在模p意义下p能够约掉,能够没有这一步

a = -(p%a)/(p/a);  再换一下职位

a-1 = -(p%a)-1*(p/a);

所以a-1可以用(p%a)-1盛产,所以就足以用递推式来生产1到a的全部数的逆元。

代码

图片 5图片 6

1 int inv[MAXN]; 
2 void INV(int a,int p)//线性求到a的逆元 
3 {
4     inv[1] = 1;
5     for (int i=2; i<=a; ++i)
6         inv[i] = (-(p/i))*inv[p%i]%p; 
7 }

线性求逆元1

上边包车型大巴代码只求三个值的逆元,运用的是上边的姿势

图片 7图片 8

1 int INV(int a)//线性求a的逆元 
2 {
3     if (a==1) return 1;
4     return ((-(p/a)*INV(p%a))%p);
5 }

线性求逆元2

 

只顾具体求a时,应不止对p取mod

叁 、欧拉定理求逆元

欧拉定理:aφ(p) ≡ 1(mod p)

对此自由互质的a,p 恒创制。

欧拉定理用来求逆元用的是欧拉定理的3个测度:
a*aφ(p)-1 ≡ 1(mod p

密切考察,a*b ≡ 1(mod
p),在此处的b不正是上面包车型地铁aφ(p)-1啊?,所以求出aφ(p)-1就好了。

就此我们用便捷幂就足以求出乘法逆元了。

其一办法它需求多算1个欧拉函数,代码那里不再给出。

补充:其实要是p是质数的话,能够用费马小定理,与欧拉定理是全然一样的,费马小定理在p不是质数时,则只可以用欧拉定理。

怎么弄呢?费马小定理 a(p-1) ≡ 1(mod p)
p是质数,且a,p互质,

下一场将方面包车型大巴架子变一下,a*a(p-2) ≡ 1(mod p) ,

再变一下,a(p-2) 
a-1 (mod p)
,然后求出a(p-2)就足以了。

然后再看一下欧拉定理,如果p是质数,φ(p) =
p-1,那么大家求aφ(p)-1,也正是求a(p-2)。和费马小定理是一律的。


#include <stdio.h>
#include <string.h>
#define LEN 100001
#define P 9973

/*注意:转化为s时,必须从1开始,因为如果a=1,那么在做快速幂时,会用到s[-1],造成下标越界*/ 
void Transform(char *s1,int *s){
    int i;
    s[0]=1;
    for(i=1;i<=strlen(s1);i++) //the entire len 
        s[i]=s[i-1]*(s1[i-1]-28)%P;
}

void HashValue(int a,int b,int *s){
    //s[b]*s[a-1]^(p-2) mod p
    //quickmod
    int res,tmp,n;
    n = P-2;
    res = 1; 
    tmp = s[a-1];//s必须从1开始取 
    while(n){
        if(n&1)
            res=(res*tmp)%P;
        n >>=1;
        tmp=(tmp*tmp)%P;
    }

    printf("%d\n",s[b]*res%P);
} 

int main(){
    int n,a,b,i,s[LEN]; 
    char s1[LEN];
    while(scanf("%d",&n)!=EOF){
        getchar();
        gets(s1);
        Transform(s1,s);
        for(i=0;i<n;i++){
            scanf("%d%d",&a,&b);
            HashValue(a,b,s);
        }
    }
    return 0;
}

应用

作者们知道(a+b)%p = (a%p+b%p)%p

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

求(a/b)%p时,只怕会因为a是3个相当大的数,无法一直算出来,也无力回天像上边一样分解。

咱俩得以由此求b关于p的乘法逆元k,k ≡ b-1 (mod p)
,将a乘上k再模p,即(a*k) mod p。其结果与(a/b) mod p等价。

下一场那就成了求a*k%p,然后就足以用那五个公式了。

推而广之欧几里得算法:

 

私家掌握

对于私有的明亮逆元,逆元是在运算除时,可以变成乘,方便总计,像上面一样,a/b(mod
p)就能够变成a*b-1,那也正是逆元的本来面目,必须求在的含义下才有效。

运算a/b时,大家除以b就一定于乘以1/b,那是个分数,不便利计算,所以大家就找到了一个整数,b的逆元,比如计算12/3(mod
7),那是个除法,所以大家能够那样12*(33.33%),纵然是乘法了,可是有分数,所以找2个平头使得x,3x≡1(mod
7),x=5,即模7意义下3的逆元是5,然后大家倍加这么些逆元,12*5 = 60,60 mod
7 = 4,诶,12/3 = 4,相等啊,那正是地点所说的性质,

 

须要 a,m 互素,存在唯一解。

定理 ®的证明:

壮大欧几里得算法。

由:b*k≡1 (mod p)有b*k=p*x+1,k=(p*x+1)/b
将k代入(a*k) mod p,得:
[a*(p*x+1)/b]mod p
=[(a*p*x)/b+a/b]mod p(注意:只要a整除b,自然有(a*p*x)整除b)
={[(a*p*x)/b] mod p +(a/b)} mod p
={[p*(a*x)/b]mod p +(a/b)} mod p,而p*[(a*x)/b] mod p=0

代码:

=(a/b) mod p

 

参考资料:

///利用扩展欧几里得算法求a/b%mod
#define mod 1000003
void ex_gcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x = 1;
        y = 0;
        return ;
    }
    ex_gcd(b,a%b,x,y);
    int t = x;
    x = y;
    y = t - a/b *y;
}
int main()
{
    int n,m,x,y;
    scanf("%d %d",&n,&m);
    ex_gcd(m, mod, x, y);
    x = (x % mod + mod) % mod;///x 为m的逆元;
    printf("%d\n",x * n % mod);
    return 0;
}

  [1]http://blog.csdn.net/nickwong\_/article/details/38797629

 

     
[2]http://www.cnblogs.com/tiankonguse/archive/2012/08/14/2638949.html

费马小定理:

      [3]http://blog.csdn.net/jklongint/article/details/51415402

在p是素数的状态下,对私自整数x都用x^p≡x(mod)p。

 Time:20:48:52 2017-03-01

如果x无法被p整除,则有x^(p-1) ≡1 (mod p).

能够在p为素数的动静下求出叁个数的逆元,x*x^(p-2) ≡
1(mod p),x^(p-2) 即为逆元。

代码:

///求x^p的值
#define mod 1000003
int quick(int n,int p)
{
    int ans = 1;
    n = n%mod;
    while(p)
    {
        if(p&1)
            ans = ans*n%mod;
        n = n*n%mod;
        p = p/2;
    }
    return ans%mod;
}
int main()
{
    int n,p;
    scanf("%d %d",&n,&p);
    int ans = quick(n,p);
    printf("%d\n",ans);
    return 0;
}

欧拉函数:

令ϕ(m)
表示小于等于m且与m互素的正整数的个数。

如果x与m互素,则有x^ϕ(m)≡1(mod
m),即x*x^(ϕ(m)-1)≡1(modm),x^(ϕ(m)-1)即为x的逆元。

在m为质数的处境下,ϕ(m) =
m-1,即为费马小定理。

代码:

驷不及舌是求欧拉函数的值。

运用欧拉函数的积星性质:

 

对给定n举行整数分解。时间复杂度O(√n).

///求ϕ(n)
#define mod 1000003
int eurler(int n)
{
    int ans = n;
    for(int i=2;i*i<= n;i++)
    {
        if(n%i==0)
        {
            ans = ans/i*(i-1);
            while(n%i==0) n/=i;
        }
    }
    if(n!=1)
        ans = ans /n *(n-1);
    return ans;
}

 

相关文章