modular_division.cpp File Reference

An algorithm to divide two numbers under modulo p Modular Division More...

#include <cassert>
#include <cstdint>
#include <iostream>

Include dependency graph for modular_division.cpp:

Go to the source code of this file.

Namespaces
namespace	math
	for assert
namespace	modular_division
	Functions for Modular Division implementation.

Functions
uint64_t	math::modular_division::power (uint64_t a, uint64_t b, uint64_t c)
	This function calculates a raised to exponent b under modulo c using modular exponentiation.
uint64_t	math::modular_division::mod_division (uint64_t a, uint64_t b, uint64_t p)
	This function calculates modular division.
static void	test ()
int	main (int argc, char *argv[])
	Main function.

Detailed Description

An algorithm to divide two numbers under modulo p Modular Division

To calculate division of two numbers under modulo p Modulo operator is not distributive under division, therefore we first have to calculate the inverse of divisor using Fermat's little theorem Now, we can multiply the dividend with the inverse of divisor and modulo is distributive over multiplication operation. Let, We have 3 numbers a, b, p To compute (a/b)p (a/b)p ≡ (a*(inverse(b)))p ≡ ((ap)*inverse(b)p)p NOTE: For the existence of inverse of 'b', 'b' and 'p' must be coprime For simplicity we take p as prime Time Complexity: O(log(b)) Example: ( 24 / 3 ) % 5 => 8 % 5 = 3 — (i) Now the inverse of 3 is 2 (24 * 2) % 5 = (24 % 5) * (2 % 5) = (4 * 2) % 5 = 3 — (ii) (i) and (ii) are equal hence the answer is correct.

See also

modular_inverse_fermat_little_theorem.cpp, modular_exponentiation.cpp

Author

Shubham Yadav

Definition in file modular_division.cpp.

Function Documentation

main()

int main	(	int	argc,
		char *	argv[] )

Main function.

Parameters

argc	commandline argument count (ignored)
argv	commandline array of arguments (ignored)

Returns

0 on exit

Definition at line 113 of file modular_division.cpp.

                                 {
    test();  // execute the tests
    return 0;
}

mod_division()

uint64_t math::modular_division::mod_division	(	uint64_t	a,
		uint64_t	b,
		uint64_t	p )

This function calculates modular division.

Parameters

a	integer dividend
b	integer divisor
p	integer modulo

Returns

a/b modulo c

Calculate the inverse of b

Calculate the final result

Definition at line 75 of file modular_division.cpp.

                                                          {
    uint64_t inverse = power(b, p - 2, p) % p;  
    uint64_t result =
        ((a % p) * (inverse % p)) % p;  
    return result;
}

power()

uint64_t math::modular_division::power	(	uint64_t	a,
		uint64_t	b,
		uint64_t	c )

This function calculates a raised to exponent b under modulo c using modular exponentiation.

Parameters

a	integer base
b	unsigned integer exponent
c	integer modulo

Returns

a raised to power b modulo c

Initialize the answer to be returned

Update a if it is more than or equal to c

In case a is divisible by c;

If b is odd, multiply a with answer

b must be even now

b = b/2

Definition at line 50 of file modular_division.cpp.

                                                   {
    uint64_t ans = 1;  
    a = a % c;         
    if (a == 0) {
        return 0;  
    }
    while (b > 0) {
        if (b & 1) {
            ans = ((ans % c) * (a % c)) % c;
        }
        b = b >> 1;  
        a = ((a % c) * (a % c)) % c;
    }
    return ans;
}

test()

static void test ( )

static

Function for testing power function. test cases and assert statement.

Returns

void

Definition at line 89 of file modular_division.cpp.

                   {
    uint64_t test_case_1 = math::modular_division::mod_division(8, 2, 2);
    assert(test_case_1 == 0);
    std::cout << "Test 1 Passed!" << std::endl;
    uint64_t test_case_2 = math::modular_division::mod_division(15, 3, 7);
    assert(test_case_2 == 5);
    std::cout << "Test 2 Passed!" << std::endl;
    uint64_t test_case_3 = math::modular_division::mod_division(10, 5, 2);
    assert(test_case_3 == 0);
    std::cout << "Test 3 Passed!" << std::endl;
    uint64_t test_case_4 = math::modular_division::mod_division(81, 3, 5);
    assert(test_case_4 == 2);
    std::cout << "Test 4 Passed!" << std::endl;
    uint64_t test_case_5 = math::modular_division::mod_division(12848, 73, 29);
    assert(test_case_5 == 2);
    std::cout << "Test 5 Passed!" << std::endl;
}