新闻  |   论坛  |   博客  |   在线研讨会
模运算的乘法逆元
电子禅石 | 2021-07-21 15:55:02    阅读:24   发布文章
模运算的乘法逆元

二元运算符  ‘≡’: 当 a%p = b%p 时,a ≡ b ( mod p )

模运算对于 加法 和 乘法 同样适用,也就是说,如果 a ≡ a` (mod p) 和 b ≡ b` (mod p),那么

       a + b ≡ a` + b` (mod p)

       a * b ≡ a` * b` (mod p)

对于 除法 却不适用

  存在  a / b mod p  !=  a` / b` mod p

模乘法逆元:若 a * b ≡ 1 (mod p),则称 a 为 b 的模乘法逆元(在mod p 的情况下),或称 b 为 a 的模乘法逆元(在mod p 的情况下)

       假设  a / b ≡ c (mod p),b * x ≡ 1 (mod p)  

       那么  a * x ≡ c (mod p)

 

  • 扩展欧几里得求模乘法逆元

  现已知 a,b,p 要求 c

         则只要找到 b 的模乘法逆元 x ,使得 b * x ≡ 1 (mod p) 则可求得 c

                   b * x ≡ 1 (mod p)

                则 b * x + p * y = 1  

         这样问题就转化为求已知 b,p 求 一元整数组 ( x, y ) 使得 b * x + p * y = 1 , 可用扩展欧几里得算法

    若得不到一元整数组 ( x, y ),也就是 gcd(b, p) != 1, 则 (在mod p 的情况下) 不存在 b 的模乘法逆元

 

  • 费马小定理求模乘法逆元

  费马小定理:假如 b 是一个整数,p 是一个质数,那么 bp - b 是 p 的倍数

    b ^ p ≡ b ( mod p)

         b * bp-2 ≡ 1 (mod p)

 

  • 递推求 1 - n 求模乘法逆元

  inv[ i ] 表示 i 的模乘法逆元

    设  k = p % i,  t = ( p - k ) / i

       则 t * i + k = p

     t * i + k ≡ 0 ( mod p )

     若 k 不为 0 ,同除以 ( k * i )

        t * i / ( k * i ) + k / ( k * i ) ≡ 0 ( mod p )

        t / (  p % i )  + 1 / i ≡ 0 ( mod p )

     ( p - k ) / i * inv[ p % i ] + inv[ i ] ≡ 0 ( mod p )

    inv[1] = 1;     for (int i = 2; i <= n; ++i)     {         inv[i] = (p - p / i) * inv[p%i] % p;     }

   因为 k 不为 0,要求 p % i 不为 0

 

扩展欧几里得算法

  已知 a 和 b 求一元组 ( x, y ) 使得 a * x + b * y = gcd(a, b)

    a*x + b*y = gcd(a, b)

  ∵  gcd(a, b) = gcd(b, a%b)           ---------  ①

       ∴  b*x` + (a%b)*y` = gcd(a, b)      ---------  ②

      设  t = a / b (下取整)

      则  b*x` + (a-t*b)*y` = gcd(a, b)

            a*y` + b(x`-t*b*y`) = gcd(a, b)

      等式 ① 的一元组为 (x`, y`),若 a % b = 0 则 x` = 1, y` = 0

   那么等式 ② 的一元组为 (x = y`, y = x`- t*b*y`)

复制代码

int extgcd(int a, int b, int &x, int &y)
 {     int c = a;   
       if( b == 0 )
        x = 1, y = 0;     
        else c = extgcd(b, a%b, y, x), 
        y -= ( a/b ) * x;     return c; 
        }



*博客内容为网友个人发布,仅代表博主个人观点,如有侵权请联系工作人员删除。

参与讨论
登录后参与讨论
属于自己的技术积累分享,成为嵌入式系统研发高手。
推荐文章
最近访客