Modular Arithmetic Library

Modular Arithmetic Library in C++

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
  • a^{b}(mod\:m)
  • Primality Test
  • Find next Prime
  • Inverse function
  • Solver for 1 equation
  • Solver for multiple equations
-GitHub repository:

Modular Arithmetic Source Code

-Article

Modular Arithmetic Article


BASICS

a\equiv b(mod\:m)\leftrightarrow a-b=\lambda m,\lambda\text{\ensuremath{\in\mathbb{Z}}}

  •  Reflexibity
  • Simmetry
  • Transivity

if a_{1}\equiv b_{1}(mod\:m),a_{2}\equiv b_{2}(mod\:m),a_{3}\equiv b_{3}(mod\:m)

then:

  • a+k\equiv b+k(mod\:m)
  • ak\equiv bk(mod\:m)
  • a_{1}+a_{2}\equiv b_{1}+b_{2}(mod\:m)
  • a_{1}a_{2}\equiv b_{1}b_{2}(mod\:m)
  • a^{k}\equiv b^{k}(mod\:m)
  • a+k\equiv b+k(mod\:m)\rightarrow a\equiv b(mod\:m)
  • ak\equiv bk(mod\:m)\land gcd(k,m)=1\rightarrow a\equiv b(mod\:m)
  • a^{-1}\leftrightarrow gcd(a,m)=1
  • a^{-1}\equiv b^{-1}(mod\:m)
  •  ax\equiv b(mod\:m)\rightarrow x=a^{-1}b(mod\:m)
  •  a^{\phi(m)}\equiv1(mod\:m)
  •  (p-1)!\equiv-1(mod\:m)

Great Common Divisor (GCD)

Euclides Algorithm is used to solve this problem.

    \[ a=bq+r \]

    \[ gcd(a,b)=gcd(b,r)=\ldots=gcd(c,1)=c \]

Least Common Multiple (LCM)

We can calculate the LCM using GCD:

    \[ lcm(a,b)=ab/gcd(a,b) \]

Bezout’s Theorem

Using Euclides Algorithm we are able to find uandv, where:

    \[ gcd(a,b)=au+bv:u,v\in\mathbb{{Z}} \]

Number Decomposition

This algorithm could be optimized because we only need to look numbers

below \sqrt{n}, 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: \alpha_{1}\alpha_{2}\dots\alpha_{n},

where \alpha_{i}is 0 or 1.

a^{b}(mod\:m)=a^{\alpha_{1}}\dots a^{\alpha_{n}}(mod\:m) and a^{\alpha_{n+1}}(mod\:m)=(a^{\alpha_{n}})^{2}(mod\:m)

 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.

    \[ \phi(n)=(p_{1}-1)p_{1}^{\alpha_{1}-1}*\dots*(p_{n}-1)p_{n}^{\alpha_{n}-1} \]

Linear Equation Solver

    \[ ax\equiv b(mod\:m),b|gcd(a,m) \]

To solve the equation, we divide by d:=gcd(a,m)

    \[ a'dx\equiv b'd(mod\:m'd)\rightarrow a'x\equiv b'(mod\:m') \]

We use Bezout:

    \[ a'u+m'v=1 \]

Then, we multiply by b':

    \[ b'=a'bu+m'vb\equiv a'du(mod\:m) \]

    \[ x=du \]

    \[ x_{0}=du+0m',x_{1}=du+1m',\dots,x_{d-1}=du+(d-1)m' \]

There are dsolutions for this equation

\section{Inverse}

The inverse of a number in mod m is calculated using the linear solver:

a^{-1}x\equiv1(mod\:m)

System of Equations

Solving a system of equations is done by constantly solving two equations.

    \[ \begin{cases} a_{1}x\equiv b_{1}(mod\:m_{1})\\ a_{2}x\equiv b_{2}(mod\:m_{2}) \end{cases} \]

    \[ gcd(m_{1},m_{2})=1=m_{1}u+m_{2}v \]

x=m_{1}ux_{2}+m_{2}vx_{1}, where x_{1}and x_{2}are the solutions

for each equation.

We repeat the process:

    \[ \begin{cases} x\equiv b(mod\:m_{1}m_{2})\\ a_{3}\equiv b_{3}(mod\:m_{3}) \end{cases} \]

Leave a Reply

Your email address will not be published. Required fields are marked *