modular_division.cpp File Reference

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

#include <cassert>
#include <iostream>

Include dependency graph for modular_division.cpp:

Namespaces
namespace	math
	for IO operations
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

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

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

Here is the call graph for this function:

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

                                                          {
    uint64_t inverse = power(b, p - 2, p) % p;  /// Calculate the inverse of b
    uint64_t result =
        ((a % p) * (inverse % p)) % p;  /// Calculate the final result
    return result;
}

Here is the call graph for this function:

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

                                                   {
    uint64_t ans = 1;  /// Initialize the answer to be returned
    a = a % c;         /// Update a if it is more than or equal to c
    if (a == 0) {
        return 0;  /// In case a is divisible by c;
    }
    while (b > 0) {
        /// If b is odd, multiply a with answer
        if (b & 1) {
            ans = ((ans % c) * (a % c)) % c;
        }
        /// b must be even now
        b = b >> 1;  /// b = b/2
        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

                   {
    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;
}

Here is the call graph for this function: