精华内容
下载资源
问答
  • 模逆元
    千次阅读
    2021-10-15 20:27:36

     方法一:使用Crypto库

    from Crypto.Util.number import *
    print(inverse(3,7))  #3是要求逆元的数,7是模数
    
    

    注:如果 两个数不互素, 则返回  最大公因数的 逆元

    方法二:用 gmpy2

    安装方法

    官方只提供到 3.4 的gmpy2 的包。

    参考下方的方法在高版本的python安装gmpy2

    Python3.7下如何安装gmpy2_yundi的博客-CSDN博客

    使用方法

    from gmpy2 import invert
    print(invert(3,7))  #3是要求逆元的数,7是模数

    注:两参数 不互素时  会报错

    更多相关内容
  • 模逆元的一种算法

    2014-07-10 20:20:36
    模逆元的一种算法 输入a,m求出a关于m的一中算法。
  • 什么是模逆元

    千次阅读 多人点赞 2020-10-11 00:50:38
    整数 a 除以整数 b,若得到的余数是 r,则记作 ...运算的部分性质如下: (a+b) mod c=((a mod c)+(b mod c)) mod c(a + b) \bmod{c} = ((a \bmod{c}) + (b \bmod{c})) \bmod{c}(a+b)modc=((amodc)+(bm

    https://aaron67.cc/2020/05/30/modular-multiplicative-inverse/

    整数 a 除以整数 b,若得到的余数是 r,则记作

    a   m o d   b = r a \bmod{b} = r amodb=r

    例如

    5   m o d   3 = 2 5 \bmod{3} = 2 5mod3=2

    − 5   m o d   3 = 1 -5 \bmod{3} = 1 5mod3=1

    模运算的部分性质如下:

    ( a + b )   m o d   c = ( ( a   m o d   c ) + ( b   m o d   c ) )   m o d   c (a + b) \bmod{c} = ((a \bmod{c}) + (b \bmod{c})) \bmod{c} (a+b)modc=((amodc)+(bmodc))modc

    ( a ⋅ b )   m o d   c = ( ( a   m o d   c ) ⋅ ( b   m o d   c ) )   m o d   c (a \cdot b) \bmod{c} = ((a \bmod{c}) \cdot (b \bmod{c})) \bmod{c} (ab)modc=((amodc)(bmodc))modc

    a b   m o d   c = ( a   m o d   c ) b   m o d   c a^{b} \bmod{c} = (a \bmod{c})^{b} \bmod{c} abmodc=(amodc)bmodc

    如果你对模运算还不太熟悉,推荐先阅读 Khan Academy 的入门课程

    同余

    两个整数 a、b,若它们除以正整数 n 所得的余数相等,即 a   m o d   n = b   m o d   n a \bmod{n} = b \bmod{n} amodn=bmodn,则称 a 和 b 对于模 n 同余,记作

    a ≡ b ( m o d n ) a\equiv b \pmod{n} ab(modn)

    读作 a 同余于 b 模 n,或 a 和 b 关于模 n 同余。例如

    2 ≡ 8 ( m o d 6 ) 2\equiv 8 \pmod{6} 28(mod6)

    当 k 为整数( k ∈ Z k \in \mathbb{Z} kZ)时,同余关系有如下性质。

    a ≡ b ( m o d n )      ⇒      a k ≡ b k ( m o d n ) a\equiv b \pmod{n}\ \ \ \ \Rightarrow \ \ \ \ ak\equiv bk \pmod{n} ab(modn)        akbk(modn)

    当 k、n 互质时,有

    a k ≡ b k ( m o d n )      ⇒      a ≡ b ( m o d n ) ak\equiv bk \pmod{n}\ \ \ \ \Rightarrow \ \ \ \ a\equiv b \pmod{n} akbk(modn)        ab(modn)

    模逆元

    参考倒数( x y = 1 xy = 1 xy=1)的定义,对整数 a 和 b,若

    a b ≡ 1 ( m o d n ) ab \equiv 1 \pmod{n} ab1(modn)

    则称 a 和 b 关于模 n 互为模倒数,也叫模反元素或模逆元(modular multiplicative inverse),还可以记作

    b ≡ 1 a ( m o d n )      或      b ≡ a − 1 ( m o d n ) b \equiv \frac{1}{a} \pmod{n}\ \ \ \ 或\ \ \ \ b \equiv a^{-1} \pmod{n} ba1(modn)        ba1(modn)

    类似于实数除法,在模 n 下的除法可以用和对应模逆元的乘法来表达。”分数取模”,等价于求分母的模逆元。

    当 a、b 关于模 n 互为模逆元时, b   m o d   n = 1 a   m o d   n b \bmod{n} = \frac{1}{a} \bmod{n} bmodn=a1modn

    c a   m o d   n = ( c ⋅ 1 a )   m o d   n = ( ( c   m o d   n ) ⋅ ( 1 a   m o d   n ) )   m o d   n = ( ( c   m o d   n ) ⋅ ( b   m o d   n ) )   m o d   n = ( c ⋅ b )   m o d   n \frac{c}{a} \bmod{n} = (c \cdot \frac{1}{a}) \bmod{n} = ((c \bmod{n}) \cdot (\frac{1}{a} \bmod{n})) \bmod{n} = ((c \bmod{n}) \cdot (b \bmod{n})) \bmod{n} = (c \cdot b) \bmod{n} acmodn=(ca1)modn=((cmodn)(a1modn))modn=((cmodn)(bmodn))modn=(cb)modn

    例如

    20 3   m o d   7 = ( ( 20   m o d   7 ) ⋅ ( 1 3   m o d   7 ) )   m o d   7 = ( 6 × 5 )   m o d   7 = 2 \frac{20}{3} \bmod{7} = ((20 \bmod{7}) \cdot (\frac{1}{3} \bmod{7})) \bmod{7} = (6 \times 5) \bmod{7} = 2 320mod7=((20mod7)(31mod7))mod7=(6×5)mod7=2

    根据定义,求 a 关于模 n 的模逆元,若 b 是解, k ∈ Z k \in \mathbb{Z} kZ,则 b + k n b + kn b+kn 也都是解,且最小的非负整数解小于 n,例如

    2 × 3 ≡ 1 ( m o d 5 ) 2 \times 3 \equiv 1 \pmod{5} 2×31(mod5)

    2 × 8 ≡ 1 ( m o d 5 ) 2 \times 8 \equiv 1 \pmod{5} 2×81(mod5)

    即 3 和 8 都是 2 关于模 5 的模逆元,其中 3 是最小的非负整数解。所以求模逆元可以通过遍历 0 ~ n 来确定。

    # find modular multiplicative inverse of 'a' under modulo 'n'
    def modular_multiplicative_inverse(a: int, n: int) -> int:
        for i in range(n):
            if (a * i) % n == 1:
                return i
        raise ValueError('{} has no multiplicative inverse under modulo {}'.format(a, n))
    

    但这种方法在 n 取值很大时效率不高。你可以参考文章 Modular multiplicative inverse,使用扩展欧几里得算法或费马小定理改进。

    def extended_euclid_gcd(a: int, b: int) -> list:
        """
        Returns [gcd(a, b), x, y] where ax + by = gcd(a, b)
        """
        s, old_s = 0, 1
        t, old_t = 1, 0
        r, old_r = b, a
        while r != 0:
            quotient = old_r // r
            old_r, r = r, old_r - quotient * r
            old_s, s = s, old_s - quotient * s
            old_t, t = t, old_t - quotient * t
        return [old_r, old_s, old_t]
    
    
    def modular_multiplicative_inverse(a: int, n: int) -> int:
        """
        Assumes that a and n are co-prime, returns modular multiplicative inverse of a under n
        """
        # Find gcd using Extended Euclid's Algorithm
        gcd, x, y = extended_euclid_gcd(a, n)
        # In case x is negative, we handle it by adding extra n
        # Because we know that modular multiplicative inverse of a in range n lies in the range [0, n-1]
        if x < 0:
            x += n
        return x
    

    已知整数 a、n,使用扩展欧几里得算法可以求出整数 x、y、g 满足下式。

    a x + n y = g ax + ny = g ax+ny=g

    其中,g 是 a 和 n 的最大公约数。上式两边同模 n,有

    ( a x + n y )   m o d   n = ( a x   m o d   n ) + ( n y   m o d   n ) = a x   m o d   n = g   m o d   n (ax + ny) \bmod{n} = (ax \bmod{n}) + (ny \bmod{n}) = ax \bmod{n} = g \bmod{n} (ax+ny)modn=(axmodn)+(nymodn)=axmodn=gmodn

    a x ≡ g ( m o d n ) ax \equiv g \pmod{n} axg(modn)

    当 a、n 互质时, g = 1 g = 1 g=1,此时 x 就是解。当 g ≠ 1 g \neq 1 g=1 时, a 关于模 n 的模逆元不存在。

    两数互质的充分必要条件是两数的最大公约数为 1。也就是说,a 关于模 n 的模逆元存在的充分必要条件是 a 和 n 互质。

    完整代码

    modular_inverse.py

    展开全文
  • 拓展欧几里得算法求乘模逆元

    千次阅读 2019-09-03 23:20:53
    前言:仅个人小记。之前已经证明了 “若正整数a,b互素,则必然存在b以内的正整数k,...本文进一步借助 拓展欧几里得算法,给出快速求解 k 值的方法,即求解乘法逆元的方法,具体多快?时间复杂度为O(log(b)). ...

    前言:仅个人小记。之前已经证明了 “若正整数a,b互素,则必然存在b以内的正整数k,使得ak%b=1” 成立。本文进一步借助 拓展欧几里得算法,给出快速求解 k 值的方法,即求解乘法逆元的方法,具体多快?时间复杂度为O(log(b))。另外,除了在这里产生了求乘法逆元的需要,其他很多场合也有求解乘法逆元的需要,比如CRT中国剩余定理算法中、模幂乘循环群中求解逆元等。

    前要知识

    1. 如果 a m o d &ThinSpace;&ThinSpace; b = 1 , 则 a ⊥ b a\mod b=1,则a\perp b amodb=1ab。参看 https://blog.csdn.net/qq_25847123/article/details/99944096
    2. a与c互质且b与c互质,则必然ab与c互质。 参看 https://blog.csdn.net/qq_25847123/article/details/95765764
    3. 拓展欧几里得算法。参看 https://blog.csdn.net/qq_25847123/article/details/100672171

    问题交代

    给出
    a x % p = 1 ax\%p=1 ax%p=1
    x = ? x=? x=?

    求解开始

    前要知识1知,既然 a x % p = 1 ax\%p=1 ax%p=1 成立,则必然 a x ⊥ p ax\perp p axp,进而再由前要知识2必然有 a ⊥ p , x ⊥ p a\perp p,x\perp p ap,xp,所以必然有 a, p 的最大公约数为 1,记为 gcd(a,p)=1
    a x % p = 1 ⇔ a x = k p + 1 , k 为 任 意 整 数 ax\%p=1\\ \Leftrightarrow ax=kp+1,k为任意整数 ax%p=1ax=kp+1,k k = − y k=-y k=y则有
    a x = − y p + 1 ax=-yp+1 ax=yp+1进而
    a x + p y = 1 ax+py=1 ax+py=1 a x + b y = 1 ⇔ a x + p y = 1 ⇔ a x + p y = g c d ( a , b ) ax+by=1\Leftrightarrow ax+py=1\Leftrightarrow ax+py=gcd(a,b) ax+by=1ax+py=1ax+py=gcd(a,b)此时问题转为拓展欧几里得算法求解问题,借助拓展欧几里得算法可以解出 x,即求解出 a 的乘模逆元。

    代码求解展示(python)

     def getMulInverse(self,a,b):
            ''' 求解乘法逆元
            
            a,b互素,ak%b=1 ,求 a 的逆元 k
            
            本质上就是构建 ax+by=1 这个方程,然后借助拓展欧几里得算法进行求解
            显然 要求 ax%b=1 中 x,就等价于求解 (ax+by)%b=1 中的 x,就等价于求 ax+by=1中的 x
            '''
            if self.gcd(a,b)!=1:
                print('a,b不互素。模数为b的情况下,a 不存在逆元')
                return -1
            
            x,y,g = self.exGCD(a,b)# 调用拓展欧几里得函数
            return x
    
    展开全文
  • 数论10——乘法逆元(模逆元)

    千次阅读 2019-08-15 20:11:06
    其实是乘法逆元: a * a^-1 ≡ 1(mod p) 方法一, 扩展欧几里得求逆元: 扩展欧几里得,可以求逆元的原因: 假设a 与 x互逆(mod p):          a * ...

    推荐https://blog.csdn.net/qq_37656398/article/details/81434277
    这几所说的乘法逆元其实是 模反元素(也叫模逆元)

      a  *  a^-1  ≡ 1(mod p)(p为素数)   
    
    方法一, 扩展欧几里得求逆元:

    扩展欧几里得,可以求逆元的原因:

    假设a 与 x互逆(mod p):
             a * x %p = 1;
             等价于:
              ax = py+1;
              ax- py = 1;
             这样就可以用扩展欧几里得解线性不定方程求逆元了

    ll exgcd(ll a, ll b, ll &x, ll &y)// ax+by == gcd(a, b)
    {
        ll res;
        if(b == 0)
        {
            x = 1;
            y = 0;
            return a;
        }
        res = exgcd(b,a%b, x, y);
    
        ll tmp = y;
        y =  x- a/b*y;
        x = tmp;
        return res;
    }
    ll mod_reverse(ll a, ll mod)
    {
        ll x, y, d;
        d = exgcd(a, mod, x, y);
    
        if(d == 1)// 有解
        {
            /**求 大于0的最小特解******/
            if(x%mod <= 0)return x%mod+mod;// 其实模的是 mod/d, 但是d == 1, 所以这个两个值相等
            else return x%mod;
        }
        else return -1ll;//(long long)-1;// 无解
    
    }
    

    方法二 费马定理求乘法逆元:

      费马小定理:
            如果p是一个质数,而整数a不是p的倍数,则有a^(p-1)≡1(mod p)

    所以a* a^p-2 ≡ 1(mod p);
    所以 a的逆元 就是 a ^ p- 2(mod p)

    using namespace std;
    long long pow_mod(long long a, long long b)
    {
        long long ret = 1;
    
        while(b)
        {
            if(b%2!= 0)ret*=a%Mod;//b&1;
            a =a*a%Mod;
            b/=2;//b>>1
        }
        return ret;
    }
    调用时:
     pow_mod(a, Mod-2);
    

    求地推求阶乘的逆

        int f[maxn];//阶乘数组
        int inv[maxn];// 逆元数组
        f[0]=1;// 
        for(int i=1; i<=N; i++)//
            f[i]=f[i-1]*i%Mod;
        inv[0]=1;
        
        inv[N]=PowMod(f[N],Mod-2);// 先用费马 求 N!的逆元
        
        for(int i=N-1; i>0; i--)// 地推求 i!的逆元
            inv[i]=inv[i+1]*(i+1)%Mod;// i阶乘的 逆 就等于 inv阶乘的逆成i+1.
    

    地推求连续数的逆元

    
    int inv[maxn]; //逆元数值
    inv[1] = 1;//1的逆元时1
    
    for(int i = 2;i<= N;i++)// N为要求逆元的上限
    {
    	inv[i] = (Mod - Mod/i)*inv[Mod%i] %Mod;
    }
    

    证明:

    https://www.cnblogs.com/Lates/p/11147053.html

    
    
        递推式:inv(i)=(p−p/i)×inv(pmodi)modp
        证明过程:
    
          假设该式成立,则有
    
               i×inv(i) ≡i×(p−⌊pi⌋)×inv(pmodi) modp
          变式后可得
    
              i×inv(i)≡(ip−i×⌊pi⌋))×inv(pmodi)modp
          根据随时取模性质,得到
                 	  i×inv(i)≡ (p*(i-1) + p-i×⌊pi⌋ )×inv(pmodi) mod p
               i×inv(i)≡(pmodi)×inv(pmodi)modp 
            
          显然,这个式子是成立的
    
    				
    
    展开全文
  • Matlab,扩展欧几里德算法,求b条件下,a的乘法逆元,函数Eulid.m,直接调用传入参数就可以用,含参数使用注释。
  • 大数 逆元 矩阵

    2021-11-18 13:46:29
    所以可以用一个很大质数取模(/ 可以用逆元来运算) 如果结果和之前不一样 那么就是- 反正则是+ AC代码 #include<bits/stdc++.h> #define endl "\n" #define INF 0x3f3f3f3f3f3f3f typedef long long ll; const ...
  • 2018-08-21模反元素也称为模倒数,或者模逆元。一整数a对 同余n之模反元素是指满足以下公式的整数 b:也可以写成以下的式子如果不看mod运算,这类似于ab=1,那么a和b互为倒数。a、b为整数。例如,对于模12来说,5和5...
  • 欧几里得拓展算法求模逆元

    千次阅读 2017-04-10 20:41:02
    实现语言:python ...模逆元和最大公约数一样有算法找出,这里用欧几里得的拓展算法,可以找一个数字的模逆。 注: 模逆元参考大神博客:http://blog.csdn.net/acdreamers/article/details...
  • #1530 : 分数取模 时间限制:1000ms 单点时限:10000ms ...这时分数 a / b 除以 p 的余数,即 a / b MOD p 可以定义为 a × b-1 MOD p。...其中b-1 是 b 的逆元,它满足 1 ≤ b-1 < p 且 b × b...
  • 版权声明:本文为博主原创文章,未经博主允许不得转载。... 一、除法取模逆元 在算法设计中,常会遇到求 a/b mod m的计算,当a很大,或者b很大,使得a/b的值无法...
  • 逆元,在解决中国余数问题中特别重要。这里简单介绍扩展欧几里得法解逆元问题
  • 辗转相除法求逆元

    万次阅读 多人点赞 2018-11-14 17:05:50
    E*D ≡ 1 mod r ,现在已知了E和r,求E即是一个求逆元问题。 注:≡是数论中表示同余的符号。公式中,≡符号的左边必须和符号右边同余,也就是两边运算结果相同。显而易见,不管r取什么值(r是N的欧拉函数值...
  • 用欧几里德算法来求逆元,该程序可以输入两个数,这两个数必须互质,来求某个数的逆元
  • 逆元

    万次阅读 2017-04-22 10:12:02
    逆元 辗转相处法 扩展欧几里得 最大公约数 质数
  • 问题:求A关于模N的逆元B,即要找出整数B,使A×B mod N=1(或A×B=x×N+1),这里要求A和N互素。 方法:辗转相除法(即欧几里德算法) 该算法原用于求两个数的最大公约数,经过变形可用于求模逆元
  • 数论—运算的逆元

    万次阅读 多人点赞 2018-09-01 21:02:16
    有关运算 定义 运算规则 逆元 定义 使用方法 求逆元的方法 枚举法 拓展欧几里得(Extend - Eculid) 费马小定理(Fermat's little theorem) 注意 有关运算 在信息学竞赛中,当答案过于庞大的时候,我们...
  • cf 1312 D 逆元模板

    2021-01-03 20:51:50
    Your task is to calculate the number of arrays such that: each array contains n elements; each element is an integer from 1 to m; for each array, there is exactly one pair of equal elements;...
  • 密码学中运算的逆元求解

    万次阅读 2019-08-09 11:29:06
    对于正整数a和m,如果有ax≡1(modm),那么把这个同余方程中的x最小正整数解叫做ax的逆元逆元一般用扩展欧几里得算法来求得,如果m为素数,那么还可以根据费马小定理得到逆元为。 推导过程: 详细见:欧拉定理与...
  • 运算的运算法则及逆元的计算

    千次阅读 2019-11-03 14:30:21
    运算与基本四则运算有些相似,但是除法例外。其规则如下: (a + b) % p = (a % p + b % p) % p (a - b) % p = (a % p - b % p) % p (a * b) % p = (a % p * b % p) % p (a^b) % p = ((a % p)^b) % p 推论: 若a≡b...
  • 加密解密的基础,扩展欧几里得算法(辗转相除法)
  • 两种求m逆元的方法

    万次阅读 2016-05-14 18:23:40
    在a|b(a能整除b)的前提下,计算(b/a)mod m的... 这时的x就是a的逆元(am的逆元);  此时x满足  (a*x mod m == 1);   这个x的求法有一下两种: 1)扩展欧几里得算法求解 a*x+m*y=1; 因为 a*x mod m =

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,259
精华内容 5,303
关键字:

模逆元