Opened 13 years ago
Closed 13 years ago
#1500 closed enhancement (fixed)
[with patch, positive review] solve_mod -- implement solving modulo n in sage
Reported by: | was | Owned by: | was |
---|---|---|---|
Priority: | major | Milestone: | sage-2.9 |
Component: | algebraic geometry | Keywords: | |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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.
Attachments (1)
Change History (5)
comment:1 Changed 13 years ago by
- Description modified (diff)
Changed 13 years ago by
comment:2 Changed 13 years ago by
comment:3 Changed 13 years ago by
- Summary changed from solve_mod -- implement solving modulo n in sage to [with patch, positive review] solve_mod -- implement solving modulo n in sage
Looks good to me, is doctested, doesn't touch any existing code, so merge it.
Cheers,
Michael
comment:4 Changed 13 years ago by
- Resolution set to fixed
- Status changed from new to closed
Merged in 2.9.alpha7.
Note: See
TracTickets for help on using
tickets.
This seems to be a good implementation for the toy cryptanalysis i want to play around with.
I like the interface a little better than "Solve[{x^{2 == 1, 4*x == 2, Modulus==10}, x, Mode->Modular]." }