算法设计：模乘逆元问题

2021年3月17日14:40:14 发表评论 797 次浏览

本文概述

给定两个整数" a"和" m", 在模" m"下找到" a"的模乘逆。

模乘法逆是一个整数" x", 使得。

a x  ≡ 1 (mod m)

x的值应为{0, 1, 2, …m-1}, 即在整数模m的范围内。

当且仅当a和m相对质数(即gcd(a, m)= 1)时, 才存在"模m"的乘法逆。

例子：

Input:  a = 3, m = 11
Output: 4
Since (4*3) mod 11 = 1, 4 is modulo inverse of 3(under 11).
One might think, 15 also as a valid output as "(15*3) mod 11" 
is also 1, but 15 is not in ring {0, 1, 2, ... 10}, so not 
valid.

Input:  a = 10, m = 17
Output: 12
Since (10*12) mod 17 = 1, 12 is modulo inverse of 10(under 17).

推荐：请在"

实践

首先, 在继续解决方案之前。

方法1(天真)

天真的方法是尝试从1到m的所有数字。对于每个数字x, 检查(a * x)％m是否为1。以下是此方法的实现。

C ++

// C++ program to find modular inverse of a under modulo m
#include<iostream>
using namespace std;
  
// A naive method to find modular multiplicative inverse of
// 'a' under modulo 'm'
int modInverse( int a, int m)
{
     a = a%m;
     for ( int x=1; x<m; x++)
        if ((a*x) % m == 1)
           return x;
}
  
// Driver Program
int main()
{
     int a = 3, m = 11;
     cout << modInverse(a, m);
     return 0;
}

Java

// Java program to find modular inverse 
// of a under modulo m
import java.io.*;
  
class GFG {
      
     // A naive method to find modulor 
     // multiplicative inverse of 'a' 
     // under modulo 'm'
     static int modInverse( int a, int m)
     {
         a = a % m;
         for ( int x = 1 ; x < m; x++)
            if ((a * x) % m == 1 )
               return x;
         return 1 ;
     }
       
     // Driver Program
     public static void main(String args[])
     {
         int a = 3 , m = 11 ;
         System.out.println(modInverse(a, m));
     }
}
  
  
/*This code is contributed by Nikita Tiwari.*/

Python3

# Python 3 program to find modular 
# inverse of a under modulo m
  
# A naive method to find modulor 
# multiplicative inverse of 'a' 
# under modulo 'm'
def modInverse(a, m) :
     a = a % m;
     for x in range ( 1 , m) :
         if ((a * x) % m = = 1 ) :
             return x
     return 1
  
# Driver Program
a = 3
m = 11
print (modInverse(a, m))
  
#This code is contributed by Nikita Tiwari.

C#

// C# program to find modular inverse 
// of a under modulo m
using System;
  
class GFG {
      
     // A naive method to find modulor 
     // multiplicative inverse of 'a' 
     // under modulo 'm'
     static int modInverse( int a, int m)
     {
         a = a % m;
         for ( int x = 1; x < m; x++)
         if ((a * x) % m == 1)
             return x;
         return 1;
     }
      
     // Driver Code
     public static void Main()
     {
         int a = 3, m = 11;
         Console.WriteLine(modInverse(a, m));
     }
}
  
// This code is contributed by anuj_67.

的PHP

<?php
// PHP program to find modular 
// inverse of a under modulo m
  
// A naive method to find modulor
// multiplicative inverse of
// 'a' under modulo 'm'
function modInverse( $a , $m )
{
     $a = $a % $m ;
     for ( $x = 1; $x < $m ; $x ++)
     if (( $a * $x ) % $m == 1)
         return $x ;
}
  
     // Driver Code
     $a = 3; 
     $m = 11;
     echo modInverse( $a , $m );
  
// This code is contributed by anuj_67.
?>

输出如下：

4

该方法的时间复杂度为O(m)。

方法2(当m和a为互质时有效)

这个想法是使用

扩展的欧几里得算法

取两个整数" a"和" b", 找到它们的gcd并找到" x"和" y", 使得

ax + by = gcd(a, b)

要在" m"下找到" a"的乘法逆, 我们将b = m放在上式中。由于我们知道a和m是相对质数, 因此可以将gcd的值设为1。

ax + my = 1

如果我们在两边取模m, 我们得到

ax + my ≡ 1 (mod m)

我们可以删除左侧的第二项, 因为" my(mod m)"对于整数y始终为0。

ax  ≡ 1 (mod m)

因此, 我们可以找到的" x"

扩展欧几里得算法

是" a"的乘法逆

下面是上述算法的C ++实现。

C

// C program to find multiplicative modulo inverse using 
// Extended Euclid algorithm. 
#include<stdio.h> 
  
// C function for extended Euclidean Algorithm 
int gcdExtended( int a, int b, int *x, int *y); 
  
// Function to find modulo inverse of a 
void modInverse( int a, int m) 
{ 
     int x, y; 
     int g = gcdExtended(a, m, &x, &y); 
     if (g != 1) 
         printf ( "Inverse doesn't exist" ); 
     else
     { 
         // m is added to handle negative x 
         int res = (x%m + m) % m; 
         printf ( "Modular multiplicative inverse is %d" , res); 
     } 
} 
  
// C function for extended Euclidean Algorithm 
int gcdExtended( int a, int b, int *x, int *y) 
{ 
     // Base Case 
     if (a == 0) 
     { 
         *x = 0, *y = 1; 
         return b; 
     } 
  
     int x1, y1; // To store results of recursive call 
     int gcd = gcdExtended(b%a, a, &x1, &y1); 
  
     // Update x and y using results of recursive 
     // call 
     *x = y1 - (b/a) * x1; 
     *y = x1; 
  
     return gcd; 
} 
  
// Driver Program 
int main() 
{ 
     int a = 3, m = 11; 
     modInverse(a, m); 
     return 0; 
}

的PHP

<?php
// PHP program to find multiplicative modulo 
// inverse using Extended Euclid algorithm.
  
// Function to find modulo inverse of a
function modInverse( $a , $m )
{
     $x = 0;
     $y = 0;
     $g = gcdExtended( $a , $m , $x , $y );
     if ( $g != 1)
         echo "Inverse doesn't exist" ;
     else
     {
         // m is added to handle negative x
         $res = ( $x % $m + $m ) % $m ;
         echo "Modular multiplicative " . 
                    "inverse is " . $res ;
     }
}
  
// function for extended Euclidean Algorithm
function gcdExtended( $a , $b , & $x , & $y )
{
     // Base Case
     if ( $a == 0)
     {
         $x = 0;
         $y = 1;
         return $b ;
     }
  
     $x1 ;
     $y1 ; // To store results of recursive call
     $gcd = gcdExtended( $b % $a , $a , $x1 , $y1 );
  
     // Update x and y using results of 
     // recursive call
     $x = $y1 - (int)( $b / $a ) * $x1 ;
     $y = $x1 ;
  
     return $gcd ;
}
  
// Driver Code
$a = 3;
$m = 11;
modInverse( $a , $m );
  
// This code is contributed by chandan_jnu
?>

输出如下： 

Modular multiplicative inverse is 4

迭代实现：

C ++

// Iterative C++ program to find modular
// inverse using extended Euclid algorithm
#include <stdio.h>
  
// Returns modulo inverse of a with respect
// to m using extended Euclid Algorithm
// Assumption: a and m are coprimes, i.e., // gcd(a, m) = 1
int modInverse( int a, int m)
{
     int m0 = m;
     int y = 0, x = 1;
  
     if (m == 1)
       return 0;
  
     while (a > 1)
     {
         // q is quotient
         int q = a / m;
         int t = m;
  
         // m is remainder now, process same as
         // Euclid's algo
         m = a % m, a = t;
         t = y;
  
         // Update y and x
         y = x - q * y;
         x = t;
     }
  
     // Make x positive
     if (x < 0)
        x += m0;
  
     return x;
}
  
// Driver program to test above function
int main()
{
     int a = 3, m = 11;
  
     printf ( "Modular multiplicative inverse is %d\n" , modInverse(a, m));
     return 0;
}

Java

// Iterative Java program to find modular
// inverse using extended Euclid algorithm
  
class GFG
{
  
     // Returns modulo inverse of a with
     // respect to m using extended Euclid
     // Algorithm Assumption: a and m are
     // coprimes, i.e., gcd(a, m) = 1
     static int modInverse( int a, int m)
     {
         int m0 = m;
         int y = 0 , x = 1 ;
  
         if (m == 1 )
             return 0 ;
  
         while (a > 1 )
         {
             // q is quotient
             int q = a / m;
  
             int t = m;
  
             // m is remainder now, process
             // same as Euclid's algo
             m = a % m;
             a = t;
             t = y;
  
             // Update x and y
             y = x - q * y;
             x = t;
         }
  
         // Make x positive
         if (x < 0 )
             x += m0;
  
         return x;
     }
  
     // Driver program to test above function
     public static void main(String args[])
     {
         int a = 3 , m = 11 ;
  
         System.out.println( "Modular multiplicative " +
                            "inverse is " + modInverse(a, m));
     }
}
  
/*This code is contributed by Nikita Tiwari.*/

Python3

# Iterative Python 3 program to find
# modular inverse using extended
# Euclid algorithm
  
# Returns modulo inverse of a with
# respect to m using extended Euclid
# Algorithm Assumption: a and m are
# coprimes, i.e., gcd(a, m) = 1
def modInverse(a, m) :
     m0 = m
     y = 0
     x = 1
  
     if (m = = 1 ) :
         return 0
  
     while (a > 1 ) :
  
         # q is quotient
         q = a / / m
  
         t = m
  
         # m is remainder now, process
         # same as Euclid's algo
         m = a % m
         a = t
         t = y
  
         # Update x and y
         y = x - q * y
         x = t
  
  
     # Make x positive
     if (x < 0 ) :
         x = x + m0
  
     return x
  
  
# Driver program to test above function
a = 3
m = 11
print ( "Modular multiplicative inverse is" , modInverse(a, m))
  
# This code is contributed by Nikita tiwari.

C#

// Iterative C# program to find modular
// inverse using extended Euclid algorithm
using System;
class GFG
{
  
     // Returns modulo inverse of a with
     // respect to m using extended Euclid
     // Algorithm Assumption: a and m are
     // coprimes, i.e., gcd(a, m) = 1
     static int modInverse( int a, int m)
     {
         int m0 = m;
         int y = 0, x = 1;
  
         if (m == 1)
             return 0;
  
         while (a > 1)
         {
             // q is quotient
             int q = a / m;
  
             int t = m;
  
             // m is remainder now, process
             // same as Euclid's algo
             m = a % m;
             a = t;
             t = y;
  
             // Update x and y
             y = x - q * y;
             x = t;
         }
  
         // Make x positive
         if (x < 0)
             x += m0;
  
         return x;
     }
  
     // Driver Code
     public static void Main()
     {
         int a = 3, m = 11;
         Console.WriteLine( "Modular multiplicative " +
                         "inverse is " + modInverse(a, m));
     }
}
  
// This code is contributed by anuj_67.

的PHP

<?php
// Iterative PHP program to find modular
// inverse using extended Euclid algorithm
  
// Returns modulo inverse of a with respect
// to m using extended Euclid Algorithm
// Assumption: a and m are coprimes, i.e., // gcd(a, m) = 1
function modInverse( $a , $m )
{
     $m0 = $m ;
     $y = 0;
     $x = 1;
  
     if ( $m == 1)
     return 0;
  
     while ( $a > 1)
     {
          
         // q is quotient
         $q = (int) ( $a / $m );
         $t = $m ;
  
         // m is remainder now, // process same as
         // Euclid's algo
         $m = $a % $m ;
         $a = $t ;
         $t = $y ;
  
         // Update y and x
         $y = $x - $q * $y ;
         $x = $t ;
     }
  
     // Make x positive
     if ( $x < 0)
     $x += $m0 ;
  
     return $x ;
}
  
     // Driver Code
     $a = 3;
     $m = 11;
  
     echo "Modular multiplicative inverse is\n" , modInverse( $a , $m );
          
// This code is contributed by Anuj_67
?>

输出如下：

Modular multiplicative inverse is 4

该方法的时间复杂度为O(Log m)

方法3(当m为素数时有效)

如果我们知道m是素数, 那么我们也可以使用

费马斯的小定理

寻找逆。

am-1 ≡ 1 (mod m)

如果我们将两边都乘以

-1

, 我们得到

a-1 ≡ a m-2 (mod m)

以下是上述想法的实现。

C ++

// C++ program to find modular inverse of a under modulo m
// This program works only if m is prime.
#include<iostream>
using namespace std;
  
// To find GCD of a and b
int gcd( int a, int b);
  
// To compute x raised to power y under modulo m
int power( int x, unsigned int y, unsigned int m);
  
// Function to find modular inverse of a under modulo m
// Assumption: m is prime
void modInverse( int a, int m)
{
     int g = gcd(a, m);
     if (g != 1)
         cout << "Inverse doesn't exist" ;
     else
     {
         // If a and m are relatively prime, then modulo inverse
         // is a^(m-2) mode m
         cout << "Modular multiplicative inverse is "
              << power(a, m-2, m);
     }
}
  
// To compute x^y under modulo m
int power( int x, unsigned int y, unsigned int m)
{
     if (y == 0)
         return 1;
     int p = power(x, y/2, m) % m;
     p = (p * p) % m;
  
     return (y%2 == 0)? p : (x * p) % m;
}
  
// Function to return gcd of a and b
int gcd( int a, int b)
{
     if (a == 0)
         return b;
     return gcd(b%a, a);
}
  
// Driver Program
int main()
{
     int a = 3, m = 11;
     modInverse(a, m);
     return 0;
}

Java

// Java program to find modular 
// inverse of a under modulo m
// This program works only if 
// m is prime.
import java.io.*;
  
class GFG {
  
     // Function to find modular inverse of a 
     // under modulo m Assumption: m is prime
     static void modInverse( int a, int m)
     {
         int g = gcd(a, m);
         if (g != 1 )
             System.out.println( "Inverse doesn't exist" );
         else 
         {
             // If a and m are relatively prime, then modulo inverse
             // is a^(m-2) mode m
             System.out.println( "Modular multiplicative inverse is " +
                                 power(a, m - 2 , m));
         }
     }
      
     // To compute x^y under modulo m
     static int power( int x, int y, int m) 
     {
         if (y == 0 )
             return 1 ;
          
         int p = power(x, y / 2 , m) % m;
         p = (p * p) % m;
      
         if (y % 2 == 0 )
             return p;
         else
             return (x * p) % m;
     }
      
     // Function to return gcd of a and b
     static int gcd( int a, int b) 
     {
         if (a == 0 )
             return b;
         return gcd(b % a, a);
     }
      
     // Driver Program
     public static void main(String args[])
     {
         int a = 3 , m = 11 ;
         modInverse(a, m);
     }
}
  
// This code is contributed by Nikita Tiwari.

Python3

# Python3 program to find modular
# inverse of a under modulo m
  
# This program works only if m is prime.
  
# Function to find modular
# inverse of a under modulo m
# Assumption: m is prime
def modInverse(a, m) :
      
     g = gcd(a, m)
      
     if (g ! = 1 ) :
         print ( "Inverse doesn't exist" )
          
     else :
          
         # If a and m are relatively prime, # then modulo inverse is a^(m-2) mode m
         print ( "Modular multiplicative inverse is " , power(a, m - 2 , m))
      
# To compute x^y under modulo m
def power(x, y, m) :
      
     if (y = = 0 ) :
         return 1
          
     p = power(x, y / / 2 , m) % m
     p = (p * p) % m
  
     if (y % 2 = = 0 ) :
         return p 
     else : 
         return ((x * p) % m)
  
# Function to return gcd of a and b
def gcd(a, b) :
     if (a = = 0 ) :
         return b
          
     return gcd(b % a, a)
      
  
# Driver Program
a = 3 ; m = 11
modInverse(a, m)
  
  
# This code is contributed by Nikita Tiwari.

C#

// C# program to find modular 
// inverse of a under modulo m
// This program works only if 
// m is prime.
using System;
class GFG {
  
     // Function to find modular
     // inverse of a under modulo 
     // m Assumption: m is prime
     static void modInverse( int a, int m)
     {
         int g = gcd(a, m);
         if (g != 1)
         Console.Write( "Inverse doesn't exist" );
         else
         {
             // If a and m are relatively
             // prime, then modulo inverse
             // is a^(m-2) mode m
             Console.Write( "Modular multiplicative inverse is " +
                                              power(a, m - 2, m));
         }
     }
      
     // To compute x^y under
     // modulo m
     static int power( int x, int y, int m) 
     {
         if (y == 0)
             return 1;
          
         int p = power(x, y / 2, m) % m;
         p = (p * p) % m;
      
         if (y % 2 == 0)
             return p;
         else
             return (x * p) % m;
     }
      
     // Function to return 
     // gcd of a and b
     static int gcd( int a, int b) 
     {
         if (a == 0)
             return b;
         return gcd(b % a, a);
     }
      
     // Driver Code
     public static void Main()
     {
         int a = 3, m = 11;
         modInverse(a, m);
     }
}
  
// This code is contributed by nitin mittal.

的PHP

<?php
// PHP program to find modular 
// inverse of a under modulo m
// This program works only if m 
// is prime.
  
// Function to find modular inverse
// of a under modulo m
// Assumption: m is prime
function modInverse( $a , $m )
{
     $g = gcd( $a , $m );
     if ( $g != 1)
         echo "Inverse doesn't exist" ;
     else
     {
          
         // If a and m are relatively 
         // prime, then modulo inverse
         // is a^(m-2) mode m
         echo "Modular multiplicative inverse is "
                         , power( $a , $m - 2, $m );
     }
}
  
// To compute x^y under modulo m
function power( $x , $y , $m )
{
     if ( $y == 0)
         return 1;
     $p = power( $x , $y / 2, $m ) % $m ;
     $p = ( $p * $p ) % $m ;
  
     return ( $y % 2 == 0)? $p : ( $x * $p ) % $m ;
}
  
// Function to return gcd of a and b
function gcd( $a , $b )
{
     if ( $a == 0)
         return $b ;
     return gcd( $b % $a , $a );
}
  
     // Driver Code
     $a = 3;
     $m = 11;
     modInverse( $a , $m );
      
// This code is contributed by anuj_67.
?>

输出：

Modular multiplicative inverse is 4

该方法的时间复杂度为O(Log m)

我们讨论了三种找到乘法逆模m的方法。

1)天真的方法, O(m)

2)扩展的Euler GCD算法O(Log m)[当a和m为互素时有效]

3)费马小定理, O(Log m)[当'm'为素数时有效]

应用范围：

模乘法逆的计算是

RSA公钥加密方法

.

参考文献：

https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

http://e-maxx.ru/algo/reverse_element

本文作者：

安库尔

。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: