Ask Your Question

Revision history [back]

All the solutions of a polynomial system over a finite ring

Let $E$ be a finite set of polynomial equations with variables $x_1, \dots, x_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,"x")
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?

All the solutions of a polynomial system over a finite ring

Let $E$ be a finite set of polynomial equations with variables $x_1, $t_0, \dots, x_r$ 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,"x")
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]

All the solutions of a polynomial system over a finite ring

Let $E$ be a finite set 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$, $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]

All the solutions of a polynomial system over a finite ring

Let $E$ be a finite set 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]
click to hide/show revision 5
retagged

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]