Author: Alessandro Conti - AlessandroConti11
License: MIT license.
Tags: #Baby-Step_Giant-Step, #C, #Chinese_Reminder_Theorem, #discrete_logarithm, #Extended_Euclidean_Algorithm, #factorisation, #Fermat_Pseudoprime, #Jacobi_Symbol, #Legendre_Symbol, #linear_diophantine_equation, #modular_arithmetic, #modular_matrix, #modular_square_root, #prime_number, #Tonelli-Shanks.
The project aims to create a library that contains all useful functions for modular arithmetic.
| Operation | Function | Description | Example of Mathematical Representation | Order of the Matrices |
|---|---|---|---|---|
| compute the sum modulo m | long long int sum(long long int a, long long int b, long long int m) | compute the sum of two numbers modulo m | ||
| compute the difference modulo m | long long int sub(long long int a, long long int b, long long int m) | compute the difference of two numbers modulo m | ||
| compute the product modulo m | long long int product(long long int a, long long int b, long long int m) | compute the product of two numbers modulo m | ||
| compute the division modulo m | long long int division(long long int a, long long int b, long long int m) | compute the division of two numbers modulo m | ||
| compute the power modulo m | long long int power(long long int a, long long int exp, long long int m) | compute the power elevation of a number given an exponent modulo m | ||
| compute the square root modulo a prime number | long long int *TonelliShanksAlgorithm(long long int a, long long int p) | compute the square root of a number modulo p using the Tonelli-Shanks algorithm | ||
| compute the square root modulo m | long long int *squareRoot(long long int a, long long int m, long long int *numberOfSquareRoots) | compute the square root of a number that is a square residue of modulus m | ||
| compute the discrete logarithm modulo m | long long int discreteLogarithm(long long int base, long long int b, long long int m) | compute the discrete logarithm modulo n of a base number using the Baby-Step Giant-Step algorithm | ||
| compute the solution of a system of modular linear equation - Chinese Reminder Theorem | long long int chineseReminderTheorem(long long int numberOfEquation, long long int *a, long long int *m) | compute the solution of a system of modular linear equation using the Chinese Reminder theorem | $\begin{cases}x = a_1 \pmod{m_1} \ \vdots \ x = a_i \pmod{m_i}\end{cases}$ | |
| compute the solution of a linear diophantine equation | void diophantineEquation(long long int a, long long int *x, long long int b, long long int *y, long long int c) | compute the solution of a linear diophantine equation | $ax + by = c \quad \text{where: } \begin{cases}x \in \mathbb{N} \ y \in \mathbb{N}\end{cases}$ | |
| check if two numbers are congruent modulo m | long long int areCongruent(long long int a, long long int b, long long int m) | check if two number are congruent modulo m | ||
| check if two numbers are coprime | long long int areCoPrime(long long int a, long long int n) | check if two numbers are coprime using the gcd method | ||
| check if the first number is a divisor of the second number | long long int isDivisor(long long int n, long long int m) | check if the first number is a divisor of the second one | ||
| check if a number is Fermat's Pseudoprime to a | long long int isFermatPseudoPrime(long long int a, long long int n) | check if the number is Fermat's Pseuodoprime to a | ||
| check if a number is a prime number | long long int isPrime(long long int n) | check if the number is a prime number using the Eratosthenes sieve | ||
| check if a number admits the square root modulo n | long long int isSquareNumber(long long int a, long long int n) | check if the number admits the square root modulo n, so check if the number is a quadratic residue modulo n | ||
| check if a number is a primitive root modulo n | long long int isPrimitiveRoot(long long int a, long long int n) | check if the number is a primitive root modulo n | ||
| check if a number is a perfect square | long long int isPerfectSquare(long long int n) | check if the number is a perfect square | ||
| compute the Greatest Common Divisor | long long int gcd(long long int n, long long int m) | compute the Greatest Common Divisor using the Euclid's algorithm | ||
| compute the Greatest Common Divisor using the Extended Euclidean algorithm | long long int extendedGCD(long long int n, long long int m, long long int *x, long long int *y) | compute the Greatest Common Divisor using the Extended Euclidean algorithm | ||
| compute the modulus of two integer | long long int mod(long long int n, long long int m) | compute the modulus of two numbers | ||
| compute a number congruent with the one given | long long int congruentNumber(long long int a, long long int m) | compute a number congruent with the given one | ||
| compute the modular reduction | long long int modularReduction(long long int n, long long int m) | compute the modular reduction of the given number | ||
| compute the modular inversion | long long int modularInverse(long long int n, long long int m) | compute the modular inversion of the given number if the number is coprime with the modulo value | ||
| factorize a number by splitting it into two of its dividends - Fermat's Factorization Method | long long int *realFermatFactorisation(long long int n) | factorize the number by splitting it into two of its dividend using the Fermat's factorisation method | ||
| factorize a number by splitting it into all of its dividends | long long int *factorisation(long long int n, long long int *factors) | factor the number by dividing it into all its dividends using a different strategy depending on the type of number you entered | ||
| compute the value of Euler Function for the given number | long long int EulerFunction(long long int n) | compute the value of the Euler function for the given number | ||
| compute the list of prime numbers up to the n-th | long long int *primeNumberList(long long int n, long long int *primeSize) | compute the list of the prime numbers up to the n-th number | ||
| search for the n-th prime number | long long int nthPrimeNumber(long long int n) | search for the n-th prime number | ||
| found the prime number following a given number | long long int nextPrimeNumber(long long int n) | found the prime number following the given number | ||
| compute the list of primitive roots modulo n | long long int *primitiveRoots(long long int n, long long int *primitiveRootsSize) | compute the list of primitive roots modulo n | ||
| compute the list of quadratic residual modulo n | long long int *quadraticResiduals(long long int n, long long int *quadraticResidualSize) | compute the list of quadratic residuals modulo n | ||
| compute the Legendre Symbol | long long int LegendreSymbol(long long int a, long long int p) | compute the Legendre symbol | $\left(\frac{a}{p}\right) = \begin{cases}1 & \textit{a}\text{ is a quadratic residue modulo }\textit{p } \land a \not\equiv 0 \pmod{p} \ -1 & \textit{a}\text{ is a quadratic nonresidue modulo }\textit{p} \ 0 & a \equiv 0 \pmod{p}\end{cases}$ | |
| compute the Jacobi Symbol | long long int JacobiSymbol(long long int a, long long int n) | compute the Jacobi symbol | ||
| print matrix modulo n | void printMatrixModulo(matrix *a, long long int n) | print the matrix modulo m | ||
| check if a matrix has all integer elements | long long int isIntegerMatrix(matrix *a) | check if the matrix has all integer elements | ||
| compute the matrix modulo n | void modularMatrix(matrix *a, matrix *modMatrix, long long int n) | compute the matrix modulo m | ${[A]} = \begin{bmatrix}a_{(0, 0)} & a_{(0, 1)} & a_{(0, 2)} & \cdots & a_{(0, m - 1)} \\ a_{(1, 0)} & a_{(1, 1)} & a_{(1, 2)} & \cdots & a_{(1, m - 1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{(k - 1, 0)} & a_{(k - 1, 1)} & a_{(k - 1, 2)} & \cdots & a_{(k - 1, m - 1)}\end{bmatrix} \pmod{n}$ | |
| compute the matrix inversion modulo n | void inverseMatrixModulo(matrix *a, matrix *inv, long long int n) | compute the matrix inversion modulo m using the cofactor matrix method | ${[A]}^{-1} = {\frac{1}{det(A)}}{\begin{bmatrix} Cof(0;0) & Cof(0;1) & Cof(0;2) & \cdots & Cof(0;k-1) \\ Cof(1;0) & Cof(1;1) & Cof(1;2) & \cdots & Cof(1;k-1) \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ Cof(k-1;0) & Cof(k-1;1) & Cof(k-1;2) & \cdots & Cof(k-1;k-1) \end{bmatrix}}^T \pmod{n}$ | |
| compute the sum of matrices modulo n | void sumMatrixModulo(matrix *a, matrix *b, matrix *res, long long int n) | compute the sum of two matrices modulo n | ${[A + B]} = \begin{bmatrix} {a_{(0;0)}+b_{(0;0)}} & {a_{(0;1)}+b_{(0;1)}} & {a_{(0;2)}+b_{(0;2)}} & \cdots & {a_{(0;m-1)}+b_{(0;m-1)}} \\ {a_{(1;0)}+b_{(1;0)}} & {a_{(1;1)}+b_{(1;1)}} & {a_{(1;2)}+b_{(1;2)}} & \cdots & {a_{(1;m-1)}+b_{(1;m-1)}} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {a_{(k-1;0)}+b_{(k-1;0)}} & {a_{(k-1;1)}+b_{(k-1;1)}} & {a_{(k-1;2)}+b_{(k-1;2)}} & \cdots & {a_{(k-1;m-1)}+b_{(k-1;m-1)}} \end{bmatrix} \pmod{n}$ | |
| compute the difference of matrices modulo n | void subMatrixModulo(matrix *a, matrix *b, matrix *res, long long int n) | compute the difference of two matrices modulo n | ${[A - B]} = \begin{bmatrix} {a_{(0;0)}-b_{(0;0)}} & {a_{(0;1)}-b_{(0;1)}} & {a_{(0;2)}-b_{(0;2)}} & \cdots & {a_{(0;m-1)}-b_{(0;m-1)}} \\ {a_{(1;0)}-b_{(1;0)}} & {a_{(1;1)}-b_{(1;1)}} & {a_{(1;2)}-b_{(1;2)}} & \cdots & {a_{(1;m-1)}-b_{(1;m-1)}} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {a_{(k-1;0)}-b_{(k-1;0)}} & {a_{(k-1;1)}-b_{(k-1;1)}} & {a_{(k-1;2)}-b_{(k-1;2)}} & \cdots & {a_{(k-1;m-1)}-b_{(k-1;m-1)}} \end{bmatrix} \pmod{n}$ | |
| compute the scalar product of matrix modulo n | void scalarProductModulo(long long int scalar, matrix *a, matrix *res, long long int n) | compute the scalar product of an integer number and a matrix modulo n | ${[s \cdot A]} = \begin{bmatrix} {s \cdot a_{(0;0)}} & {s \cdot a_{(0;1)}} & {s \cdot a_{(0;2)}} & \cdots & {s \cdot a_{(0;m-1)}} \\ {s \cdot a_{(1;0)}} & {s \cdot a_{(1;1)}} & {s \cdot a_{(1;2)}} & \cdots & {s \cdot a_{(1;m-1)}} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {s \cdot a_{(k-1;0)}} & {s \cdot a_{(k-1;1)}} & {s \cdot a_{(k-1;2)}} & \cdots & {s \cdot a_{(k-1;m-1)}} \end{bmatrix} \pmod{n}$ | |
| compute the product of matrices modulo n | void productMatrixModulo(matrix *a, matrix *b, matrix *res, long long int n) | compute the product of two matrices modulo n | ${[A \cdot B]} = \begin{bmatrix} {\sum_{j=1}^k{a_{(0;j)} \cdot b_{(j;0)}}} & {\sum_{j=1}^k{a_{(0;j)} \cdot b_{(j;1)}}} & {\sum_{j=1}^k{a_{(0;j)} \cdot b_{(j;2)}}} & \cdots & {\sum_{j=1}^k{a_{(0;j)} \cdot b_{(j;m-1)}}} \\ {\sum_{j=1}^k{a_{(1;j)} \cdot b_{(j;0)}}} & {\sum_{j=1}^k{a_{(1;j)} \cdot b_{(j;1)}}} & {\sum_{j=1}^k{a_{(1;j)} \cdot b_{(j;2)}}} & \cdots & {\sum_{j=1}^k{a_{(1;j)} \cdot b_{(j;m-1)}}} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {\sum_{j=1}^k{a_{(k-1;j)} \cdot b_{(j;0)}}} & {\sum_{j=1}^k{a_{(k-1;j)} \cdot b_{(j;1)}}} & {\sum_{j=1}^k{a_{(k-1;j)} \cdot b_{(j;2)}}} & \cdots & {\sum_{j=1}^k{a_{(k-1;j)} \cdot b_{(j;m-1)}}} \end{bmatrix} \pmod{n}$ | |
| compute the power elevation of a matrix modulo n | void powerMatrixModulo(matrix *a, long long int k, matrix *res, long long int n) | compute the power elevation of the matrix modulo n | ${[A]^k} = \prod^k{\begin{bmatrix} a_{(0;0)} & a_{(0;1)} & a_{(0;2)} & \cdots & a_{(0;m-1)} \\ a_{(1;0)} & a_{(1;1)} & a_{(1;2)} & \cdots & a_{(1;m-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{(m-1;0)} & a_{(m-1;1)} & a_{(m-1;2)} & \cdots & a_{(m-1;m-1)} \end{bmatrix}} \pmod{n}$ | |
| compute the Kronecker product of matrices modulo n | void kroneckerProductMatrixModulo(matrix *a, matrix *b, matrix *res, long long int n) | compute the Kronecker product of two matrices modulo n | ${[A \otimes B]} = \begin{bmatrix} {a_{(0;0)} \cdot [B]} & {a_{(0;1)} \cdot [B]} & {a_{(0;2)} \cdot [B]} & \cdots & {a_{(0;m-1)} \cdot [B]} \\ {a_{(1;0)} \cdot [B]} & {a_{(1;1)} \cdot [B]} & {a_{(1;2)} \cdot [B]} & \cdots & {a_{(1;m-1)} \cdot [B]} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {a_{(k-1;0)} \cdot [B]} & {a_{(k-1;1)} \cdot [B]} & {a_{(k-1;2)} \cdot [B]} & \cdots & {a_{(k-1;m-1)} \cdot [B]} \end{bmatrix} \pmod{n}$ |
- install gcc
sudo apt-get install gcc
- compile the project
gcc -Wall -Werror -O2 -g3 main.c -o EXECUTABLE
- run the project
./EXECUTABLE
The Makefile in the repository can also be used to compile the code.
- this option allows you to compile with the following tags: -Wall -Werror -O2 -g3
make compile
- if you want to specify different tags, you can set them
make compile CFLAGS=YOUR_FLAGS
- if you want to use Address SANitizer
make asan
- if you want to delete some file - default is the executable file
make clean
- If you find a security vulnerability, do NOT open an issue. Email Alessandro Conti instead.
- If you find a bug or error or want to add some other function that is not implemented yet
- FORK the repo
- CLONE the project to your own machine
- COMMIT to your own branch
- PUSH your work back up to your fork
- submit a PULL REQUEST so that I can review your changes
NOTE: Be sure to merge the latest from "upstream" before making a pull request!
Each new function must be documented using the following style:
- Short function description: A brief description explaining what the function does.
- @details: A detailed section describing how the function works, explaining the algorithms and logic used.
- @warning: A section listing all the assumptions made by the function, such as the preconditions that the parameters must fulfil.
- Blank line: Add a blank line to separate the documentation sections.
- @param: A list of the parameters required by the function, each accompanied by a brief description of its role and type.
- @return: A description of what the function returns, including the data type.
Within the function, each variable must be commented out to explain its purpose. In general, any additional comments that might improve understanding of the code are welcome. 😃