I actually managed to write the thing, and it works. I have never written anything like this before, so it was an interesting experiment.

Of course, to write it, I had to write a function to calculate the multiplicative inverse of a number in [1..N-1] (mod N), so naturally the first thing I wanted to do with it when I was done is see what polynomial generates the multiplicative inverse.

My solver only works for prime values of N, and the result was interesting:

x

^{-1}= x (mod 3)
x

x^{-1}= x^{3}(mod 5)^{-1}= x

^{5}(mod 7)

x

^{-1}= x^{9}(mod 11)
The pattern here, of course, is that x

^{-1}= x^{N-2}(mod N). The Wikipedia article on modular multiplicative inverse mentions that this precise formula works, but only for prime values of N.
My current solver only works for polynomials of a single indeterminate, but I ought to be able to write one that works for multiple indeterminates. If I get the time to do it, the first thing I'm going to look at is the inverses of the exponent function.

## No comments:

## Post a Comment