This library provides the basics of modular arithmetic operations:
- Great Common Divisor (GCD)
- Least Common Multiple (LCM)
- Bezout solver
- Decomposition number algorithm
- Euler’s totient function
- Primality Test
- Find next Prime
- Inverse function
- Solver for 1 equation
- Solver for multiple equations
Modular Arithmetic Source Code
Great Common Divisor (GCD)
Euclides Algorithm is used to solve this problem.
Least Common Multiple (LCM)
We can calculate the LCM using GCD:
Using Euclides Algorithm we are able to find and, where:
This algorithm could be optimized because we only need to look numbers
below , and thus, the time is reduced.
we are not always to compute high numbers with big exponents, and
hence we need another way that simplifies:
we write b in binary, such as: ,
where is 0 or 1.
This algorithm tells you, whether a number is prime or not (optimized).
Find next Prime
This function is important in cryptography. It uses an initial number and finds the next prime over the number given.
Euler’s Totient Function
We need the number decomposition algorithm mentioned before.
Linear Equation Solver
To solve the equation, we divide by
We use Bezout:
Then, we multiply by :
There are solutions for this equation
The inverse of a number in mod m is calculated using the linear solver:
System of Equations
Solving a system of equations is done by constantly solving two equations.
, where and are the solutions
for each equation.
We repeat the process: