I am looking at cryptography, and need to find the inverse of every possible number mod 26. Is there a fast way of this, or am i headed to the algorithm every time?
$\endgroup$ 12 Answers
$\begingroup$Credit to @lulu's comment above.
List down the coprimes of $26$ smaller than itself: $1,3,5,7,9,11,15,17,19,21,23,25$.
Then calculate the inverse of each one.
Here is a piece of C code that you might find useful:
int Inverse(int n,int a)
{ int x1 = 1; int x2 = 0; int y1 = 0; int y2 = 1; int r1 = n; int r2 = a; while (r2 != 0) { int r3 = r1%r2; int q3 = r1/r2; int x3 = x1-q3*x2; int y3 = y1-q3*y2; x1 = x2; x2 = x3; y1 = y2; y2 = y3; r1 = r2; r2 = r3; } return y1>0? y1:y1+n;
}
void Run()
{ int arr[] = {1,3,5,7,9,11,15,17,19,21,23,25}; for (int i=0; i<sizeof(arr)/sizeof(*arr); i++) printf("%d - %d\n",arr[i],Inverse(26,arr[i]));
}The corresponding output is: $1,9,21,15,3,19,7,23,11,5,17,25$.
You can then use these values as a lookup table whenever you want to get the inverse:
int GetInverseOf26(int n)
{ static int lut[] = {0,1,0,9,0,21,0,15,0,3,0,19,0,0,0,7,0,23,0,11,0,5,0,17,0,25}; return lut[n%26];
}If $a$ is coprime with $26$, then $a^{12}=a^{\phi(26)} \equiv 1 \bmod 26$ and so its inverse is $a^{11} \bmod 26$.
This can be computed fast with
$a_2 = a^2 \bmod 26$
$a_4 = a_2^2 \bmod 26$
$a_8 = a_4^2 \bmod 26$
$b = a_8 \cdot a_2 \cdot a \bmod 26$
$\endgroup$
