Odwrotność modulo

Witam,
znalazłem na internecie bardzo fajne rozwiązanie obliczania a^p(mod x) dla dużych liczb - http://stackoverflow.com/questions/4236673/sample-code-for-fast-primality-testing-in-c-sharp
Czy może któryś z forumowiczów wie jak poniższe rozwiązanie przekonwertować na rozwiązanie problemu odwrotności modulo dla dużych liczb (a^p)-1(mod x) ?

    ulong pow(ulong a, ulong p, ulong mod)
    {
        if (p == 0) return 1;
        if (p % 2 == 0) return pow(mul(a, a, mod), p / 2, mod);
        return mul(pow(a, p - 1, mod), a, mod);
    } 

ulong mul(ulong a, ulong b, ulong mod)
    {
        int i;
        ulong now = 0;
        for (i = 63; i >= 0; i--) if (((a >> i) & 1) == 1) break;
        for (; i >= 0; i--)
        {
            now <<= 1;
            while (now > mod) now -= mod;
            if (((a >> i) & 1) == 1) now += b;
            while (now > mod) now -= mod;
        }
        return now;
    }

Nie ma czegoś takiego jak odwrotność modulo (chyba).
Ten link co podałeś pozwala szybko przetestować czy liczba jest potencjalnie pierwsza ("fast primality testing").
Nie wiem czy to jest dokładny test, ale pewnie działa w ten sposób, że mówi czy dana liczba jest "na pewno nie-pierwsza".

Co do wzoru to spróbuj go zapisać poprawnie z nawiasami i operacjami mnożenia i potęgowania, albo przy użyciu tego narzędzia poniżej, bo nie widać o co Ci chodzi bez zgłębiania tematu:

http://www.codecogs.com/latex/eqneditor.php

http://s17.postimage.org/w0yjkgccb/wzor.gif - to jest mój problem :) czyli ElGamal. Operuję na liczbach typu ulong. Jestem w stanie zaszyfrować wiadomość - gorzej z operacją odszyfrowania.

Liczbę odwrotną w pierścieniu liczy się rozszerzonym algorytmem Euklidesa.
O ile dobrze pamiętam to dla dużych liczb problemu tego nie rozwiążesz w rozsądnym czasie.

Jak ktoś będzie miał jeszcze taki problem jak ja to proponuję korzystać np. z http://www.codeproject.com/Articles/2728/C-BigInteger-Class - tam jest zaimplementowana odpowiednia metoda do odwrotności liczby. Potestuję to jak będę miał czas ;)