Finding modular inverse of every number mod 26?

Question

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?

Answer 1

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];
}

Answer 2

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$