Calculating a table of inverses modulo a prime

Question

I know that the extended euclidean algorithm is the ideal way to calculate the multiplicative inverse of a single number modulo prime p.

But what if I want to create an array A where A[x] has the inverse of x? Is there a faster way calculate such an array then by calculating the inverse of every element individually?

I intuitively expect that there is a shortcut because you have many identities like

A[x*y % p] = A[x]*A[y] % p

However I can not think of a general methodology for getting the entire array A.

If the values of (x) are small enough, it might be more efficient to use Euler's theorem, provided you can perform modular exponentiation without resorting to bignums: x^-1 = x^(p-2) (mod p) — Brett Hale
– Brett Hale, Commented Dec 24, 2012 at 1:33

Daniel Fischer · Accepted Answer · 2012-12-24 01:37:30Z

An easy way to halve the computations of the inverses is to use

inverse(p - k) = p - inverse(k)

and fill only the first half of the array using the extended Euclidean algorithm, and the remaining half by the symmetry.

I am not sure whether the following will be faster, it takes less computation, but has worse access patterns to the array, so it may well be slower:

int A[p] = {0}; A[1] = 1; for(int k = 2; k < p; ++k) { if (A[k] == 0) { // haven't found the inverse yet inv = inverse(k,p); // extended Euclidean algorithm or Fermat's theorem int m = k, i = inv; while(m != 1) { A[m] = i; m = (m*k) % p; i = (i*inv) % p; } } }

Every time you encounter a value whose inverse you don't yet know, you iteratively compute the inverses for the entire subgroup generated by that value using only two modular multiplications per element (besides the initial inversion). You should relatively soon hit a generator of the entire group of units modulo p.

user515430 · Accepted Answer · 2012-12-25 04:01:45Z

For p a prime, the elements {1, 2, 3, ..., (p-1)} form a cyclic group. That is, there exist a number (actually many) x such that {x^0, x^1, x^2, ..., x^(p-2)} is the set. After you find the inverse of x, call it y, you can get the corresponding inverses by simply raising y to the appropriate power, y^k is the inverse of x^k. How do you find such an x? Pick a random element and raise it to the power of (p-1)/2. That number will either be 1 or -1 (p-1). If it is -1, you have your generator. Raising an element to a power should be done using "exponentiation by squaring".

“If it is −1, you have your generator.” That's wrong. Try p=13 and x=5.
Daniel, you are right. Don't know what I was thinking of. For each prime divisor q of (p - 1) we must show that x raised to the power of (p - 1)/q is different from 1 mod p. In your example the reason x = 5 is not a generator is because with q = 3, x raised to the power of (13 - 1)/3 = 4, we get 1 mod 13. Thanks for catching this.

Wesner Moise · Accepted Answer · 2020-07-03 19:03:18Z

The following code is derived from the definition of the mod function:

public long[] InverseTable(long n, long p) { long[] inverse = new long[n+1]; inverse[1] = 1; for (long i = 2; i <= n; i++) inverse[i] = p - (inverse[p % i] * (p / i) % p); return inverse; }

Collectives™ on Stack Overflow

Calculating a table of inverses modulo a prime

3 Answers 3

Comments

2 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Related