Some internet & literature searching revealed a bunch of embarrassingly stupid schemes for making a table telling you for each x, what is y so that x*y (mod p) = 1 where p is some fixed prime modulus. There are less-stupid ways to do it. Here is one; maybe you can do even better. Step 1. find a generator mod p. That is, find g so that g^(p-1) mod p=1 but g^((p-1)/d) mod p is not 1 for any divisor d of p-1. Then g's inverse is f where f=g^(p-2). [Simply random trials will find such a g quickly, i.e. way sublinear(p) time.] Step 2. for k=0,1,...,p-1: write f^k (mod p) into entry g^k (mod p) of your table. The end. Another approach is to do this for some random g which might not be a generator, then while the table of inverses you get is not filled up, go to a random unfilled entry, make that location be your new g, and do it again. --Warren D. Smith