Changeset 7633:2a522c38737a

Timestamp:

12/13/07 16:36:42 (6 years ago)

Author:

William Stein <wstein@…>

Branch:

default

Message:

trac #1500 - solve_mod command, that solves equations modulo n.

Location:

sage/calculus

Files:

• all.py (modified) (1 diff)
• equations.py (modified) (2 diffs)

sage/calculus/all.py

@@ -1 @@
-from equations import SymbolicEquation, forget, assume, assumptions, solve
+from equations import (SymbolicEquation,
+                       forget, assume, assumptions,
+                       solve, solve_mod)
 
 from calculus import (SymbolicExpressionRing,

sage/calculus/equations.py

@@ -524 +524 @@
 
         INPUT:
-            x -- a SymbolicVariable object (if not given, the first in the expression is used)
-            multiplicities -- (default: False) if True, also returns the multiplicities
-                          of each solution, in order. 
-            solution_dict -- (default: False) if True, return the solution as a dictionary rather than an equation.
-            explicit_solution -- (default: False); if True, require that all solutions
-                returned be explicit (rather than implicit)
-        OUTPUT:
-            A list of SymbolicEquations with the variable to solve for on the
-            left hand side.
+            x -- a SymbolicVariable object (if not given, the first in
+                 the expression is used)
+
+            multiplicities -- (default: False) if True, also returns
+                          the multiplicities of each solution, in order.
+
+            solution_dict -- (default: False) if True, return the
+                        solution as a dictionary rather than an equation.
+            
+            explicit_solution -- (default: False); if True, require
+                that all solutions returned be explicit (rather than
+                implicit) OUTPUT: A list of SymbolicEquations with the
+                variable to solve for on the left hand side.
 
         EXAMPLES:
@@ -781 +785 @@
     return Sequence(v, universe=objs, cr_str=True)
 
+
+############################################################
+# Solving modulo N
+
+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: 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.
+    """
+    from sage.rings.all import Integer, Integers, MPolynomialRing
+    from calculus import is_SymbolicExpression
+    from sage.misc.all import cartesian_product_iterator
+    
+    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