calling invert on a symbol returns 0

[redabourial]

Here is an example :

import sympy
multiplicate_inverse = sympy.Symbol("x").invert(7)
print(multiplicate_inverse) # 0

[oscarbenjamin]

It looks like this tries to compute the inverse of x in QQ[x]/<7> but that's a nonsensical ring. Probably an error should be raised for Poly.invert if the modulus is a constant:

diff --git a/sympy/polys/polytools.py b/sympy/polys/polytools.py
index be1b71b..95ad56b 100644
--- a/sympy/polys/polytools.py
+++ b/sympy/polys/polytools.py
@@ -40,6 +40,7 @@
     PolificationFailed,
     ComputationFailed,
     GeneratorsError,
+    NotInvertible,
 )
 from sympy.polys.polyutils import (
     basic_from_dict,
@@ -2590,6 +2591,9 @@ def invert(f, g, auto=True):
         """
         dom, per, F, G = f._unify(g)
 
+        if G.degree() < 1:
+            raise NotInvertible('constant modulus in polynomial ring')
+
         if auto and dom.is_Ring:
             F, G = F.to_field(), G.to_field()
 

[oscarbenjamin]

Maybe it's deeper than that and the problem is with dup_half_gcdex:

In [1]: from sympy.polys.euclidtools import dup_half_gcdex

In [2]: dup_half_gcdex([QQ(1), QQ(1)], [QQ(7)], QQ)
Out[2]: ([], [mpq(1,1)])

The docstring says:

sympy/sympy/polys/euclidtools.py

Lines 50 to 54 in 4801871

	def dup_half_gcdex(f, g, K):
	"""
	Half extended Euclidean algorithm in `F[x]`.
	Returns ``(s, h)`` such that ``h = gcd(f, g)`` and ``s*f = h (mod g)``.

Here we have h=1 which is the correct gcd of f and g. However we have s=0 and so it is not the case that s*f = h mod g

[jksuom]

I don't think that dup_half_gcdex is to blame. s*f = h mod g is true because h = 1 is a multiple of g = 7 in the coefficient field QQ.

[oscarbenjamin]

I suppose if QQ[x]/<7> is just the zero ring then 0 is actually the correct answer since 1 = 0 and so 0 is the multiplicative inverse of every element.

[oscarbenjamin]

Possibly it's better for invert to raise an exception though as I suggested in the diff above. The invert function expects to work with either K[x] for a field K or ZZ and these give different results:

In [11]: invert(2, 5)
Out[11]: 3

In [12]: invert(2, 5, x)
Out[12]: 0

In [16]: invert(2, 5, domain=QQ)
Out[16]: 3

Probably it should be clearer in the docs that this is the expectation and perhaps domain=QQ should be consistent with QQ[x].

[asmeurer]

I wonder if the OP was actually intending to find a symbolic expression for the inverse of x mod p=7. mod_inverse ought to be the function to do that, but if you try it, it tells you to use invert:

>>> mod_inverse(x, 7)
Traceback (most recent call last):
  File "/Users/aaronmeurer/Documents/Python/sympy/sympy/./sympy/utilities/misc.py", line 545, in as_int
    return operator.index(n)
TypeError: 'Symbol' object cannot be interpreted as an integer

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "/Users/aaronmeurer/Documents/Python/sympy/sympy/./sympy/core/numbers.py", line 532, in mod_inverse
    a, m = as_int(a), as_int(m)
  File "/Users/aaronmeurer/Documents/Python/sympy/sympy/./sympy/utilities/misc.py", line 547, in as_int
    raise ValueError('%s is not an integer' % (n,))
ValueError: x is not an integer

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Users/aaronmeurer/Documents/Python/sympy/sympy/./sympy/core/numbers.py", line 540, in mod_inverse
    raise TypeError(filldedent('''
TypeError:
Expected numbers for arguments; symbolic `mod_inverse` is not
implemented but symbolic expressions can be handled with the similar
function, sympy.polys.polytools.invert

You can also do Mod(1/x, 7), but that doesn't seem to be actually implemented correctly:

>>> pow(x, -1, 7)
Mod(1/x, 7)
>>> pow(x, -1, 7).subs(x, 2)
1/2
>>> mod_inverse(2, 7)
4

[oscarbenjamin]

The result for Mod(1/x, 7) is correct. The Mod function is not expected to interpret 1/x as meaning a modular multiplicative inverse. There is not currently any symbolic representation of a modular multiplicative inverse.

[asmeurer]

Why is that? Is there a special definition used for rational numbers in Mod? Nothing is documented in the Mod docstring. I don't see the benefit of not treating inversions in Mod as modular inverses.

And even if this is the case, then returning this from pow is wrong, because pow(x, -1, p) is supposed to mean modular inverse.

[oscarbenjamin]

Mod(x, 7) is just a real function of x. Plot it and see:

plot(Mod(x, 7))

This is a symbolic version of what % (modulo division) does in Python for floats:

In [133]: 1/2 % 7
Out[133]: 0.5

If the argument happens to be given as x or 1/x that doesn't change what the Mod function itself is. No other SymPy function changes it's meaning depending on the structure of the expression that it receives in its args.

And even if this is the case, then returning this from pow is wrong, because pow(x, -1, p) is supposed to mean modular inverse.

Yes, that is wrong. Mod should correctly correspond to % (which it does):

In [134]: print(x % 1)
Mod(x, 1)

[asmeurer]

I see. So there are three notions of mod: polynomial modulo a polynomial, integer modulo a prime, and real modulo a real. Mod currently does the third of these, and the polys support the first one, but we can only do the second indirectly through Mod when the definitions align, or with some functions like mod_inverse. (there's actually even more notions than that, but those are the relevant ones here)

Really, we need a much better way to represent elements of a cyclic finite field (or ring). There's GF in the polys, but it's hidden and clunky to deal with, especially if you do want to deal with symbolic elements. This is something that comes up a lot in many places like StackOverflow questions. Note that an element of GF(p)[x] is not the same as a symbolic element x of GF(p). For instance, $x^7 - x$ is identically 0 mod 7 by Fermat's little theorem, but it is considered a degree 7 polynomial distinct from 0 in $Z_7[x]$.

This is all mostly off topic for this issue, though. If this existed I would have suggested mentioning it in the error message for invert(0), but since it doesn't, I think we can at best just mention mod_inverse, even though it doesn't actually work for symbolic x. The error message in mod_inverse really shouldn't refer people to invert, or if it does, it should caveat it by saying that invert does polynomial modular inverse, which is not the same thing as symbolic inverse mod a prime.

[asmeurer]

It would also be good to have a document in the docs clarifying the difference between polynomial algorithms and integer algorithms. There's a lot of functions that one might expect to operate on $\mathbb{Z}$ but actually operate on $\mathbb{Q}[x]$. For example:

• gcd vs. igcd
• factor vs. factorint
• invert vs. mod_inverse

There's also further subtleties depending on whether the base ring of the polynomial operation is $\mathbb{Z}$ or $\mathbb{Q}$, and conversely, some "integer" functions are also extended to rational or real numbers. It doesn't help that some of the polynomial functions like gcd "automatically" do the integer variant when presented with integers.

A document explaining the mathematical distinctions here with a table of the different functions for each would be quite useful.