[math-fun] build table of multiplicative inverses without dying of embarrassment
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
yes, my proposed algorithm will build the full p-1 entry table of inverses in O(p) arithmetic operations and using basically no memory. Methods like extended euclidean algorithm, continued fraction alg, (p-2)-power alg, and "brute force" trying all possible candidate-reciprocals, all take longer than linear time, ranging from p*log(p) to p^2 time, plus mine is easier (or not much harder) to program. I also saw advocated building tables of discrete logs then using them to compute the inverses, which achieves O(p) time again (with a larger constant) but only at the cost of using much more memory and more code complexity. For example, these bad approaches were advocated on the Numerical Recipes blog. However, if you do not want the full table, only want one, then yes, I agree with Gosper the continued fraction trick is very elegant, in fact more elegant than I had realized.
participants (1)
-
Warren Smith