算法设计：模划分详细实现

本文概述

• C
• Python 3
• 的PHP

给定三个正数a, b和m。在模m下计算a/b。任务基本上是找到一个数字c, 使得(b * c)％m = a％m。

例子：

Input  : a  = 8, b = 4, m = 5
Output : 2

Input  : a  = 8, b = 3, m = 5
Output : 1
Note that (1*3)%5 is same as 8%5

Input  : a  = 11, b = 4, m = 5
Output : 4
Note that (4*4)%5 is same as 11%5

以下文章是此前提条件。

模乘逆

扩展的欧几里得算法

我们可以一直做模划分吗？

答案是不"。首先, 像普通算术一样, 不定义除以0。例如, 不允许使用4/0。在模算术中, 不仅不允许4/0, 而且也不允许模6下的4/12。原因是, 当模数为6时12等于0。

什么时候定义模划分？

当除数的模逆存在时, 定义模除法。整数" x"的倒数是另一个整数" y", 使得(x * y)％m = 1, 其中m是模数。

逆何时存在？如前所述

这里

, 如果" a"和" m"是互质的, 则它们的模数" m"下的数字为" a"的倒数, 即它们的GCD为1。

如何找到模部门？

The task is to compute a/b under modulo m.
1) First check if inverse of b under modulo m exists or not. 
    a) If inverse doesn't exists (GCD of b and m is not 1), print "Division not defined"
    b) Else return  "(inverse * a) % m"

C

//C++ program to do modular division
#include<iostream>
using namespace std;
  
//C function for extended Euclidean Algorithm
int gcdExtended( int a, int b, int *x, int *y);
  
//Function to find modulo inverse of b. It returns
//-1 when inverse doesn't
int modInverse( int b, int m)
{
     int x, y; //used in extended GCD algorithm
     int g = gcdExtended(b, m, &x, &y);
  
     //Return -1 if b and m are not co-prime
     if (g != 1)
         return -1;
  
     //m is added to handle negative x
     return (x%m + m) % m;
}
  
//Function to compute a/b under modlo m
void modDivide( int a, int b, int m)
{
     a = a % m;
     int inv = modInverse(b, m);
     if (inv == -1)
        cout <<"Division not defined" ;
     else
        cout <<"Result of division is " <<(inv * a) % m;
}
  
//C function for extended Euclidean Algorithm (used to
//find modular inverse.
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  = 8, b = 3, m = 5;
     modDivide(a, b, m);
     return 0;
}

Python 3

# Python3 program to do modular division
import math
  
# Function to find modulo inverse of b. It returns 
# -1 when inverse doesn't 
# modInverse works for prime m
def modInverse(b, m):
     g = math.gcd(b, m) 
     if (g ! = 1 ):
         # print("Inverse doesn't exist") 
         return - 1
     else : 
         # If b and m are relatively prime, # then modulo inverse is b^(m-2) mode m 
         return pow (b, m - 2 , m)
  
  
# Function to compute a/b under modulo m 
def modDivide(a, b, m):
     a = a % m
     inv = modInverse(b, m)
     if (inv = = - 1 ):
         print ( "Division not defined" )
     else :
         print ( "Result of Division is " , (inv * a) % m)
  
# Driver Program 
a = 8
b = 3
m = 5
modDivide(a, b, m)
  
# This code is Contributed by HarendraSingh22

的PHP

<?php
//PHP program to do modular division
  
//Function to find modulo inverse of b. 
//It returns -1 when inverse doesn't
function modInverse( $b , $m )
{
     $x = 0;
     $y = 0; //used in extended GCD algorithm
     $g = gcdExtended( $b , $m , $x , $y );
  
     //Return -1 if b and m are not co-prime
     if ( $g != 1)
         return -1;
  
     //m is added to handle negative x
     return ( $x % $m + $m ) % $m ;
}
  
//Function to compute a/b under modlo m
function modDivide( $a , $b , $m )
{
     $a = $a % $m ;
     $inv = modInverse( $b , $m );
     if ( $inv == -1)
         echo "Division not defined" ;
     else
         echo "Result of division is " . 
                       ( $inv * $a ) % $m ;
}
  
//function for extended Euclidean Algorithm 
//(used to find modular inverse.
function gcdExtended( $a , $b , & $x , & $y )
{
     //Base Case
     if ( $a == 0)
     {
         $x = 0;
         $y = 1;
         return $b ;
     }
  
     $x1 = 0;
     $y1 = 0; //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 = 8;
$b = 3;
$m = 5;
modDivide( $a , $b , $m );
  
//This code is contributed by mits 
?>

输出如下：

Result of division is 1

模除法不同于加法, 减法和乘法。

一个区别是划分并不总是存在的(如上所述)。以下是另一个区别。

Below equations are valid
(a * b) % m = ((a % m) * (b % m)) % m
(a + b) % m = ((a % m) + (b % m)) % m

//m is added to handle negative numbers
(a - b + m) % m = ((a % m) - (b % m) + m) % m 

But, (a /b) % m may NOT be same as ((a % m)/(b % m)) % m

For example, a = 10, b = 5, m = 5. 
   (a /b) % m is 2, but ((a % m) /(b % m)) % m 
                          is not defined.

参考文献：

http://www.doc.ic.ac.uk/~mrh/330tutor/ch03.html

本文作者：德莱拉吉·古普塔(Dheeraj Gupta)。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。