Thursday, December 26, 2013

Discrete logarithm as a polynomial

I finally had time to retool my "solver" so it could work on polynomials with multiple indeterminates. Much debugging was required, but in the process I discovered a number of ways to make it run more quickly.

Once I had it running correctly, I wanted to start exploring the modular logarithm function. I immediately ran into trouble because the modular exponent is not a permutation, so for some values there may be multiple valid logarithms, and for other values there may be none. I'll have to figure out how to make that work properly.

In the meantime I managed to put in place some manual workarounds. The solutions have a strange kind of beauty, but I'm not sure how to present them, and I think I should find the proper way to handle the shortcomings I noted above.

How long would it take to calculate the logarithm (mod N) as a polynomial?  Looking at sample solutions for N=3 through N=11, I think the calculation could be done in roughly 2N3 operations (multiplications and additions--provided unlimited memory to cache precalculated values).  Given that the brute force approach would only require a maximum of 2N multiplications and comparisons, I think it's fair to say that the discrete logarithm probably cannot be calculated in polynomial time with any kind of polynomial expression.

No comments:

Post a Comment