maths.modular_division

Functions

extended_euclid(→ tuple[int, int])	Extended Euclid
extended_gcd(→ tuple[int, int, int])	Extended Euclid's Algorithm : If d divides a and b and d = a*x + b*y for integers x
greatest_common_divisor(→ int)	Euclid's Lemma : d divides a and b, if and only if d divides a-b and b
invert_modulo(→ int)	This function find the inverses of a i.e., a^(-1)
modular_division(→ int)	Modular Division :
modular_division2(→ int)	This function used the above inversion of a to find x = (b*a^(-1))mod n

Module Contents

maths.modular_division.extended_euclid(a: int, b: int) → tuple[int, int]

Extended Euclid >>> extended_euclid(10, 6) (-1, 2)

>>> extended_euclid(7, 5)
(-2, 3)

maths.modular_division.extended_gcd(a: int, b: int) → tuple[int, int, int]

Extended Euclid’s Algorithm : If d divides a and b and d = a*x + b*y for integers x and y, then d = gcd(a,b) >>> extended_gcd(10, 6) (2, -1, 2)

>>> extended_gcd(7, 5)
(1, -2, 3)

** extended_gcd function is used when d = gcd(a,b) is required in output

maths.modular_division.greatest_common_divisor(a: int, b: int) → int

Euclid’s Lemma : d divides a and b, if and only if d divides a-b and b Euclid’s Algorithm

>>> greatest_common_divisor(7,5)
1

NoteIn number theory, two integers a and b are said to be relatively prime,

mutually prime, or co-prime if the only positive integer (factor) that divides both of them is 1 i.e., gcd(a,b) = 1.

>>> greatest_common_divisor(121, 11)
11

maths.modular_division.invert_modulo(a: int, n: int) → int

This function find the inverses of a i.e., a^(-1)

>>> invert_modulo(2, 5)
3

>>> invert_modulo(8,7)
1

maths.modular_division.modular_division(a: int, b: int, n: int) → int

Modular Division : An efficient algorithm for dividing b by a modulo n.

GCD ( Greatest Common Divisor ) or HCF ( Highest Common Factor )

Given three integers a, b, and n, such that gcd(a,n)=1 and n>1, the algorithm should return an integer x such that 0≤x≤n-1, and b/a=x(modn) (that is, b=ax(modn)).

Theorem: a has a multiplicative inverse modulo n iff gcd(a,n) = 1

This find x = b*a^(-1) mod n Uses ExtendedEuclid to find the inverse of a

>>> modular_division(4,8,5)
2

>>> modular_division(3,8,5)
1

>>> modular_division(4, 11, 5)
4

maths.modular_division.modular_division2(a: int, b: int, n: int) → int

This function used the above inversion of a to find x = (b*a^(-1))mod n

>>> modular_division2(4,8,5)
2

>>> modular_division2(3,8,5)
1

>>> modular_division2(4, 11, 5)
4