Modular Equation Solver in Solveset - sympy/sympy GitHub Wiki
Modular equations deals with the Modular arithmetic and the Modulo operation.
-
a mod n
refers to the remainder when a is divided by n
From the Euclid's division Lemma, we know that,
a = q * n + r
-
Modulo equivalence : a ~ b mod n , iff n divides (a - b)
We will say that a and b are equivalent modulo, where ~ is the congruence modulo operator
An important thing to be noted is that modular equations deals with integer solutions
More about congruence can be found out here.
The application of modular equations can seen in the generation of random numbers with Linear congruential generator as explained here
There are a bunch of equations involving the modular arithmetic which solveset
currently is not able to solve.
Issue #13178 relates to the same. Fixing this would make solveset
a versatile solver. The basic idea to be used here is solving such equations by gradually inverting it.
The current invert()
would fail to do so because :
- It does not incorporate the "wrap around" technique, where an integer upon reaching a certain value repeats itself.
- Multiplication and division operations are different from those of the conventional arithmetic. Here the logic multiplicative inverse has to be used.
- Exponential equations cannot be solved by the general log method, rather a different method involving
discrete_log
has to be used.
So here comes a need of a different invert()
which would solve these types of equations with a different logic, but the same technique. This has to be done by implementing the invert_modular()
which would add-on solveset's
ability to solve Modular equations
This would require two things:
1. Identification of Modular equations
2. Solving via inversion