# All the solutions of a polynomial system over a finite ring

Let $E$ be a finite list of polynomial equations with variables $t_0, \dots, t_r$ over the finite ring of integers modulo $n$ (for some $n$). We can compute the Groebner basis as follows:

ZN=Integers(n)
R=PolynomialRing(ZN,r,"t")
R.inject_variables()
Id=R.ideal(E)
G=Id.groebner_basis()


Usually, over a field and if Id.dimension()=0 then we can get all the solutions by Id.variety(). But here the dimension is not necessarily $0$ and moreover it is not over a field but a ring, the finite ring of integers modulo $n$. By finiteness of the ring, there still have finitely many solutions. How to get them all?

Example: $n=248832$, $r=10$ and:

sage: G
[t4*t7, t7*t8, t7*t9, t0, t1, t2, t3 + 248831*t4, 2*t4, t5 + 248783*t7, t6 + 11*t7, 9*t7, 4*t8 + 248828*t9, 16*t9]

edit retag close merge delete

1

In your example, all non-linear polynomials (like t4*t7) are reducible and furthermore are products of linear factors. So, it's enough to iterate over their factors, making them equal to divisors of zero, to obtain a number of systems of linear equations, which can be solved via integer lattices like explained in https://ask.sagemath.org/question/625...

( 2022-06-11 14:14:14 +0200 )edit

@Max Alekseyev Is it working as well for the finite ring of integers modulo $n$?

( 2022-06-11 15:53:24 +0200 )edit
1

The standard approach to modeling "modulo $n$" is by adding a term $n\cdot z_i$ to the $i$-th equation (where $z_i$ are new integer variables) and considering the resulting system over the integers.

( 2022-06-11 17:10:07 +0200 )edit

Sort by » oldest newest most voted

In fact, my custom implementation of variety() method from other answer works fine here, provided two things:

• a custom implementation of roots() method that supports polynomials with the content non-coprime to the ring modulus;
• a correct implementation of interreduced_basis()method avoiding the bug https://trac.sagemath.org/ticket/33982

It finds all 1152 solutions within a few seconds.

import itertools
from sage.rings.finite_rings.integer_mod_ring import crt as mycrt

def myinterreduced_basis(J):
B = list(J.gens())
R = J.ring()
while True:
updated = False
for i in range(len(B)):
r = R.ideal(list(set(B)-{B[i]})).reduce(B[i])
if r!=B[i]:
B[i] = r
updated = True
if not updated:
return B
B = [b for b in B if b!=0]

def myroots(p):
R = p.base_ring()
if not isinstance(R,sage.rings.abc.IntegerModRing):
yield from p.roots(multiplicities=False)
return

m = R.zero().modulus()
pz = p.change_ring(ZZ)
g = gcd(gcd(pz.coefficients()),m)
mg = m//g

roots = (pz/g).roots(ring=Integers(mg),multiplicities=False)  # roots modulo mg = m/g

# embedding roots modulo mg to modulo m=mg*g
for rr in itertools.product( *( [Mod(r*q^valuation(mg,q),q^k) for r in range(q^valuation(g,q))] for q,k in factor(m) ) ):
r2 = mycrt(rr)
yield from (r2 + ZZ(r) for r in roots)


In fact, computing the interreduced basis of G immediately eliminates quadratic terms, and so the problem can be reduced solving linear equations right away as explained in the comments. This way it takes just a fraction of a second to get all the solutions.

more

I solved the example by hand, and I found $1152$ solution (whereas you found $144$ ones). The problem may come from the quadratic equations: for all $1152$ solutions, t4*t7, t7*t8 and t7*t9 are always equal to $0$ modulo $n$ (unless I am mistaken).

( 2022-06-12 06:05:01 +0200 )edit

Here is the reason for missing solutions: https://trac.sagemath.org/ticket/33982

( 2022-06-12 20:12:49 +0200 )edit

But you did not use interreduced_basis. I hope that the use of groebner_basis on non-field (say Integers(n)) does not produce wrong results.

( 2022-06-13 04:46:36 +0200 )edit

It is used in myvariety function. Replacing it with groebner_basis may help, but will be slower.

( 2022-06-13 05:13:20 +0200 )edit
1

I've updated my answer accordingly and all 1152 solutions are in place. I also confirm that all t4*t7, t7*t8 and t7*t9 are implied to be zero by the other terms as they are eliminated in the interreduced basis. Their presence in the Groebner basis seems to indicate that there is also a bug in .groebner_basis() method.

( 2022-06-13 17:08:23 +0200 )edit