Revision history - ASKSAGE: Sage Q&A Forum

In fact, my custom implementation of variety() method from (other answer)[https://ask.sagemath.org/question/55545/sage-crash-when-computing-variety-for-an-ideal-with-many-variables/?answer=55642#post-id-55642] works fine here and finds 144 solutions within a few seconds. It only needs a custom implementation of roots() method that supports polynomials with the content non-coprime to the ring modulus:

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

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

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

    mg = m//g
    pg = (pz/g).change_ring(Integers(mg))

    roots = pg.roots(multiplicities=False)

    # 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 + r).lift() for r in roots)

In fact, my custom implementation of variety() method from ~~(other answer)[https://ask.sagemath.org/question/55545/sage-crash-when-computing-variety-for-an-ideal-with-many-variables/?answer=55642#post-id-55642]~~ other answer works fine here and finds all 144 solutions within a few seconds. It only needs a custom implementation of roots() method that supports polynomials with the content non-coprime to the ring modulus:

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

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

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

    mg = m//g
    pg = (pz/g).change_ring(Integers(mg))

    roots = pg.roots(multiplicities=False)

    # 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 + r).lift() for r in roots)

In fact, my custom implementation of variety() method from other answer works fine here and finds all 144 solutions within a few seconds. It only needs a custom implementation of roots() method that supports polynomials with the content non-coprime to the ring modulus:

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

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

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

    roots = pg.roots(multiplicities=False)
(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 + r).lift() for r in roots)

In fact, my custom implementation of variety() method from other answer works fine here and finds all 144 solutions within a few seconds. It only needs a custom implementation of roots() method that supports polynomials with the content non-coprime to the ring modulus:

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

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

    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 (r2 + r).lift() r for r in roots)

In fact, my custom implementation of variety() method from other answer works fine here and finds all 144 solutions within a few seconds. It only needs a custom implementation of roots() method that supports polynomials with the content non-coprime to the ring modulus:

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

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 + r for r in roots)

In fact, my custom implementation of variety() method from other answer works fine here and finds all 144 solutions within a few seconds. It only needs a custom implementation of roots() method that supports polynomials with the content non-coprime to the ring modulus:

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

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 + r ZZ(r) for r in roots)

In fact, my custom implementation of variety() method from other answer works fine ~~here and finds all 144 solutions within a few seconds. It only needs~~ here, provided two things:

a custom implementation of roots() method that supports polynomials with the content non-coprime to the ring ~~modulus:~~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 = J.basis
    R = J.basis[0].parent()
    while True:
        newB = []
        for b in B:
            r = R.ideal(list(set(B)-{b})).reduce(b)
            if r:
                newB.append(r)
        if newB == B:
            break
        B = newB
    return B


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.

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 = J.basis
list(J.gens())
    R = J.basis[0].parent()
J.ring()
    while True:
        newB = []
        for b in B:
updated = False
        for i in range(len(B)):
            r = R.ideal(list(set(B)-{b})).reduce(b)
R.ideal(list(set(B)-{B[i]})).reduce(B[i])
            if r:
                newB.append(r)
r!=B[i]:
                B[i] = r
                updated = True
        if newB == B:
            break
        B = newB
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.

Revision history [back]