ORIGIN

Extended Euclid and Inverse element

Algorithm 2 mins395 words

Today’s importance is inverse element, however, inverse element calculation is based on the extended Euclid algorithm. At first, we need to know the Euclid’s algorithm.

A much more efficient method is the Euclidean algorithm, which uses a division algorithm such as long division in combination with the observation that the gcd of two numbers also divides their difference. –from Wikipedia

Extended Euclidean

ax+by=gcd(a,b)

From the Euclid Method of calculating gcd, we know that
gcd(a,b)=gcd(b,a


We set another function
bx1+(a

So, combine the first function with the third function we got
ax+by=bx1+(a

We define that if
b=0:x=1,y=0

So we can write our function in this way

C
1
2
3
4
5
6
7
8
typedef pair<int,int> P;
P gcdEx(int a, int b){
if(b == 0) return P(1, 0);
else{
P p = gcdEx(b, a % b);
return P(t.second, t.first - (a / b) * t.second);
}
}

The previous one is the direct one we can get from the mathematical function. Here is a better way of writing it.

C
1
2
3
4
5
6
7
8
void gcdEx(int a, int b, int &x, int &y){
if(b == 0){
x = 1; y = 0;
}else{
gcdEx(b, a % b, y, x);
y -= a / b * x;
}
}

Inverse Element

ax1(mod b)

There is a inverse element only if a and b are both prime numbers. The equation above means both side mod b at the same time is equal. x is a reverse element of a under mod b.

We can change the equation into this.
ax mod m=1 axmy=1


y is the middle element used to solve x.

So the code looks like this.

C++
1
2
3
int x, y;
gcdEx(a, m, x, y);
x = (x % m + m) % m;

x is the inverse element of a.

Powered By Valine
v1.5.1
TOP
COMMENT
  • ABOUT
  • |
o_oyao
  The Jigsaw puzzle is incomplete with even one missing piece. And I want to be the last piece to make the puzzle complete.
Like my post?
Default QR Code
made with ❤️ by o_oyao
©o_oyao 2019-2025

31042 | 87