Fast Modular (% prime) Inverses

Description:

Find inverses of all numbers 1 through P-1 where P is a prime number in O(P) time. One can find mod inverses of all numbers from 1 to P-1 by using Fermat's little theorem but that takes time O(P log P). This technique is much more efficient. It is based on the following recurrence relation:

inverse[1] = 1
inverse[i] = -(P / i) * inverse[P mod i];

Implementation

#include <cstdio>
#include <cassert>
#include <iostream>

using namespace std;

const int P = 11; // To adjust (must be prime).
long long r[P];

/* For debugging only */
long long power(long long x, long long y) {
    if(y == 0)
        return 1;

    long long ans = power(x, y / 2);
    ans = (ans * ans) % P;
    if(y % 2 == 1)
        ans = (ans * x) % P;

    return ans;
}

/* Example */
int main( void ) {
    r[1] = 1;
    for(int i = 2; i < P; i++)
        r[i] = ((P - (P / i)) * r[P % i]) % P;

    // Check
    for(int i = 1; i < P; i++)
        assert(power(i, P - 2) == r[i]);

    return 0;
}