2

For a certain project, I'm using sympy to calculate expressions modulo another function. These functions all have binary coefficients (so x^2 + 2x = x^2$). Their application is in Galois Fields.

My issue is that when using the the sympy rem function with inverses (for example x**-1), is simply returns the inverse of the number (so in this case the answer is 1/x) rather than returning the modular inverse.

Due to the below comment, here is some further clarification. An oversimplified version of what I'm doing is:

from sympy import *
x = symbols('x')
f = raw_input() #here f = '(x^3 + x)*(x + 1)^2 + (x^2 + x)/(x^3) + (x)^-1'
expand(f)
>>> x**5 + 2*x**4 + 2*x**3 + 2*x**2 + x + 2/x + x**(-2)

#this is what I'm currently doing
rem(expand('(x^3 + x)*(x + 1)^2 + (x^2 + x)/(x^3) + (x)^-1'), 'x^2')
>>> x + 2/x + x**(-2)
#not the answer I am looking for, as I want all the degrees to be positive

This remainder function doesn't act as a mod function (ie doesn't keep things as positive powers of x), and I'm trying to find a replacement for it. I want to avoid parsing through the expression searching for inverse mods and just have the function deal with that on it's own. I might be missing a parameter, or just looking at a completely different function.

PS: I know that the ability to compute an expression mod another expression, while simultaneously treating inverses as modular inverses exists in sympy since I did it while testing that sympy will be enough for our purposes but didn't save the code back then.

Emad Y
  • 415
  • 4
  • 14
  • Can you write your own function? If so, check out [this question](http://stackoverflow.com/questions/4798654/modular-multiplicative-inverse-function-in-python). – Jared Goguen May 02 '16 at 17:29
  • 1
    Also, is [this method](http://docs.sympy.org/0.6.7/modules/polynomials.html#sympy.polys.Poly.invert) what you're looking for? – Jared Goguen May 02 '16 at 17:30
  • Not exactly. I'll edit my question so that I clear up somethings, but basically: I'm trying to avoid the trouble of having to parse the entire string to check for inverses, as the expression might be complex, and I want to evaluate all of it. If this is not possible, I will obviously have to do what you suggested, but I think it is possible, hence the question. – Emad Y May 02 '16 at 18:56
  • Also, please note that I realize that this choice of mod (`x^2`) is a bad one, I just picked it so that the example wouldn't be too long – Emad Y May 02 '16 at 19:14

1 Answers1

1

First off, it's better to immediately convert your string into a SymPy expression with sympify. Passing strings to SymPy functions is bad practice.

When you use a polynomial like x + 1/x, SymPy treats this as a polynomial in x and 1/x.

In [73]: Poly(x + 1/x)
Out[73]: Poly(x + (1/x), x, 1/x, domain='ZZ')

I believe ratsimpmodprime does what you want. You should also be able to pass domain=GF(2), but it seems there are some bugs that prevent that from working.

asmeurer
  • 86,894
  • 26
  • 169
  • 240