Monday, December 23, 2013

Multiplicative inverse

I was thinking about the conclusions I came to in my last post, and it occurred to me that I could build a little problem solver. You could feed part of a truth table into it, and it would generate the simplest polynomial that would explain the truth table.

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-1 = x3 (mod 5)
x-1 = x5 (mod 7)
x-1 = x9 (mod 11)

The pattern here, of course, is that x-1 = xN-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.