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
-GitHub repository:
Modular Arithmetic Source Code
-Article
BASICS
- Reflexibity
- Simmetry
- Transivity
if ,
,
then:
)
-
-
-
Great Common Divisor (GCD)
Euclides Algorithm is used to solve this problem.
Least Common Multiple (LCM)
We can calculate the LCM using GCD:
Bezout’s Theorem
Using Euclides Algorithm we are able to find and
, where:
Number Decomposition
This algorithm could be optimized because we only need to look numbers
below , and thus, the time is reduced.
a^b(mod m)
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.
and
Primality Test
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
\section{Inverse}
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: