solve_mod -- implement solving modulo n in sage

[williamstein]

I've already had two requests just today to solve simple equations modulo n.

Here is code to be pasted into the notebook that can do it:

def solve_mod(eqns, modulus):
    """
    Return all solutions to an equation or lists of equations modulo 
    the given integer modulus.  Each equation must involve only 
    polynomials in 1 or many variables. 

    The solutions are returned as n-tuples, where n is the 
    number of variables appearing anywhere in the given equations.  
    The variables are in alphabetical order. 

    INPUT:
        eqns -- equation or list of equations
        modulus -- an integer 

    EXAMPLES:
        sage: var('x,y')
        (x, y)
        sage: solve_mod([x^2 + 2 == x, x^2 + y == y^2], 14)
        [(2, 4), (6, 4), (9, 4), (13, 4)]
        sage: solve_mod([x^2 == 1, 4*x  == 11], 15)
        [(14,)]

    Fermat's equation modulo 3 with exponent 5:
        sage: var('x,y,z')
        (x, y, z)
        sage: time solve_mod([x^5 + y^5 == z^5], 3)
        [(0, 0, 0), (0, 1, 1), (0, 2, 2), (1, 0, 1), (1, 1, 2), (1, 2, 0), (2, 0, 2), (2, 1, 0), (2, 2, 1)]

    WARNING:
        Currently this naively enumerates all possible solutions.
        The interface is good, but the algorithm is horrible if the
        modulus is at all large!   Sage *does* have the ability to do
        something much faster in certain cases at least by using
        the Chinese Remainder Theorem, Groebner basis, linear algebra
        techniques, etc.  But for a lot of toy problems this function
        as is might be useful.  At least it establishes an interface.
    """
    if not isinstance(eqns, (list, tuple)):
        eqns = [eqns]
    modulus = Integer(modulus)
    if modulus < 1:
         raise ValueError, "the modulus must be a positive integer"
    vars = list(set(sum([list(e.variables()) for e in eqns], [])))
    vars.sort()
    n = len(vars)
    R = Integers(modulus)
    S = MPolynomialRing(R, len(vars), vars)
    eqns_mod = [S(eq) if is_SymbolicExpression(eq) else \
                  S(eq.lhs() - eq.rhs()) for eq in eqns]
    ans = []
    for t in cartesian_product_iterator([R]*len(vars)):
        is_soln = True
        for e in eqns_mod:
            if e(t) != 0:
                is_soln = False
                break
        if is_soln:
            ans.append(t)

    return ans

I'll incorporate this into sage as a patch in a moment.

Component: algebraic geometry

Issue created by migration from https://trac.sagemath.org/ticket/1500

[williamstein]

Description changed:

--- 
+++ 
@@ -23,6 +23,8 @@
         (x, y)
         sage: solve_mod([x^2 + 2 == x, x^2 + y == y^2], 14)
         [(2, 4), (6, 4), (9, 4), (13, 4)]
+        sage: solve_mod([x^2 == 1, 4*x  == 11], 15)
+        [(14,)]

     Fermat's equation modulo 3 with exponent 5:
         sage: var('x,y,z')
@@ -41,11 +43,14 @@
     """
     if not isinstance(eqns, (list, tuple)):
         eqns = [eqns]
+    modulus = Integer(modulus)
+    if modulus < 1:
+         raise ValueError, "the modulus must be a positive integer"
     vars = list(set(sum([list(e.variables()) for e in eqns], [])))
     vars.sort()
     n = len(vars)
     R = Integers(modulus)
-    S = PolynomialRing(R, vars)
+    S = MPolynomialRing(R, len(vars), vars)
     eqns_mod = [S(eq) if is_SymbolicExpression(eq) else \
                   S(eq.lhs() - eq.rhs()) for eq in eqns]
     ans = []

[williamstein]

Attachment: trac-1500.patch.gz

[300dc0f9-16bb-4ab3-b547-c11ee4df10df]

comment:2

This seems to be a good implementation for the toy cryptanalysis i want to play around with.

a,b = var('a,b')
solve_mod([4*a + b == 17,19*a + b == 3],26)
///
[(6, 19)]

I like the interface a little better than "Solve[{x^2 == 1, 4*x == 2, Modulus==10}, x, Mode->Modular]."

[85eec1a4-3d04-4b4d-b711-d4db03337c41]

comment:3

Looks good to me, is doctested, doesn't touch any existing code, so merge it.

Cheers,

Michael

[85eec1a4-3d04-4b4d-b711-d4db03337c41]

comment:4

Merged in 2.9.alpha7.