Рубрики

Модульное подразделение

Даны три положительных числа a, b и m. Вычислить a / b по модулю m. Задача в основном состоит в том, чтобы найти число 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 не допускается, но 4/12 по модулю 6 также не допускается. Причина в том, что 12 равно 0, когда модуль равен 6.

Когда определяется модульное деление?
Модульное деление определяется, когда существует модульная инверсия делителя. Инверсия целого числа «x» — это другое целое число «y», такое, что (x * y)% m = 1, где m — модуль.
Когда существует обратное? Как обсуждалось здесь , обратное число «a» существует по модулю «m», если «a» и «m» взаимно просты, т. Е. 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 ++ программа для модульного деления
#include<iostream>

using namespace std;

  
// C-функция для расширенного евклидова алгоритма

int gcdExtended(int a, int b, int *x, int *y);

  
// Функция для нахождения по модулю обратной величины b. Возвращается
// -1, когда инверсия не

int modInverse(int b, int m)

{

    int x, y; // используется в расширенном алгоритме GCD

    int g = gcdExtended(b, m, &x, &y);

  

    // Возвращаем -1, если b и m не взаимно просты

    if (g != 1)

        return -1;

  

    // добавлен m для обработки отрицательного x

    return (x%m + m) % m;

}

  
// Функция для вычисления a / b под 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-функция для расширенного евклидова алгоритма (используется для
// найти модульное обратное.

int gcdExtended(int a, int b, int *x, int *y)

{

    // Базовый вариант

    if (a == 0)

    {

        *x = 0, *y = 1;

        return b;

    }

  

    int x1, y1; // Для сохранения результатов рекурсивного вызова

    int gcd = gcdExtended(b%a, a, &x1, &y1);

  

    // Обновляем x и y, используя рекурсивные результаты

    // вызов

    *x = y1 - (b/a) * x1;

    *y = x1;

  

    return gcd;

}

  
// Программа для водителя

int main()

{

    int  a  = 8, b = 3, m = 5;

    modDivide(a, b, m);

    return 0;

}

Python 3

# Python3 программа для модульного деления

import math

  
# Функция для поиска по модулю обратной величины b. Возвращается
# -1, когда обратный не
# modInverse работает для простого m

def modInverse(b,m):

    g = math.gcd(b, m) 

    if (g != 1):

        # print («Обратного не существует»)

        return -1

    else

        # Если b и m относительно простые,

        # тогда по модулю обратный это b ^ (m-2) mode m

        return pow(b, m - 2, m)

  

  
# Функция для вычисления a / b по модулю 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)

  
# Драйверная программа

a = 8

b = 3

m = 5

modDivide(a, b, m)

  
# Этот код предоставлен HarendraSingh22

PHP

<?php
// PHP программа для модульного деления

  
// Функция для нахождения по модулю обратной величины b.
// Возвращает -1, когда обратное не

function modInverse($b, $m)

{

    $x = 0;

    $y = 0; // используется в расширенном алгоритме GCD

    $g = gcdExtended($b, $m, $x, $y);

  

    // Возвращаем -1, если b и m не взаимно просты

    if ($g != 1)

        return -1;

  

    // добавлен m для обработки отрицательного x

    return ($x % $m + $m) % $m;

}

  
// Функция для вычисления a / b под 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 gcdExtended($a, $b, &$x, &$y)

{

    // Базовый вариант

    if ($a == 0)

    {

        $x = 0;

        $y = 1;

        return $b;

    }

  

    $x1 = 0;

    $y1 = 0; // Для сохранения результатов рекурсивного вызова

    $gcd = gcdExtended($b % $a, $a, $x1, $y1);

  

    // Обновляем x и y, используя результаты

    // рекурсивный вызов

    $x = $y1 - (int)($b / $a) * $x1;

    $y = $x1;

  

    return $gcd;

}

  
// Код драйвера

$a = 8;

$b = 3;

$m = 5;

modDivide($a, $b, $m);

  
// Этот код предоставлен 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 . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Модульное подразделение

0.00 (0%) 0 votes