C Code For Solving Modular Linear Equations
The Extended Euclid’s Algorithm solves the equation of the form
Congruence Modulo
You just saw a weird kind of mathematical expression of the form
\[ A \equiv B (\text { mod } C) \]
This says that A is congruent to B modulo C. What does it mean? Before I tell you the meaning of above operator, please note that this kind of expression is every common in number theory. If you are interested in Cryptography and starting to learn it, you will encounter this operator numerous time. Lets take an example,
\[ 21 \equiv 5 (\text { mod } 4) \]
A symbol $equiv$ means “Equivalence”. In above equation, 21 and 5 are equivalent. This is because 21 modulo 4 = 1 is equal to 5 modulo 4 = 1. Another example is $51 \equiv 16 (\text{ mod } 7)$
The value of x can be more than one depending upon the GCD of a and n. There are always d number of solutions of x where d = GCD(a, n). If a and n are relatively prime i.e. GCD is 1, there is only one unique solution and this is very important for calculating secret key in RSA algorithm.
The following code solves the above relation. The code is also available on GitHub.
#include <stdio.h>
#include <math.h>
typedef struct {
int d;
int x;
int y;
} EE;
EE extended_euclid(int a, int b) {
EE ee1, ee2, ee3;
if (b == 0) {
ee1.d = a;
ee1.x = 1;
ee1.y = 0;
return ee1;
} else {
ee2 = extended_euclid(b, a % b);
ee3.d = ee2.d;
ee3.x = ee2.y;
ee3.y = ee2.x - floor(a / b) * ee2.y;
return ee3;
}
}
// Copied from
// https://stackoverflow.com/questions/11720656/modulo-operation-with-negative-numbers
int modulo(int x, int N){
return (x % N + N) % N;
}
void modular_linear_equation_solver(int a, int b, int n){
EE ee;
int x0, i;
ee = extended_euclid(a, n);
if (b % ee.d == 0) {
x0 = modulo(ee.x * (b/ee.d), n);
for (i = 0; i < ee.d; i++) {
printf("Solution %d: %d\n", i + 1, modulo(x0 + i * (n / ee.d), n));
}
} else {
printf("No Solutions\n");
}
}
int main(int argc, char* argv[]) {
int a = 17, b = 1, n = 60;
modular_linear_equation_solver(a, b, n);
return 0;
}
